AVL树C++实现

1. AVL 树本质上还是一棵二叉搜索树，它的特点是：

本身首先是一棵二叉搜索树。
带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为 1。

2. 数据结构定义

AVL树节点类：

 template <typename T>

 class AVLTreeNode {

 public:

     T key;

     AVLTreeNode<T>* parent;

     AVLTreeNode<T>* left;

     AVLTreeNode<T>* right;

     AVLTreeNode():key(T()), parent(NULL), left(NULL), right(NULL) {}

 };

AVL树类：

 template <typename T>

 class AVLTree {

 public:

     AVLTree():root(NIL) {};

     void inorder_tree_walk(AVLTreeNode<T>* proot);     //中序遍历整棵树, 参数为AVL树的根节点

     int insert_key(const T& k);

     int delete_key(const T& k);

     AVLTreeNode<T>* tree_search(const T& k) const;     //根据关键字k搜索AVL树，返回对应的节点指针

     AVLTreeNode<T>* get_root() const;

     ~AVLTree();

 private:

     AVLTreeNode<T>* root;

     static AVLTreeNode<T>* NIL;

     int getDepth(const AVLTreeNode<T>* pnode) const;     //获取以pnode为根节点的树的深度

     int insert_Key(const T& k, AVLTreeNode<T>* pnode);

     int delete_key(const T& k, AVLTreeNode<T>* pnode);

     AVLTreeNode<T>* tree_minimum(AVLTreeNode<T>* pnode);  //获取最小值节点（最左边节点）

     void make_empty(AVLTreeNode<T>* proot);

     void avl_translate(AVLTreeNode<T>* node_u, AVLTreeNode<T>* node_v);

     void singleRotateWithL(AVLTreeNode<T>* pnode);   //左单旋

     void singleRotateWithR(AVLTreeNode<T>* pnode);   //右单旋

     void avl_delete_fixup(AVLTreeNode<T>* pnode, int flag);    //节点删除后调整AVL树, 使其满足AVL树的性质

     inline void rotateWithLR(AVLTreeNode<T>* pnode); //先左后右双旋

     inline void rotateWithRL(AVLTreeNode<T>* pnode); //先右后左双旋

 };

3. 假设有一个结点的平衡因子为 2（在 AVL 树中，最大就是 2，因为结点是一个一个地插入到树中的，一旦出现不平衡的状态就会立即进行调整，因此平衡因子最大不可能超过 2），那么就需要进行调整。由于任意一个结点最多只有两个儿子，所以当高度不平衡时，只可能是以下四种情况造成的：

对该结点的左儿子的左子树进行了一次插入。
对该结点的左儿子的右子树进行了一次插入。
对该结点的右儿子的左子树进行了一次插入。
对该结点的右儿子的右子树进行了一次插入。

　　情况 1 和 4 是关于该点的镜像对称，同样，情况 2 和 3 也是一对镜像对称。因此，理论上只有两种情况，当然了，从编程的角度来看还是四种情况。第一种情况是插入发生在“外边” 的情况（即左-左的情况或右-右的情况），该情况可以通过对树的一次单旋转来完成调整。第二种情况是插入发生在“内部”的情况（即左-右的情况或右-左的情况），该情况要通过稍微复杂些的双旋转来处理。
左单旋：

 template <typename T>

 void AVLTree<T>::singleRotateWithL(AVLTreeNode<T>* pnode) {

     AVLTreeNode<T> *tmpnode_x = pnode->right;

     pnode->right = tmpnode_x->left;

     if(tmpnode_x->left != NIL)

         tmpnode_x->left->parent = pnode;

     tmpnode_x->parent = pnode->parent;

     if(pnode->parent == NIL)

         root = tmpnode_x;

     else if(pnode == pnode->parent->left)

         pnode->parent->left = tmpnode_x;

     else

         pnode->parent->right = tmpnode_x;

     tmpnode_x->left = pnode;

     pnode->parent = tmpnode_x;

 }

右单旋：

 template <typename T>

 void AVLTree<T>::singleRotateWithR(AVLTreeNode<T>* pnode) {

     AVLTreeNode<T> *tmpnode_x = pnode->left;

     pnode->left = tmpnode_x->right;

     if(tmpnode_x->right != NIL)

         tmpnode_x->right->parent = pnode;

     tmpnode_x->parent = pnode->parent;

     if(pnode->parent == NIL)

         root = tmpnode_x;

     else if(pnode == pnode->parent->left)

         pnode->parent->left = tmpnode_x;

     else

         pnode->parent->right = tmpnode_x;

     tmpnode_x->right = pnode;

     pnode->parent = tmpnode_x;

 }

双旋可以直接复用单旋的代码：

 template <typename T>

 void AVLTree<T>::rotateWithLR(AVLTreeNode<T>* pnode) {

     singleRotateWithL(pnode->left);

     return singleRotateWithR(pnode);

 }

 template <typename T>

 void AVLTree<T>::rotateWithRL(AVLTreeNode<T>* pnode) {

     singleRotateWithR(pnode->right);

     return singleRotateWithL(pnode);

 }

