AVL 树

avltree.h

#pragma once
#include
#include
#include
#include
using namespace std;

template
struct AVLTreeNode
{
    AVLTreeNode(T value)
    :key(value), lchild(nullptr), rchild(nullptr), height(0), bf(0){}
 
    T key;
    int height;
    int bf;   // the height of rchild - the height of lchild
    AVLTreeNode* lchild;
    AVLTreeNode* rchild;
};

template
class AVLTree
{
public:
    AVLTree(); 
    ~AVLTree();

    void Destroy();
 
    void Insert(T key);
    void Remove(T key);
    void LayerOrder();
    int Height();
 
private:
    AVLTreeNode* root;
 
private:
    void destroy(AVLTreeNode* &pNode);
    int Height(AVLTreeNode* pNode);
 
    bool insert(AVLTreeNode* &pNode, T key);       
    bool remove(AVLTreeNode* &pNode, T key);
 
    void RotateL(AVLTreeNode* &pNode);
    void RotateR(AVLTreeNode* &pNode);
    void RotateLR(AVLTreeNode* &pNode);
    void RotateRL(AVLTreeNode* &pNode);
};

template
AVLTree::AVLTree()
    :root(nullptr)
{
}

template
AVLTree::~AVLTree()
{
    destroy(root);
}

template
void AVLTree::Destroy()
{
    destroy(root);
}

template
void AVLTree::destroy(AVLTreeNode* &pNode)
{
    if (pNode != NULL)
    {
        destroy(pNode->lchild);
        destroy(pNode->rchild);
        delete pNode;
        pNode = NULL;
    }
}

template
void AVLTree::Insert(T key)
{
    insert(root, key);
}

/**********
AVL树插入：
    再向一颗本来是高度平衡的AVL树中插入一个新结点,如果树中的某个结点的平衡因子的
绝对值|bf|>1,则出现了不平衡，需要做平衡化处理。

    设新插入的结点为p, 从结点p到根结点的路径上,每个结点为根的子树的高度都可能增加1,
因此在每执行一次二叉树的插入运算后,都需要从新插入的结点p开始,沿该结点的插入路径向
根结点的方向回溯,修改各结点的平衡因子,调整子树的高度,恢复被破坏的平衡性质。

    新结点p的平衡因子为0。现在考察它的父结点parent,若p是parent的右子树，
则parent的平衡因子增加1，否则parent的平衡因子减少1,按照修改后的parent
的平衡因子值分三种情况
    (1) 结点parent的平衡因子为0，说明刚才试在parent的较矮的子树上插入
了新结点，结点parent处平衡，且高度没有增减，此时从parent到根的路径上的
各结点为根的子树高度不变，从而各个结点的平衡因子不变，可以结束重新平衡
化调整，返回主程序。
    (2) 结点parent的平衡因子绝对值为1，说明插入前的平衡因子为0，插入
新结点后，以parent为根的子树没有失去平衡，不需要平衡化旋转，但该子树
的高度增加，还需要从结点parent向根的方向回溯，继续考察结点parent的
父结点的平衡状态。
    (3) 结点parent的平衡因子绝对值为2，说明新结点在较高的子树上插入，
造成了不平衡，需要做平衡化旋转，分二种情况
       3.1 若结点parent的bf为2， 说明右子树高，结合其右子女q的bf分别处理：
           3.1.1  若q的bf为1，执行左单旋转
           3.1.2  若q的bf为-1，执行先右后左双旋转
       3.2 若结点parent的bf为-2，说明左子树高，结合其左子女q的bf分别处理：
           3.2.1  若q的bf为-1，执行右单旋转
           3.2.2  若q的bf为1，执行先左后右双旋转
*********/

