Делать ротацию для AVL - PullRequest
Новая
       10

Делать ротацию для AVL

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

Я пытаюсь реализовать дерево AVL для образовательных целей, но ротация работает не так, как я ожидал.

У меня есть узлы, каждый из которых имеет указатель на левый, правый и родительский узлы.

Ниже приведен мой код для вращения вправо-вправо.Во-первых, (как я поясню, это то, что я понимаю как случай RR) 

a
  \
   b
    \
     c

Код для поворота - 

if (subTreeRoot == root) {
  this->root=subTreeRoot->right;
}
else { // not resetting at root
  subTreeRoot->right->myParent = subTreeRoot->myParent;      
  subTreeRoot->myParent->right = subTreeRoot->right;           
}
subTreeRoot->right->left = subTreeRoot;
subTreeRoot->right = NULL;  
subTreeRoot->height = 1;   
return;

Это на самом деле работает.Это даже работает, если a не является корнем.

Неудачный тестовый пример - это что-то вроде dcbae

В этом случае я делаю поворот, а затем подхожу и вставляю что-то еще.

Я собирался вернуться и посмотреть на

http://www.cse.ohio -state.edu / ~ sgomori / 570 / avlrotations.html

Но яСначала я хотел убедиться, что я не только вдали или в другом месте.

...