Избегайте вставки дубликатов в двоичном дереве поиска

Question

Итак, у меня есть дерево двоичного поиска, которое отлично работает, за исключением того факта, что я не хочу вставлять дубликаты. Я пробовал подумать над несколькими способами сделать это, но, похоже, не понял этого.

То, что я пытаюсь сделать, это сначала вызвать мой метод поиска, прежде чем вставлять что-либо, чтобы проверить, а если нет, то вставьте метод вставки курсора.

Кто-нибудь знает хороший способ приблизиться к этому? Правильно ли моя логика?

Вот мой метод вставки:

bool BinarySearchTree::treeInsert(string courseNumber, string courseTitle) 
{ 
Course * z = new Course(courseNumber, courseTitle); 
Course *x, *y; 
y = NULL; 
x = root; 

while (x != NULL){ 
    y = x; 
    if(z->getCourseNumber() < y->getCourseNumber()){ 
     x = x->getLeft(); 
    } else{ 
     x = x->getRight(); 
    } 
} 
z->setParent(y); 

if (y == NULL){ 
    root = z; 
} else if (z->getCourseNumber() < y->getCourseNumber()){ 
     y->setLeft(z); 
    } 
    else { 
     y->setRight(z); 
    } 
} 

Заранее спасибо

Answer 1

Я предлагаю проверить равенство в цикле вместо того, чтобы следовать цепочке >= и возвращать false, если вставка не выполняется. Создание нового элемента будет создано только при условии, что оно будет использоваться:

bool BinarySearchTree::treeInsert(string courseNumber, string courseTitle) 
{ 
    Course *x=root, *y=nullptr; 

    while (x != NULL) { 
     y = x; 
     if(courseNumber < y->getCourseNumber()) 
      x = x->getLeft(); 
     else if(courseNumber==y->getCourseNumber()) 
      return false; 
     else x = x->getRight(); 
    } 
    Course * z = new Course(courseNumber, courseTitle); 
    z->setParent(y); 
    if (y == NULL) 
     root = z; 
    else if (z->getCourseNumber() < y->getCourseNumber()) 
      y->setLeft(z); 
    else y->setRight(z); 
    return true; 
} 

Answer 2

В вашем методе вставки в конце цикла, когда вы пытаетесь вставить дубликат, номер курса в y будет равный номеру курса в z. Если это так, не делайте ничего (кроме удаления z, поскольку вы в настоящее время выделили его, даже если он вам не нужен).