template
bool AVLTree::insert(AVLTreeNode* &pNode, T key)
{
     AVLTreeNode* p = pNode;
     // the inserted node's parent
     AVLTreeNode* parent = nullptr;
     stack*> st;
     while (p != nullptr)
     {
         if (key == p->key)
             return false;
         parent = p;
         st.push(parent);
         if (key < p->key)
             p = p->lchild;
         else
             p = p->rchild;
     }

     p = new AVLTreeNode(key);
     // insert the root node
     if (nullptr == parent)
     {
         pNode = p;
         return true;
     }

     if (key < parent->key)
         parent->lchild = p;
     else
         parent->rchild = p;

     // adjust bf
     while (!st.empty())
     {
         parent = st.top();
         st.pop();
         if (parent->lchild == p)
             parent->bf--;
         else
             parent->bf++;

         if (0 == parent->bf)
             break;
         if (1 == parent->bf || -1 == parent->bf)
             p = parent;
         else  // bf is 2 or -2, need rotate the balance
         {
             int flag = (parent->bf < 0) ? -1 : 1;
             if (p->bf == flag) // straight line, single rotate
             {
                 if (-1 == flag)     // "/"
                     RotateR(parent);
                 else                // "\"
                     RotateL(parent);
             }
             else   //parent is the uppermost node, whose bf is |2|
             {
                 if (1 == flag)    // ">", the middle node is axis, from the buttom up, so first rotate R, the rotate L 
                     RotateRL(parent);
                 else              // "<", the middle node is axis, from the buttom up, so first rotate L, the rotate R
                     RotateLR(parent);
             }
             break;
         }
     }

     if (st.empty())
         pNode = parent;
     else
     {
         AVLTreeNode* q = st.top();
         if (q->key > parent->key)
             q->lchild = parent;
         else
             q->rchild = parent;
     }

     return true;
}

template
void AVLTree::RotateL(AVLTreeNode* &pNode)
{
    AVLTreeNode* pSubL = pNode;
    pNode = pSubL->rchild;
    pSubL->rchild = pNode->lchild;
    pNode->lchild = pSubL;
    pNode->bf = pSubL->bf = 0;
}

template
void AVLTree::RotateR(AVLTreeNode* &pNode)
{
    AVLTreeNode* pSubR = pNode;
    pNode = pSubR->lchild;
    pSubR->lchild = pNode->rchild;
    pNode->rchild = pSubR;
    pNode->bf = pSubR->bf = 0;
}

// 以40为原始pNode做RotateLR

template
void AVLTree::RotateLR(AVLTreeNode* &pNode)
{
    // specify root, L and R
    AVLTreeNode* pSubL = pNode->lchild;
    AVLTreeNode* pSubR = pNode;
    pNode = pSubL->rchild;

    // create the left link
    pSubL->rchild = pNode->lchild;
    pNode->lchild = pSubL;
    if (pNode->bf <= 0)
        pSubL->bf = 0;
    else
        pSubL->bf = -1;

    // create the right link
    pSubR->lchild = pNode->rchild;
    pNode->rchild = pSubR;
    if (-1 == pNode->bf)
        pSubR->bf = 1;
    else
        pSubR->bf = 0;
    pNode->bf = 0;
}

// 以50为原始pNode做RotateRL

template
void AVLTree::RotateRL(AVLTreeNode* &pNode)
{
    // specify root, L and R
    AVLTreeNode* pSubL = pNode;
    AVLTreeNode* pSubR = pNode->rchild;
    pNode = pSubR->lchild;

    // create the right link
    pSubR->lchild = pNode->rchild;
    pNode->rchild = pSubR;
    if (pNode->bf >= 0)
        pSubR->bf = 0;
    else
        pSubR->bf = 1;

    // create the left link
    pSubL->rchild = pNode->lchild;
    pNode->lchild = pSubL;
    if (1 == pNode->bf)
        pSubL->bf = -1;
    else
        pSubL->bf = 0;
    pNode->bf = 0;
}

/*************
AVL树的删除
若删除结点后破坏了AVL树的平衡，则需要进行平衡旋转。
       1.如果被删除节点p有两个子女节点，首先，搜素p在中序下的直接前驱q(或者直接后继)，
         再把节点q的内容传送给节点p，问题转移到删除结点q，把结点q当做被删除节点p，
         它是只有一个子女的节点。
        2.如果被删除结点p最多只有一个子女q，可以简单的把p的父结点parent中原来
          指向的指针改指到q，如果节点p没有子女，p父结点parent的相应指针为NULL，
          然后将原来的结点parent为根的子树的高度减1,并沿 parent通向根的路径
          反向追踪高度的这一变化对路经上各结点的影响;

考察结点q的父结点 parent，若q是parent的左子女，
则parent的平衡因子增加1，否则减少1，根据修改后的parent的平衡因子，
按三种情况分别进行处理:
       (1)parent的平衡因子原来为0，在它的左子树或右子树被缩短后，
           则它的平衡因子改为1或-1，由于以parent为根的子树高度没有改变，
           从parent到根结点的路径上所有结点都不需要调整，
           此时可结束本次删除的重新平衡过程。
        (2)结点parent的平衡因子原不为0，且较高的子树被缩短，
            则p的平衡因子改为0，此时parent为根的子树平衡，但其高度减1， 
            为此需要继续考察结点parent的父结点的平衡状态。
        (3)结点parent的平衡因子原不为0，且较矮的子树被缩短，
            则在结点parent发生不平衡, 为此需要进行平衡化旋转来恢复平衡。
            令parent的较高的子树的根为q(该子树未被缩短)，根据q的平衡因子，有3种平衡化操作
             a.如果q的平衡因子为0，执行一个单旋转来恢复结点 parent的平衡
             b.如果q的平衡因子与parent的平衡因子正负号相同，
                则执行一个单旋转来恢复平衡，结点parent和q的平衡因子均改为0
             c.如果parent与q的平衡因子正负号相反，则执行一个双旋转来恢复平衡。
***********/

