установка родителя в дереве AVL - PullRequest
Новая
       10

установка родителя в дереве AVL

0 голосов
/ 06 августа 2010

Я пытаюсь реализовать дерево AVL и не уверен, как лучше всего вставить и отследить родительский узел каждого узла.Это познавательно, поэтому, пожалуйста, не предлагайте «использовать повышение»:)

Это компилируется, но я не уверен в его правильности или в том, что это лучший способ.В частности, это 

insert(someNumber,root,root);

Кроме того, я буду переделывать часть высоты, когда перебалансирую и поднимаю дерево.

Я вставляю вот так 

myTree.insert(someNumber);

Вотметод.Я не уверен, что мой второй параметр должен быть здесь.Я бы подумал NULL, но компилятору это не нравится (другое определение функции). 

void Tree::insert(int someNumber){
    insert(someNumber,root,root);
}

Вот моя вставка 

void Tree::insert(int someNumber,Node*& subTreeRoot,Node*& parent){
    if(subTreeRoot==NULL)
    {
        subTreeRoot = new Node(someNumber,parent);
        if(subTreeRoot->myParent)   
    }
    else if (someNumber<subTreeRoot->myNumber)
    {
        if((subTreeRoot->right==NULL)||((subTreeRoot->left!=NULL)&&(subTreeRoot->right!=NULL)))
            subTreeRoot->height++;
        insert(someNumber,subTreeRoot->left,subTreeRoot);
    }
    else
    {
        if((subTreeRoot->left==NULL)||((subTreeRoot->left!=NULL)&&(subTreeRoot->right!=NULL)))
            subTreeRoot->height++;
        insert(someNumber,subTreeRoot->right,subTreeRoot);
    }
}

-

Ответы [ 2 ]

1 голос
/ 06 августа 2010

Поскольку вы делаете это для образования, я бы посоветовал вам отработать некоторые случаи вручную, а затем закодировать их в тесты вида 

 Insert(6);
 Insert(11);
 // ...
 Insert(3);

 Node test = root;
 assert(root->height == 3);
 assert(root->value == 6);
 test = root->right;
 assert( ... );

номера полностью составлены.

Это будет

  1. Дайте вам больше, чем ощущение, работает ли ваш код. (Подсказка: если вы не уверены, что ваш код работает, вероятно, это не так)
  2. Дайте вам место, чтобы начать выяснять, что происходит не так.
  3. Развить привычку к тестированию. Для некоторых людей нелогично, что написание вдвое больше кода (тесты + код) быстрее, чем просто написание кода, но попробуйте. Плюс написание большего кода = больше практики.
0 голосов
/ 06 августа 2010

В чем разница между деревом и узлом? (Дерево является только заполнителем для корневого узла, не более того. Иногда говорят, что узел имеет два поддерева. Дерево и узел не отличаются. Достаточно одного класса.)

Почему бы просто не рассчитать высоту, когда вам это нужно? Намного проще программировать и корректировать доказательства. Если вам мешает производительность, вы всегда можете изменить функцию, чтобы она возвращала кэшированное значение.

Узел не должен знать, что он родитель (по моему мнению). Таким образом, функция вставки нуждается в родительском параметре. После создания нового узла сравните глубину «родители-дети», чтобы увидеть, нужно ли вам делать какие-либо повороты. Программирование поворотов очень сложно: попробуйте, отладьте и протестируйте! 

Node::insert(int number,Node * parent)
{
  //code
  left=new node(number);
  if (parent->left->depth() > parent->right->depth()+1)
    parent->rotate_tree_or_something();
  //
}
...