AVL树旋转的正确实现是什么?

发布于 2024-10-20 12:07:47 字数 1590 浏览 4 评论 0原文

当将 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;}

When inserting 50,49,48 into an AVL Tree, it prints out.

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?

Here are my functions.
Rotate Left:

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;

}

insert:

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;}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

最单纯的乌龟 2024-10-27 12:07:47

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

void AVLTree::rotateLeft(AVLNode** node)

的原理也

void AVLTree::rotateLeft(AVLNode*& node)

适用于 insertn 参数 - 如果您希望函数修改变量的值,则需要向其传递一个指针或引用该变量而不是它的值。

The node parameter to your rotateLeft function is a local variable in rotateLeft.
In other words, when you assign a value to that variable in rotateLeft, the n variable in insert is not modified. You need to pass n to rotateLeft either through a pointer or through a reference, i.e.
either

void AVLTree::rotateLeft(AVLNode** node)

or

void AVLTree::rotateLeft(AVLNode*& node)

The same principle applies to insert's n parameter - if you want a function to modify the value of a variable, you need to pass it a pointer or reference to that variable rather than its value.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文