​​​​​​​

 

// 删除60后-> RotateR -> RotateLR
template
void AVLTree::Remove(T key)
{
    remove(root, key);
}

template
bool AVLTree::remove(AVLTreeNode* &pNode, T key)
{
    AVLTreeNode *ppr = NULL;
    AVLTreeNode *parent = NULL;
    AVLTreeNode *p = pNode;
    std::stack *> st;
    while (p != NULL)
    {
         if (p->key == key)
            break;
         parent = p;
         st.push(parent);
         if (key < p->key)
             p = p->lchild;
         else
             p = p->rchild;
    }
    // there has no node whose key is equal to key
    if (p == NULL)
       return false;

    AVLTreeNode *q = NULL;
    int f = 0;  // lchild is NULL, used for calculating bf of null child
    
    // case 1: the deleted node has two subtrees
    if (p->lchild != NULL && p->rchild != NULL)
    {
         parent = p;
         st.push(parent);
         // find precursor node of inorder
         q = p->lchild;
         while (q->rchild != NULL)
         {
              parent = q;
              st.push(parent);
              q = q->rchild;
         }
         p->key = q->key;
         p = q;
    }

    // case 2: the deleted node has one subtree at most 
    if (p->lchild != NULL)
       q = p->lchild;
    else
       q = p->rchild;

    // the root node has no parent
    if (parent == NULL)
        pNode = q;
    else
    {
        // the deleted node is the left subtree
        if (parent->lchild == p)
        {
             parent->lchild = q;
             f = 0; // Left subtree
        }
        else
        {
             parent->rchild = q;
             f = 1; // Right subtree
        }

        // adjust bf
        int link_flag = 0; // -1: left, 1: right, 0: no link
        while (!st.empty())
        {
             parent = st.top();
             st.pop();

             // when f is 1, q is one real subtree
             if (parent->rchild == q && f == 1)
                 parent->bf--;
             else
                 parent->bf++;

             if (!st.empty())
             {
                 ppr = st.top();
                 // ppr links the new subtree(after rotate)
                 link_flag = (ppr->lchild == parent) ? -1 : 1;
             }
             else
                 link_flag = 0;

             // before delete the node, the parent's bf is 0, delete this node will not affect the height of the tree
             if (parent->bf == -1 || parent->bf == 1)
                 break;

             if (parent->bf == 0)
                 q = parent;
             else   // |2|
             {
                  // q points the the taller substree
                  int flag = 0;
                  if (parent->bf < 0)
                  {
                       flag = -1;
                       q = parent->lchild;
                  }
                  else  // rchild is taller than lchild
                  {
                       flag = 1;
                       q = parent->rchild; 
                  }

                  // case a:
                  if (q->bf == 0) // singe rotate
                  {
                       if (flag == -1) // right rotate，lchild is higher than rchild
                       {
                           RotateR(parent);
                           parent->bf = 1;
                           parent->rchild->bf = -1;
                       }
                       else
                       {
                           RotateL(parent);
                           parent->bf = -1;
                           parent->lchild->bf = 1;
                       }
                       break;
                  }

                  if (q->bf == flag)    // straight line, single rotate
                  {
                       if (flag == -1)  // "/"
                          RotateR(parent);
                       else             // "\"
                          RotateL(parent);
                  }
                  else
                  {
                        if (flag == -1)   
                           RotateLR(parent); // "<"
                        else
                           RotateRL(parent); // ">"
                  }

                  if (link_flag == 1)
                      ppr->rchild = parent;
                  else if (link_flag == -1)
                      ppr->lchild = parent;

             }

        }
        if (st.empty())
           pNode = parent; 
    }

    delete p;
    p = NULL;
    
    return true; 
}

