gpt4 book ai didi

c++ - AVL Tree Rotation 的正确实现是什么?

转载 作者:塔克拉玛干 更新时间:2023-11-03 07:35:29 27 4
gpt4 key购买 nike

将 50,49,48 插入 AVL 树时,它会打印出来。

The root is: 50 
50 Level: 0 Height: 0

49 Level: 1 Height: 0
50 Level: 0 Height: -1

50 Level: 0 Height: 0 -->> Rotation did not work?

这是我的功能。向左旋转:

void AVLTree::rotateLeft(AVLNode* node)
{
AVLNode* otherNode = node;


otherNode = node->leftchild;
node->leftchild = otherNode->rightchild;
otherNode->rightchild = node;

node->height = max( height(node->leftchild), height(node->rightchild)) +1;
otherNode->height = max( height(otherNode->leftchild) , height(otherNode->rightchild))+1;
node = otherNode;

}

插入:

AVLTree::AVLNode* AVLTree::insert(int d,AVLNode *n){
if (n == NULL)
{
n = new AVLNode;
n->data = d;
n->leftchild = NULL;
n->rightchild = NULL;
n->height = 0;

} else if( d < n->data) {

n->leftchild = insert(d,n->leftchild);

if (height(n->leftchild) - height(n->rightchild) == 2) {
if (d < n->leftchild->data) {
rotateLeft(n);
} else {
rotateLeftTwice(n);
}
}

} else if (d > n->data) {

n->rightchild = insert(d,n->rightchild);

if (height(n->rightchild) - height(n->leftchild) == 2) {
if (d > n->rightchild->data) {
rotateRight(n);
} else {
rotateRightTwice(n);
}
}
} else {
;
}
n->height = max(height(n->leftchild), height(n->rightchild))+1;
return n;}

最佳答案

rotateLeft 函数的node 参数是rotateLeft 中的局部变量。换句话说,当您在 rotateLeft 中为该变量赋值时,insert 中的 n 变量不会被修改。您需要通过指针或引用将 n 传递给 rotateLeft,即要么

void AVLTree::rotateLeft(AVLNode** node)

void AVLTree::rotateLeft(AVLNode*& node)

同样的原则也适用于insertn参数——如果你想让一个函数修改一个变量的值,你需要给它传递一个指针或引用到那个变量而不是它的值。

关于c++ - AVL Tree Rotation 的正确实现是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5224733/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com