AVL树详解

桃扇骨 2022-06-01 00:51 141阅读 0赞

AVL树是最先发明的自平衡二叉查树，二叉查找树的性质如果不知道可以百度一下。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。其实性质还是比较简单的，看一张网上图大概就明白了：  
![这里写图片描述][SouthEast]  
话不多说，直接上重点。

### 一、AVL树的旋转 ###

AVL树在插入和删除接点的时候会破坏树的平衡，这时候就需要一些操作来恢复平衡。我们暂时不考虑是如何恢复平衡的，首先学习下单个接点的旋转，旋转无非就是几个节点之间的位置变换，操作步骤也是很简单的。

#### 1.左旋转 ####

![这里写图片描述][SouthEast 1]  
按照图中一步一步来，参考代码:

template<class T>
    void AVLTree<T>::leftRotate(TreeNode<T>* x)
    {
        if (!x) {
            return;
        }
    
        TreeNode<T>* parent = x->parent;
        TreeNode<T>* y = x->rightChild;
        if (!y) {
            return;
        }
        x->rightChild = y->leftChild;
        if (y->leftChild) {
            y->leftChild->parent = x;
        }
    
        if (!parent) {
            root = y;
        }
        else
        {
            if (parent->leftChild == x) {
                parent->leftChild = y;
            }
            else {
                parent->rightChild = y;
            }
        }
        y->parent = parent;
        y->leftChild = x;
        x->parent = y;
    }

#### 2.右旋转 ####

同理，其实操作也类似，我们不必考虑影响以外的其他节点:  
![这里写图片描述][SouthEast 2]

template<class T>
    void AVLTree<T>::rightRotate(TreeNode<T>* y)
    {
        if (!y) {
            return;
        }
    
        TreeNode<T>* x = y->leftChild;
        if (!x) {
            return;
        }
        y->leftChild = x->rightChild;
        if (x->rightChild) {
            x->rightChild->parent = y;
    
        }
    
        TreeNode<T>* parent = y->parent;
        x->parent = parent;
        if (!parent) {
            root = x;
        }
        else {
            if (parent->leftChild == y) {
                parent->leftChild = x;
            }
            else {
                parent->rightChild = x;
    
            }
        }
        y->parent = x;
        x->rightChild = y;
    }

### 二、AVL树的左右平衡恢复情况讨论 ###

平衡点恢复有的需要经过一次旋转，有的需要经过两次旋转，分各种情况讨论，明确节点的balance未平衡因子，也就是左子树的高度减去右子树的高度，因为插入或删除节点之前树是平衡的，所以就只有-1，0，1三种情况，导致不平衡的原因也就是balance的绝对值等于2。这里定义:  
RH(RIGHT\_HIGH)=-1;  
LH(LEFT\_HIGH)=1;  
EH(EQUAL\_HIGH)=0;

#### 1、左平衡 ####

情况分析：  
![这里写图片描述][SouthEast 3]  
其实情况也不太多，旋转搞清楚了这里就简单很多了。这里的回溯节点是删除的时候用到的，可以暂时不管。

template<class T>
    void AVLTree<T>::leftBlance(TreeNode<T>* t,bool traceBalance)
    {
        TreeNode<T>* tl = t->leftChild;
        if (traceBalance) {
            //回溯balance
            TreeNode<T>* tp = t->parent;
            TreeNode<T>* pre = t;
            while (tp) {
                if (tp->rightChild == pre) {
                    tp->balance++;
                }
                else {
                    tp->balance--;
                }
                if (tp->balance != EH) {
                    break;
                }
                pre = tp;
                tp = tp->parent;
            }
        }
    
        switch (tl->balance)
        {
            //添加到左树 回溯找到第一个不平衡的点t，t的左子树balance为LH就是添加到了左边
        case LH:
            rightRotate(t);
            tl->balance = EH;
            t->balance = EH;
            break;
        case RH:
            TreeNode<T>* tlr = tl->rightChild;
            switch (tlr->balance)
            {
            case LH:
                t->balance = RH;
                tl->balance = EH;
                tlr->balance = EH;
                break;
            case RH:
                t->balance = EH;
                tl->balance = LH;
                tlr->balance = EH;
                break;
            case EH:
                t->balance = EH;
                tl->balance = EH;
                tlr->balance = EH;
                break;
    
            }
    
            leftRotate(tl);
            rightRotate(t);
    
        }
    }