template
void AVLTree::LayerOrder()
{
    AVLTreeNode * p = root;
    std::queue *> qu;
    qu.push(p);
    while (!qu.empty())
    {
        std::vector vec;
        int num = qu.size();
        for (int i = 0; i < num; ++i)
        {
            p = qu.front();
            qu.pop();
            vec.push_back(p->key);
            if (p->lchild != NULL)
                qu.push(p->lchild);
            if (p->rchild != NULL)
                qu.push(p->rchild);
        }
        for (int j = 0; j < vec.size(); ++j)
            std::cout << vec[j] << " ";
        std::cout << std::endl;
    }

}

template
int AVLTree::Height()
{
    return Height(root)
}

template
int AVLTree::Height(AVLTreeNode* pNode)
{
    if (pNode != NULL)
    {
        int lHeight = Height(pNode->lchild) + 1;
        int rHeight = Height(pNode->rchild) + 1;
        return lHeight > rHeight ? lHeight ： rHeight;
    }

    return 0;
}

testavl.cpp

#include "avltree.h"

int main( )
{
    AVLTree avlTree;
    int lrArr[] = {50, 40 , 60, 10, 45, 70, 5, 30, 20};
    int rlArr[] = {30, 20, 50, 10, 40, 70, 60, 80, 65};
    int delArr1[] = {30, 20};
    int delArr2[] = {50, 40, 60, 10, 45, 70, 5, 30, 48};
    int delFArr3[] = {30, 20, 60, 10, 50, 70, 40, 65, 80};
    int delLFArr4[] = {50, 30, 60, 20, 40, 55, 70, 10, 25, 35, 45, 58, 65, 80, 5, 33, 38, 48, 75, 32};
    int i = 0;

    std::cout << "Insert elements need rotateLR" << std::endl;
    for (i = 0; i < sizeof(lrArr)/sizeof(int); ++i)
        avlTree.Insert(lrArr[i]);
    avlTree.LayerOrder();
    avlTree.Destroy();

    std::cout << "Insert elements need rotateRL" << std::endl;
    for (i = 0; i < sizeof(rlArr)/sizeof(int); ++i)
        avlTree.Insert(rlArr[i]);
    avlTree.LayerOrder();
    avlTree.Destroy();

    std::cout << "Delete root" << std::endl;
    for (i = 0; i < sizeof(delArr1)/sizeof(int); ++i)
        avlTree.Insert(delArr1[i]);
    avlTree.Remove(30);
    avlTree.LayerOrder();
    avlTree.Destroy();

    std::cout << "Delete elememt 40" << std::endl;
    for (i = 0; i < sizeof(delArr2)/sizeof(int); ++i)
        avlTree.Insert(delArr2[i]);
    avlTree.Remove(40);
    avlTree.LayerOrder();
    avlTree.Destroy();

    std::cout << "Delete elememt 10, check variant f == 1" << std::endl;
    for (i = 0; i < sizeof(delFArr3)/sizeof(int); ++i)
        avlTree.Insert(delFArr3[i]);
    avlTree.Remove(10);
    avlTree.LayerOrder();
    avlTree.Destroy();

    std::cout << "Delete elememt 60, check variant link_flag" << std::endl;
    for (i = 0; i < sizeof(delLFArr4)/sizeof(int); ++i)
        avlTree.Insert(delLFArr4[i]);
    avlTree.Remove(60);
    avlTree.LayerOrder();
    avlTree.Destroy();

    return 0;
}

Insert elements need rotateLR
50
30 60
10 40 70
5 20 45
Insert elements need rotateLR
50
30 60
10 40 70
5 20 45
Insert elements need rotateLR
50
30 60
10 40 70
5 20 45
Insert elements need rotateRL
30
20 60
10 50 70
40 65 80
Delete root
20
Delete elememt 40
50
30 60
10 45 70
5 48
Delete elememt 10, check variant f == 1
60
30 70
20 50 65 80
40
Delete elememt 60, check variant link_flag
40
30 50
20 35 45 70
10 25 33 38 48 58 80
5 32 55 65 75