1

我正在尝试为教育目的实现 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

但我想首先确保我不只是勉强离场，否则离得太远了。

4

0 回答 0