#### 2、右平衡 ####

![这里写图片描述][SouthEast 4]

template<class T>
    void AVLTree<T>::rightBlance(TreeNode<T>* t, bool traceBalance)
    {
        TreeNode<T>* tr = t->rightChild;
        if (traceBalance) {
            //回溯balance
            TreeNode<T>* tp = t->parent;
            TreeNode<T>* pre = t;
            while (tp) {
                if (tp->rightChild == pre) {
                    tp->balance++;
                }
                else {
                    tp->balance--;
                }
                if (tp->balance != EH) {
                    break;
                }
                pre = tp;
                tp = tp->parent;
            }
        }
        switch (tr->balance) {
        case RH:
            leftRotate(t);
            t->balance = EH;
            tr->balance = EH;
            break;
        case LH:
            TreeNode<T>* trl = tr->leftChild;
            switch (trl->balance) {
            case RH:
                t->balance = LH;
                tr->balance = EH;
                trl->balance = EH;
                break;
            case LH:
                t->balance = EH;
                tr->balance = RH;
                trl->balance = EH;
                break;
            case EH:
                t->balance = EH;
                tr->balance = EH;
                trl->balance = EH;
                break;
            }
            rightRotate(tr);
            leftRotate(t);
            break;
    
        }
    
    }

### 三、AVL树的插入节点 ###

理解了前面的，插入节点就很简单了。首先循环找到插入位置，然后修改平衡因子，回溯寻找最小不平衡的节点，进行平衡恢复就行了。这里插入节点也有可能不会破坏平衡，比如插入一个节点后父节点就刚好EH，这种情况就是没有破坏平衡的，所以直接就不必在回溯了。

template<class T>
    inline bool AVLTree<T>::add(T e)
    {
        if (!root) {
            root = new TreeNode<T>(e);
            size++;
            root->balance = 0;
            return true;
        }
        else
        {
            TreeNode<T>* temp = root;
            TreeNode<T>* parent=NULL;
            while (temp)
            {
                parent = temp;
                if (e > temp->element) {
                    temp = temp->rightChild;
                }
                else if(e<temp->element) {
                    temp = temp->leftChild;
                }
                else {
                    return false;
                }
            }
            TreeNode<T>* child = new TreeNode<T>(e);
            if (e > parent->element) {
                parent->rightChild = child;
            }
            else
            {
                parent->leftChild = child;
            }
            child->parent = parent;
            size++;
            while (parent != NULL)
            {
                if (e > parent->element) {
                    parent->balance--;
                }
                else
                {
                    parent->balance++;
                }
                if (parent->balance == EH) {
                    break;
                }
                if (abs(parent->balance) == 2) {
                    fixAfterInsert(parent);
                    break;
                }
                else {
                    parent = parent->parent;
                }
    
            }
            return true;
    
    
        }
    
    }

template<class T>
    inline void AVLTree<T>::fixAfterInsert(TreeNode<T>* t)
    {
        switch (t->balance)
        {
        case 2:
            leftBlance(t,false);
            break;
        case -2:
            rightBlance(t,false);
            break;
    
        }
    }

### 三、AVL树的删除节点 ###

删除节点和插入节点其实类似，主要是删除后通过一开始balance变化的节点进行回溯，找到不平衡的就直接按照规则旋转即可。这里有个问题，就是通过左平衡或者右平衡，会影响父节点的平衡因子，这里也需要分情况讨论。、