4. 插入的核心思路是通过递归，找到合适的位置，插入新结点，然后看新结点是否平衡（平衡因子是否为 2），如果不平衡的话，就分成两种大情况以及两种小情况：
1）在结点的左儿子(data < p->data)

在左儿子的左子树((data < p->data) AND (data < p->left->data))， “外边”，要做单旋转。
在左儿子的右子树((data < p->data) AND (data > p->left->data0))，“内部”，要做双旋转。

2）在结点的右儿子(data > p->data)

在右儿子的左子树((data > p->data) AND (data < p->right->data))，“内部”，要做双旋转。
在右儿子的右子树((data > p->data) AND (data > p->right->data))，“外边”，要做单旋转。

 template <typename T>

 int AVLTree<T>::insert_Key(const T& k, AVLTreeNode<T>* pnode) {

     if(root == NIL) {

         AVLTreeNode<T>* newnode = new AVLTreeNode<T>;

         newnode->key = k;

         newnode->left = NIL;

         newnode->right = NIL;

         newnode->parent = NIL;

         root = newnode;

     }

     else {

         if(k < pnode->key) {

             if(pnode->left == NIL) {

                 AVLTreeNode<T>* newnode = new AVLTreeNode<T>;

                 newnode->key = k;

                 newnode->left = NIL;

                 newnode->right = NIL;

                 newnode->parent = pnode;

                 pnode->left = newnode;

             }

             else

                 insert_Key(k, pnode->left);

             if( == (getDepth(pnode->left) - getDepth(pnode->right))) {

                 if(k < pnode->left->key)

                     singleRotateWithR(pnode);

                 else

                     rotateWithLR(pnode);

             }

         }

         else {

             if(pnode->right == NIL) {

                 AVLTreeNode<T>* newnode = new AVLTreeNode<T>;

                 newnode->key = k;

                 newnode->left = NIL;

                 newnode->right = NIL;

                 newnode->parent = pnode;

                 pnode->right = newnode;

             }

             else

                 insert_Key(k, pnode->right);

             if( == (getDepth(pnode->right) - getDepth(pnode->left))) {

                 if(k > pnode->right->key)

                     singleRotateWithL(pnode);

                 else

                     rotateWithRL(pnode);

             }

         }

     }

     return ;

 }

5. AVL删除

 template <typename T>

 int AVLTree<T>::delete_key(const T& k) {

     int flag;

     AVLTreeNode<T>* delnode = tree_search(k);

     AVLTreeNode<T>* tmpnode_x = delnode->parent;

     if(delnode == tmpnode_x->left)

         flag = LC;

     else

         flag = RC;

     if(delnode->left == NIL)

         avl_translate(delnode, delnode->right);

     else if(delnode->right == NIL)

         avl_translate(delnode, delnode->left);

     else {

         AVLTreeNode<T>* tmpnode_y = tree_minimum(delnode->right);

         tmpnode_x = tmpnode_y->parent;

         if(tmpnode_y == tmpnode_x->left)

             flag = LC;

         else

             flag = RC;

         if(tmpnode_y->parent != delnode) {

             avl_translate(tmpnode_y, tmpnode_y->right);

             tmpnode_y->right = delnode->right;

             tmpnode_y->right->parent = tmpnode_y;

         }

         avl_translate(delnode, tmpnode_y);

         tmpnode_y->left = delnode->left;

         tmpnode_y->left->parent = tmpnode_y;

     }

     avl_delete_fixup(tmpnode_x, flag);

     return ;

 }

 template <typename T>

 void AVLTree<T>::avl_delete_fixup(AVLTreeNode<T>* pnode, int flag) {

     int tmpflag = flag;

     AVLTreeNode<T>* tmpnode_x = pnode;

     while(tmpnode_x != NIL) {

         if(tmpflag == LC) {

             if( == (getDepth(tmpnode_x->right) - getDepth(tmpnode_x->left))) {

                 if(LH == (getDepth(tmpnode_x->right->left) - getDepth(tmpnode_x->right->right)))

                     rotateWithRL(tmpnode_x);

                 else

                     singleRotateWithL(tmpnode_x);

                 break;

             }

         }

         else if(tmpflag == RC) {

             if( == (getDepth(tmpnode_x->left) - getDepth(tmpnode_x->right))) {

                 if(RH == (getDepth(tmpnode_x->left->left) - getDepth(tmpnode_x->left->right)))

                     rotateWithLR(tmpnode_x);

                 else

                     singleRotateWithR(tmpnode_x);

                 break;

             }

         }

         if(tmpnode_x == tmpnode_x->parent->left)

             tmpflag = LC;

         else if(tmpnode_x == tmpnode_x->parent->right)

             tmpflag = RC;

         tmpnode_x = tmpnode_x->parent;

     }

 }

简单测试：

==========================我是华丽的分割线=================================

源码猛戳{这里}！

=====================================================================

参考资料：

http://www.luocong.com/dsaanotes/index-Z-H-11.htm#node_sec_10.1

巴特西

AVL树C++实现

最新文章

热门文章