高度平衡二叉搜索树（AVL）的插入与删除

青旅半醒 2022-06-17 06:46 168阅读 0赞

## avl树的插入 ##

平衡二叉树：要么是空树，要么是左右子树的高度差不超过一，并且左右子树又分别为平衡二叉树。  
而AVL树插入就需要对二叉树的平衡性做调整，使之即平衡又是有序的，这里就会需要左旋转、右旋转、和左右双旋转。并且调节相应的平衡因子，平衡因子等于右子树高度减去左子树高度。  
**AVLTreeNOde:**

struct AVLNode
        {
            AVLNode *leftchild;
            AVLNode*rightchild;
            AVLNode*parent;
            int balance;
            KeyType key;
        };

**左单旋：**

static void RotateLeft(AVLNode*&p)
        {
            if (p == NULL)
                return;
            AVLNode*newroot = p->rightchild;
            newroot->parent = p->parent;
            p->rightchild = newroot->leftchild;
            if (newroot->leftchild != NULL)
            {
    
                newroot->leftchild->parent = p;
            }
            newroot->leftchild = p;
            p->parent = newroot;
            p = newroot;
    
        }

右单旋：

static void RotateRight(AVLNode*&p)
        {
            if (p == NULL)
                return;
            AVLNode*newroot = p->leftchild;
            newroot->parent = p->parent;
            p->leftchild = newroot->rightchild;
            if (newroot->rightchild != NULL)
            {
                newroot->rightchild->parent = p;
            }
            newroot->rightchild = p;
            p->parent = newroot;
            p = newroot;
        }

当树不平衡时就有好的多种情况，根据每种情况将平衡后的平衡因子情况做记录就会发现规律，这里又分为左平衡和右平衡两大类：  
**左平衡：**

static void LeftBalance(AVLNode *&p)
        {
            if (p == NULL)
                return;
            AVLNode*right = p->rightchild;
            AVLNode*left = NULL;
            switch (right->balance)
            {
            case 0:
                if ((GetDepth(p->rightchild) - GetDepth(p->leftchild)) <= 1)
                    cout << "balanced" << endl; 
                else
                {
                    right->balance = -1; p->balance = 1;
                    RotateLeft(p);
                }
                break;
            case 1:
                right->balance = p->balance = 0;
                RotateLeft(p);
                break;
            case -1:
                left = right->leftchild;
                switch (left->balance)
                {
                case 0:  right->balance  = left->balance = p->balance = 0; break;
                case 1:  left->balance = right->balance = 0; p->balance = -1; break;
                case -1: left->balance = p->balance = 0; right->balance = 1; break;
                }
    
                RotateRight(p->rightchild); 
                RotateLeft(p);
                break;
            default:
                cout << "error" << endl;
                break;
            }
        }

**右平衡：**

static void RightBalance(AVLNode*&p)
        {
            if (p == NULL)
                return;
            AVLNode*left = p->leftchild;
            AVLNode*right = NULL;
            switch (left->balance)
            {
            case 0:
                if((GetDepth(p->rightchild)-GetDepth(p->leftchild))>=-1)
                    cout << "balanced" << endl;
                else
                {
                    p->balance = -1; left->balance = 1;
                    RotateRight(p);
                }
                break;
            case 1:
                right = left->rightchild;
                switch (right->balance)
                {
                case 0:right->balance = left->balance = p->balance =  0; break;
                case 1:left->balance = -1; p->balance = right->balance = 0; break;
                case -1:p->balance = 1; right->balance = left->balance = 0; break;
                }
                RotateLeft(p->leftchild);
                RotateRight(p);
                break;
            case -1:
                p->balance = left->balance = 0;
                RotateRight(p);
                break;
            default:
                cout << "error" << endl;
                break;
            }
        }

插入就是对每插入一个元素就改平衡因子，不平衡就调整：  
**插入代码：**

static bool Insert(AVLNode*&root, KeyType k, AVLNode*p)
        {
            bool res = false;
            if (root == NULL)
            {
                AVLNode*node = BuyNode();
                node->key = k;
                node->parent = p;
                root = node;
                res=true;
            }
            else if (root->key > k)
            {
                res=Insert(root->leftchild, k, root);
                if (res == true)
                {
                    switch (root->balance)
                    {
                    case 0:root->balance = -1; break;
                    case 1:root->balance = 0; break;
                    case -1:
                        RightBalance(root);
                        break;
                    default:
                        cout << "error" << endl;
                        break;
                    }
                }
            }
            else if (root->key < k)
            {
                res= Insert(root->rightchild, k, root);
                if (res == true)
                {
                    switch (root->balance)
                    {
                    case 0:root->balance = 1; break;
                    case 1:
                        LeftBalance(root); break;
                    case -1:root->balance = 0; break;
                    default:
                        cout << "error" << endl;
                        break;
                    }
                }
            }
            return res;
        }

删除与插入很相似代码如下：

static bool ReMove_ex(AVLNode* &root, KeyType e)
        {
            bool res = false;
            if (root == NULL)
                res= false;
            else if (root->key > e)
            {
                res = ReMove_ex(root->leftchild, e);
    
                if (res == true)
                {
                    /*switch (root->balance)
                    {
                    case 0:root->balance = 1; break;
                    case 1:LeftBalance(root); break;
                    case -1:root->balance=0; break;
                    }*/
                    int balance = GetDepth(root->rightchild) - GetDepth(root->leftchild);
                    if (balance >= 2)
                    {
                        LeftBalance(root);
                    }
                    else
                    {
                        root->balance = balance;
                    }
                }
    
            }
            else if (root->key < e)
            {
                res = ReMove_ex(root->rightchild, e);
                if (res == true)
                {
                    int balance = GetDepth(root->rightchild) - GetDepth(root->leftchild);
                    if (balance <= -2)
                    {
                        RightBalance(root);
                    }
                    else
                    {
                        root->balance = balance;
                    }
                }
            }
            else
            {
                if (root->leftchild != NULL&&root->rightchild != NULL)
                {
                    AVLNode*child = Next(root);
                    root->key = child->key;
                    res=ReMove_ex(root->rightchild, child->key);
                }
                else//必须要加
                {
                    AVLNode*p = root->leftchild == NULL ? root->rightchild : root->leftchild;
                    if (p != NULL)
                        p->parent = root->parent;
                    free(root);
                    root = p;
                    //(*size)--;
                    res = true;
                }
            }
            return res;
        }