template<class T>
      void AVLTree<T>::remove(TreeNode<T>* node)
     {
    
         if (!node) {
             return ;
         }
         else {
             TreeNode<T>* parent = node->parent;
             //1、没有孩子
             if (!node->leftChild && !node->rightChild) {
                 if (!node->parent) {
                     root = NULL;
                 }
                 if (node == parent->leftChild) {
                     parent->leftChild = NULL;
                 }
                 else
                 {
                     parent->rightChild = NULL;
                 }
                 recall(node->parent, node->element);
                 node->parent = NULL;
                 delete node;
    
             }
             else if (node->leftChild && !node->rightChild) {
                 //只有左孩子
                 if (!parent) {
                     root = node->leftChild;
                     node->leftChild->parent = NULL;
                 }
                 else
                 {
                     if (parent->leftChild == node) {
                         parent->leftChild = node->leftChild;
                     }
                     else {
                         parent->rightChild = node->leftChild;
                     }
                     node->leftChild->parent = parent;
                 }
                 recall(node->parent, node->element);
                 delete node;
    
             }
             else if (!node->leftChild && node->rightChild) {
                 //只有右孩子
                 if (!parent) {
                     root = node->rightChild;
                     node->rightChild->parent = NULL;
                 }
                 else {
                     if (parent->leftChild == node) {
                         parent->leftChild = node->rightChild;
                     }
                     else {
                         parent->rightChild = node->rightChild;
                     }
                     node->rightChild->parent = parent;
                 }
                 recall(node->parent, node->element);
                 delete node;
             }
             else if (node->leftChild&&node->rightChild) {
                 //左孩子和右孩子
                 //这里需要把右孩子的最左的节点提到被删除的节点出，通过各种情形判断来调整
                 //左平衡或者右平衡都是将树的高度减少了1，所以需要向上回溯判断
                 TreeNode<T> * leftChild = getMinLeftNode(node->rightChild);
                 TreeNode<T>* leftNodeP = leftChild->parent;
                 if (leftChild != node->rightChild) {
                     leftNodeP->leftChild = leftChild->rightChild;
                     leftChild->rightChild = node->rightChild;
                 }
                 leftChild->leftChild = node->leftChild;
                 node->rightChild->parent=leftChild;
                 node->leftChild->parent = leftChild;
                 if (!parent) {
                     root = leftChild;
                 }
                 else {
                     if (parent->leftChild == node) {
                         parent->leftChild = leftChild;
                     }
                     else {
                         parent->rightChild = leftChild;
                     }
                     leftChild->parent = parent;
                     leftChild->balance = node->balance;
                 }
                 if (leftChild == node->rightChild) {
                     leftNodeP = leftChild;
                 }
    
                 while (leftNodeP != NULL)
                 {
                     if (leftChild->element > leftNodeP->element) {
                         leftNodeP->balance++;
    
                     }
                     else if (leftChild->element < leftNodeP->element) {
                         leftNodeP->balance--;
                     }
                     else {
                         leftNodeP->balance++;
                     }
    
    
                     if (abs(leftNodeP->balance) == 2) {
                         switch (leftNodeP->balance)
                         {
                         case 2:
                             leftBlance(leftNodeP, true);
                             break;
                         case -2:
                             rightBlance(leftNodeP, true);
                             break;
    
                         }
                         break;
                     }
                     if (leftNodeP->balance != EH) {
                         break;
                     }
                        leftNodeP = leftNodeP->parent;
    
    
                 }
    
             }
         }
    
    template<class T>
    inline void AVLTree<T>::recall(TreeNode<T> * &parent, T &e)
    {
    
        while (parent != NULL)
        {
    
                if (e > parent->element) {
                    parent->balance++;
                }
                else
                {
                    parent->balance--;
                }
    
    
            if (abs(parent->balance) == 2) {
                fixAfterInsert(parent);
                break;
            }
    
            if (parent->balance != EH) {
                break;
            }
    
            parent = parent->parent;
    
    
        }
    }

### 完整代码 ###

#### AVLTree.h ####

#pragma once
    #include "TreeNode.h"
    #include <math.h>
    #include <iostream>
    #include <queue>
    template <class T>
    class AVLTree
    {
    private:
        TreeNode<T> * root;
        int size = 0;
        //平衡因子 左树比又树高
        static const int LH = 1;
        //右树比左树高
        static const int RH = -1;
        //平衡
        static const int EH = 0;
    public:
        AVLTree();
        ~AVLTree();
        bool add(T e);
        void leftRotate(TreeNode<T>* x);
        void rightRotate(TreeNode<T>* y);
        void rightBlance(TreeNode<T>* t,bool traceBalance);
        void leftBlance(TreeNode<T>* t,  bool traceBalanc);
        void fixAfterInsert(TreeNode<T>* t);
        void levelDisplay();
        void release(TreeNode<T>* root);
        int getBalance(TreeNode<T>* t);
        void remove(TreeNode<T>* node);
        void recall(TreeNode<T> * &parent, T &e);
        TreeNode<T>* getMinLeftNode(TreeNode<T>* node);
        TreeNode<T>* search(T e);
        TreeNode<T>* getRoot();
    
    
    };
    
    template<class T>
     AVLTree<T>::AVLTree()
    {
    
    
    
    }
    
    template<class T>
    inline AVLTree<T>::~AVLTree()
    {
        release(root);
    
    }
    
    
    template<class T>
    inline bool AVLTree<T>::add(T e)
    {
        if (!root) {
            root = new TreeNode<T>(e);
            size++;
            root->balance = 0;
            return true;
        }
        else
        {
            TreeNode<T>* temp = root;
            TreeNode<T>* parent=NULL;
            while (temp)
            {
                parent = temp;
                if (e > temp->element) {
                    temp = temp->rightChild;
                }
                else if(e<temp->element) {
                    temp = temp->leftChild;
                }
                else {
                    return false;
                }
            }
            TreeNode<T>* child = new TreeNode<T>(e);
            if (e > parent->element) {
                parent->rightChild = child;
            }
            else
            {
                parent->leftChild = child;
            }
            child->parent = parent;
            size++;
            while (parent != NULL)
            {
                if (e > parent->element) {
                    parent->balance--;
                }
                else
                {
                    parent->balance++;
                }
                if (parent->balance == EH) {
                    break;
                }
                if (abs(parent->balance) == 2) {
                    fixAfterInsert(parent);
                    break;
                }
                else {
                    parent = parent->parent;
                }
    
            }
            return true;
    
    
        }
    
    }
    
    template<class T>
    inline void AVLTree<T>::recall(TreeNode<T> * &parent, T &e)
    {
    
        while (parent != NULL)
        {
    
                if (e > parent->element) {
                    parent->balance++;
                }
                else
                {
                    parent->balance--;
                }
    
    
            if (abs(parent->balance) == 2) {
                fixAfterInsert(parent);
                break;
            }
    
            if (parent->balance != EH) {
                break;
            }
    
            parent = parent->parent;
    
    
        }
    }
    
    template<class T>
     TreeNode<T>* AVLTree<T>::getMinLeftNode(TreeNode<T> * node)
    {
        TreeNode<T>* curRoot;
        if (!node) {
            return  NULL;
        }
        else {
            curRoot = node;
            while (curRoot->leftChild)
            {
                curRoot = curRoot->leftChild;
            }
        }
        return curRoot;
    }
    
     template<class T>
     inline TreeNode<T>* AVLTree<T>::search(T data)
     {
         if (!root) return NULL;
         TreeNode<T>* temp = root;
         while (temp)
         {
             if (data > temp->element) {
                 temp = temp->rightChild;
             }
             else if (data < temp->element) {
                 temp = temp->leftChild;
             }
             else
             {
                 return temp;
             }
         }
    
         return NULL;
    
     }
    
     template<class T>
     inline TreeNode<T>* AVLTree<T>::getRoot()
     {
         return root;
     }
    
    template<class T>
    void AVLTree<T>::leftRotate(TreeNode<T>* x)
    {
        if (!x) {
            return;
        }
    
        TreeNode<T>* parent = x->parent;
        TreeNode<T>* y = x->rightChild;
        if (!y) {
            return;
        }
        x->rightChild = y->leftChild;
        if (y->leftChild) {
            y->leftChild->parent = x;
        }
    
        if (!parent) {
            root = y;
        }
        else
        {
            if (parent->leftChild == x) {
                parent->leftChild = y;
            }
            else {
                parent->rightChild = y;
            }
        }
        y->parent = parent;
        y->leftChild = x;
        x->parent = y;
    }
    
    template<class T>
    void AVLTree<T>::rightRotate(TreeNode<T>* y)
    {
        if (!y) {
            return;
        }
    
        TreeNode<T>* x = y->leftChild;
        if (!x) {
            return;
        }
        y->leftChild = x->rightChild;
        if (x->rightChild) {
            x->rightChild->parent = y;
    
        }
    
        TreeNode<T>* parent = y->parent;
        x->parent = parent;
        if (!parent) {
            root = x;
        }
        else {
            if (parent->leftChild == y) {
                parent->leftChild = x;
            }
            else {
                parent->rightChild = x;
    
            }
        }
        y->parent = x;
        x->rightChild = y;
    
    }
    
    template<class T>
    void AVLTree<T>::rightBlance(TreeNode<T>* t, bool traceBalance)
    {
        TreeNode<T>* tr = t->rightChild;
        if (traceBalance) {
            //回溯balance
            TreeNode<T>* tp = t->parent;
            TreeNode<T>* pre = t;
            while (tp) {
                if (tp->rightChild == pre) {
                    tp->balance++;
                }
                else {
                    tp->balance--;
                }
                if (tp->balance != EH) {
                    break;
                }
                pre = tp;
                tp = tp->parent;
            }
        }
        switch (tr->balance) {
        case RH:
            leftRotate(t);
            t->balance = EH;
            tr->balance = EH;
            break;
        case LH:
            TreeNode<T>* trl = tr->leftChild;
            switch (trl->balance) {
            case RH:
                t->balance = LH;
                tr->balance = EH;
                trl->balance = EH;
                break;
            case LH:
                t->balance = EH;
                tr->balance = RH;
                trl->balance = EH;
                break;
            case EH:
                t->balance = EH;
                tr->balance = EH;
                trl->balance = EH;
                break;
            }
            rightRotate(tr);
            leftRotate(t);
            break;
    
        }
    
    }
    
    template<class T>
    void AVLTree<T>::leftBlance(TreeNode<T>* t,bool traceBalance)
    {
        TreeNode<T>* tl = t->leftChild;
        if (traceBalance) {
            //回溯balance
            TreeNode<T>* tp = t->parent;
            TreeNode<T>* pre = t;
            while (tp) {
                if (tp->rightChild == pre) {
                    tp->balance++;
                }
                else {
                    tp->balance--;
                }
                if (tp->balance != EH) {
                    break;
                }
                pre = tp;
                tp = tp->parent;
            }
        }
    
        switch (tl->balance)
        {
            //添加到左树 回溯找到第一个不平衡的点t，t的左子树balance为LH就是添加到了左边
        case LH:
            rightRotate(t);
            tl->balance = EH;
            t->balance = EH;
            break;
        case RH:
            TreeNode<T>* tlr = tl->rightChild;
            switch (tlr->balance)
            {
            case LH:
                t->balance = RH;
                tl->balance = EH;
                tlr->balance = EH;
                break;
            case RH:
                t->balance = EH;
                tl->balance = LH;
                tlr->balance = EH;
                break;
            case EH:
                t->balance = EH;
                tl->balance = EH;
                tlr->balance = EH;
                break;
    
            }
    
            leftRotate(tl);
            rightRotate(t);
    
        }
    }
    
    template<class T>
    inline void AVLTree<T>::fixAfterInsert(TreeNode<T>* t)
    {
        switch (t->balance)
        {
        case 2:
            leftBlance(t,false);
            break;
        case -2:
            rightBlance(t,false);
            break;
    
        }
    }
    
    template<class T>
     void AVLTree<T>::levelDisplay()
    {
         if (root) {
            TreeNode<T>* temp = root;
            queue<TreeNode<T>*> q;
            q.push(temp);
            while (!q.empty())
            {
                TreeNode<T>* t = q.front();
                q.pop();
                cout << t->element << ",";
                if (t->leftChild) q.push(t->leftChild);
                if (t->rightChild) q.push(t->rightChild);
            }
    
         }
    }
    
    
    template<class T>
     void AVLTree<T>::release(TreeNode<T>* root)
    {
         if (root) {
             release(root->leftChild);
             release(root->rightChild);
             delete root;
         }
    }
    
     template<class T>
     inline int AVLTree<T>::getBalance(TreeNode<T>* t)
     {
         if (!t) return 0;
         if (!t->leftChild && !t->rightChild)
             return 0;
         TreeNode<T>* temp = t;
         int balance = 0;
         while (temp)
         {
             temp = temp->leftChild;
             balance++;
         }
         temp = t;
         while (temp)
         {
             temp = temp->rightChild;
             balance--;
         }
    
         return balance;
     }
    
     template<class T>
      void AVLTree<T>::remove(TreeNode<T>* node)
     {
    
         if (!node) {
             return ;
         }
         else {
             TreeNode<T>* parent = node->parent;
             //1、没有孩子
             if (!node->leftChild && !node->rightChild) {
                 if (!node->parent) {
                     root = NULL;
                 }
                 if (node == parent->leftChild) {
                     parent->leftChild = NULL;
                 }
                 else
                 {
                     parent->rightChild = NULL;
                 }
                 recall(node->parent, node->element);
                 node->parent = NULL;
                 delete node;
    
             }
             else if (node->leftChild && !node->rightChild) {
                 //只有左孩子
                 if (!parent) {
                     root = node->leftChild;
                     node->leftChild->parent = NULL;
                 }
                 else
                 {
                     if (parent->leftChild == node) {
                         parent->leftChild = node->leftChild;
                     }
                     else {
                         parent->rightChild = node->leftChild;
                     }
                     node->leftChild->parent = parent;
                 }
                 recall(node->parent, node->element);
                 delete node;
    
             }
             else if (!node->leftChild && node->rightChild) {
                 if (!parent) {
                     root = node->rightChild;
                     node->rightChild->parent = NULL;
                 }
                 else {
                     if (parent->leftChild == node) {
                         parent->leftChild = node->rightChild;
                     }
                     else {
                         parent->rightChild = node->rightChild;
                     }
                     node->rightChild->parent = parent;
    
    
                 }
                 recall(node->parent, node->element);
                 delete node;
             }
             else if (node->leftChild&&node->rightChild) {
                 TreeNode<T> * leftChild = getMinLeftNode(node->rightChild);
                 TreeNode<T>* leftNodeP = leftChild->parent;
                 if (leftChild != node->rightChild) {
                     leftNodeP->leftChild = leftChild->rightChild;
                     leftChild->rightChild = node->rightChild;
                 }
                 leftChild->leftChild = node->leftChild;
                 node->rightChild->parent=leftChild;
                 node->leftChild->parent = leftChild;
                 if (!parent) {
                     root = leftChild;
                 }
                 else {
                     if (parent->leftChild == node) {
                         parent->leftChild = leftChild;
                     }
                     else {
                         parent->rightChild = leftChild;
                     }
                     leftChild->parent = parent;
                     leftChild->balance = node->balance;
                 }
                 if (leftChild == node->rightChild) {
                     leftNodeP = leftChild;
                 }
    
                 while (leftNodeP != NULL)
                 {
                     if (leftChild->element > leftNodeP->element) {
                         leftNodeP->balance++;
    
                     }
                     else if (leftChild->element < leftNodeP->element) {
                         leftNodeP->balance--;
                     }
                     else {
                         leftNodeP->balance++;
                     }
    
    
                     if (abs(leftNodeP->balance) == 2) {
                         switch (leftNodeP->balance)
                         {
                         case 2:
                             leftBlance(leftNodeP, true);
                             break;
                         case -2:
                             rightBlance(leftNodeP, true);
                             break;
    
                         }
                         break;
                     }
                     if (leftNodeP->balance != EH) {
                         break;
                     }
                        leftNodeP = leftNodeP->parent;
    
    
                 }
    
    
             }
         }
     }

#### 测试代码 ####

main.cpp

#include "stdafx.h"
    #include "Node.h"
    #include <iostream>
    #include <stack>
    #include "BinarySearchTree.h"
    #include "AVLTree.h"
    using namespace std;
    
    
    
    
    
    
    
    #define ARRAY_LENTH(a) sizeof(a)/sizeof(a[0])
    struct Trunk
    {
        Trunk *prev;
        string str;
    
        Trunk(Trunk *prev, string str)
        {
            this->prev = prev;
            this->str = str;
        }
    };
    // Helper function to print branches of the binary tree
    void showTrunks(Trunk *p)
    {
        if (p == nullptr)
            return;
    
        showTrunks(p->prev);
    
        cout << p->str;
    }
    
    
    // Recursive function to print binary tree
    // It uses inorder traversal
    void printTree(TreeNode<int> *root, Trunk *prev, bool isLeft)
    {
        if (root == nullptr)
            return;
    
        string prev_str = "    ";
        Trunk *trunk = new Trunk(prev, prev_str);
    
        printTree(root->rightChild, trunk, true);
    
        if (!prev)
            trunk->str = "--- ";
        else if (isLeft)
        {
            trunk->str = ".---";
            prev_str = "   |";
        }
        else
        {
            trunk->str = "`---";
            prev->str = prev_str;
        }
    
        showTrunks(trunk);
        cout<< root->element <<"("<<root->balance<<")"<< endl;
    
        if (prev)
            prev->str = prev_str;
        trunk->str = "   |";
    
        printTree(root->leftChild, trunk, false);
    }
    
    
    
    int main() {
    
    
        AVLTree<int> AVLTree;
        int nums[]= { 5, 8, 2, 0, 1,-2 ,7,10,15,3,4,6,20,21};
        for (int i = 0; i < ARRAY_LENTH(nums); i++) {
            AVLTree.add(nums[i]);
        }
        printTree(AVLTree.getRoot(), nullptr, false);
    
        TreeNode<int>* t = AVLTree.search(15);
    
        cout << endl<<"-----------------------------" << endl;
    
        AVLTree.remove(t);
        printTree(AVLTree.getRoot(), nullptr, false);
        cout << endl << "-----------------------------" << endl;
    
    
    
        TreeNode<int>* t1 = AVLTree.search(8);
        AVLTree.remove(t1);
        printTree(AVLTree.getRoot(), nullptr, false);
        cout << endl << "-----------------------------" << endl;
    
    
    
        TreeNode<int>* t2 = AVLTree.search(1);
        AVLTree.remove(t2);
        printTree(AVLTree.getRoot(), nullptr, false);
        cout << endl << "-----------------------------" << endl;
    
    
    
        TreeNode<int>* t3 = AVLTree.search(5);
        AVLTree.remove(t3);
        printTree(AVLTree.getRoot(), nullptr, false);
    
    
        system("pause");
    
    }

[SouthEast]: /images/20220601/bbd2c60d7fe64338ac7c6ea41d8b3165.png
[SouthEast 1]: /images/20220601/da1b28c7d00d4821a4d0d5a8f0cf0745.png
[SouthEast 2]: /images/20220601/1e8e67b125614830924bf8c4242c48c8.png
[SouthEast 3]: /images/20220601/9c316b40e62a4cb88187c7b540c5848c.png
[SouthEast 4]: /images/20220601/31a6ef258d1f4a858089358cbf7b9db9.png