欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

AVL树(平衡搜索二叉树)

程序员文章站 2022-06-07 08:21:56
...

二叉搜索树具有很高的灵活性,,对其进行优化可以生成平衡搜索二叉树。
AVL树为高度平衡的二叉搜索树,能保持二叉树的高度平衡,尽量降低二叉树的高度,减少树的平均搜索长度。
AVL树增删查改的效率都是O(lgN)。

AVL树的特性:
左子树和右子树高度之差绝对值不超过1;
树中的每个左子树和右子树都应该是AVL树;每个节点都有一个平衡因子,任一节点的平衡因子都等于右子树高度减去左子树高度,且平衡因子是-1 0 1.

AVL树的插入:
插入操作和二叉搜索树的插入操作基本相同,不同的是AVL树在插入数据之后需要对每个节点的平衡因子进行判断(每个节点的平衡因子)分为以下三种情况:
循环的条件是parent存在:

1.当新插入节点的父亲节点的平衡因子_bf==0,return true插入成功;
2.当新插入节点的父亲节点的平衡因子_bf==1|_bf==-1,需要往上不断进行更新,cur=parent;parent=cur->parent;;
3.当新插入节点的父亲节点的平衡因子_bf==2|_bf==-2,这是需要根据情况进行旋转:

右单旋: parent->_bf==-2 cur->_bf==-1
AVL树(平衡搜索二叉树)

说明:当此时的parent已经是整棵树的根节点的时候,subL=parent;如果存在pparent,还需要判断subL位于pparent的左子树还是右子树。
调节完成后需要将subL和parent的平衡因子置0.

    void Rotate_R(Node* parent)
    {
        Node* ppNode = parent->_parent;
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        parent->_left = subLR;
        if (subLR)
        {
            subLR->_parent = parent;
        }
        subL->_right = parent;
        parent->_parent = subL;
        if (_root == parent)
        {
            _root = subL;
            subL->_parent = NULL;
        }
        else
        {
            if (parent == ppNode->_left)
            {
                ppNode->_left = subL;
                subL->_parent = ppNode;
            }
            else
            {
                ppNode->_right = subL;
                subL->_parent = ppNode;
            }
        }
        subL->_bf = 0;
        parent->_bf = 0;
    }

左单旋: parent->_bf==2 cur->_bf==1
AVL树(平衡搜索二叉树)
说明:当此时的parent已经是整棵树的根节点的时候,subR=parent;如果存在pparent,还需要判断subR位于pparent的左子树还是右子树。
调节完成后需要将subR和parent的平衡因子置0。

void Rotate_L(Node* parent)
    {
        Node* ppNode = parent->_parent;
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        parent->_right = subRL;
        if (subRL)
        {
            subRL->_parent = parent;
        }
        subR->_left = parent;
        parent->_parent = subR;
        if (_root == parent)
        {
            _root = subR;
            subR->_parent = NULL;
        }
        else
        {
            //这里还需判断parent是在ppNode的左子树还是右子树
            if (parent == ppNode->_left)
            {
                ppNode->_left = subR;
                subR->_parent = ppNode;
            }
            else
            {
                ppNode->_right = subR;
                subR->_parent = ppNode;
            }
            subR->_bf = 0;
            parent->_bf = 0;
        }
    }

左右双旋: parent->_bf==-2 cur->_bf==1
AVL树(平衡搜索二叉树)

void Rotate_LR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        int bf = subLR->_bf;

        Rotate_L(subL);
        Rotate_R(parent);

        if (bf == -1)
        {
            subL->_bf = 0;
            parent->_bf = 1;
            subLR->_bf = 0;
        }
        else if (bf == 1)
        {
            subL->_bf = -1;
            parent->_bf = 0;
            subLR->_bf = 0;
        }
        else
        {
            subL->_bf = subLR->_bf = parent->_bf = 0;
        }
    }

右左双旋: parent->_bf==2 cur->_bf==-1
AVL树(平衡搜索二叉树)

void Rotate_RL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        int bf = subR->_bf;

        Rotate_R(subR);
        Rotate_L(parent);

        if (bf == 1)
        {
            subR->_bf = 0;
            subRL->_bf = 0;
            parent->_bf = -1;
        }
        else if (bf == -1)
        {
            subR->_bf = 1;
            parent->_bf = 0;
            subRL->_bf = 0;
        }
        else
        {
            subR->_bf = subRL->_bf = parent->_bf = 0;
        }
    }
相关标签: AVL