我正在尝试为教育目的实现 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
但我想首先确保我不只是勉强离场,否则离得太远了。