"《算法导论》之‘树’"：AVL树

　　本文关于AVL树的介绍引自博文AVL树(二)之 C++的实现，与二叉查找树相同的部分则不作介绍直接引用；代码实现是在本文的基础上自己实现且继承自上一篇博文二叉查找树。

1.AVL树的介绍

　　AVL树是高度平衡的而二叉树。它的特点是：AVL树中任何节点的两个子树的高度最大差别为1。

　　

　　上面的两张图片，左边的是AVL树，它的任何节点的两个子树的高度差别都<=1；而右边的不是AVL树，因为7的两颗子树的高度相差为2(以2为根节点的树的高度是3，而以8为根节点的树的高度是1)。

2.节点的旋转

　　如果在AVL树中进行插入或删除节点后，可能导致AVL树失去平衡。这种失去平衡的可以概括为4种姿态：LL(左左)，LR(左右)，RR(右右)和RL(右左)。下面给出它们的示意图：

　　

　　上图中的4棵树都是"失去平衡的AVL树"，从左往右的情况依次是：LL、LR、RL、RR。除了上面的情况之外，还有其它的失去平衡的AVL树，如下图：

　　

　　上面的两张图都是为了便于理解，而列举的关于"失去平衡的AVL树"的例子。总的来说，AVL树失去平衡时的情况一定是LL、LR、RL、RR这4种之一，它们都由各自的定义：

　　(1) LL：LeftLeft，也称为"左左"。插入或删除一个节点后，根节点的左子树的左子树还有非空子节点，导致"根的左子树的高度"比"根的右子树的高度"大2，导致AVL树失去了平衡。
     例如，在上面LL情况中，由于"根节点(8)的左子树(4)的左子树(2)还有非空子节点"，而"根节点(8)的右子树(12)没有子节点"；导致"根节点(8)的左子树(4)高度"比"根节点(8)的右子树(12)"高2。

　　(2) LR：LeftRight，也称为"左右"。插入或删除一个节点后，根节点的左子树的右子树还有非空子节点，导致"根的左子树的高度"比"根的右子树的高度"大2，导致AVL树失去了平衡。
     例如，在上面LR情况中，由于"根节点(8)的左子树(4)的左子树(6)还有非空子节点"，而"根节点(8)的右子树(12)没有子节点"；导致"根节点(8)的左子树(4)高度"比"根节点(8)的右子树(12)"高2。

　　(3) RL：RightLeft，称为"右左"。插入或删除一个节点后，根节点的右子树的左子树还有非空子节点，导致"根的右子树的高度"比"根的左子树的高度"大2，导致AVL树失去了平衡。
     例如，在上面RL情况中，由于"根节点(8)的右子树(12)的左子树(10)还有非空子节点"，而"根节点(8)的左子树(4)没有子节点"；导致"根节点(8)的右子树(12)高度"比"根节点(8)的左子树(4)"高2。

　　(4) RR：RightRight，称为"右右"。插入或删除一个节点后，根节点的右子树的右子树还有非空子节点，导致"根的右子树的高度"比"根的左子树的高度"大2，导致AVL树失去了平衡。
     例如，在上面RR情况中，由于"根节点(8)的右子树(12)的右子树(14)还有非空子节点"，而"根节点(8)的左子树(4)没有子节点"；导致"根节点(8)的右子树(12)高度"比"根节点(8)的左子树(4)"高2。

　　前面说过，如果在AVL树中进行插入或删除节点后，可能导致AVL树失去平衡。AVL失去平衡之后，可以通过旋转使其恢复平衡，下面分别介绍"LL(左左)，LR(左右)，RR(右右)和RL(右左)"这4种情况对应的旋转方法。

2.1 LL的旋转

　　LL失去平衡的情况，可以通过一次旋转让AVL树恢复平衡。如下图：

　　

　　图中左边是旋转之前的树，右边是旋转之后的树。从中可以发现，旋转之后的树又变成了AVL树，而且该旋转只需要一次即可完成。
　　对于LL旋转，你可以这样理解为：LL旋转是围绕"失去平衡的AVL根节点"进行的，也就是节点k2；而且由于是LL情况，即左左情况，就用手抓着"左孩子，即k1"使劲摇。将k1变成根节点，k2变成k1的右子树，"k1的右子树"变成"k2的左子树"。

　　代码如下：

 // LL：左左对应的情况(左单旋转)。
 template<class T>
 Node<T> * AVLTree<T>::leftLeftRotation(Node<T>* k2)
 {
     NodePointer k1 = NULL, k2ParentPtr = NULL;

     k1 = k2->left;
     if (k2 != root)
     {
         k2ParentPtr = k2->parent;
         if (k2ParentPtr->left == k2)
         {
             k2ParentPtr->left = k1;
         }
         else
         {
             k2ParentPtr->right = k1;
         }
         k1->parent = k2ParentPtr;
     }
     else
     {
         k1->parent = NULL;
     }

     k2->left = k1->right;
     k1->right = k2;
     k2->parent = k1;

     if (k2->left != NULL)
     {
         NodePointer tmpK2Left = k2->left;
         tmpK2Left->parent = k2;
     }

     return k1;
 }

leftLeftRotation

2.2 RR的旋转

　　理解了LL之后，RR就相当容易理解了。RR是与LL对称的情况！RR恢复平衡的旋转方法如下：

　　

　　图中左边是旋转之前的树，右边是旋转之后的树。RR旋转也只需要一次即可完成。

　　代码如下：

 // RR：右右对应的情况(右单旋转)。
 template<class T>
 Node<T> * AVLTree<T>::rightRightRotation(Node<T>* k1)
 {
     NodePointer k2 = NULL, k1ParentPtr = NULL;

     k2 = k1->right;
     if (k1 != root)
     {
         k1ParentPtr = k1->parent;
         if (k1ParentPtr->left == k1)
         {
             k1ParentPtr->left = k2;
         }
         else
         {
             k1ParentPtr->right = k2;
         }
         k2->parent = k1ParentPtr;
     }
     else
     {
         k2->parent = NULL;
     }

     k1->right = k2->left;
     k2->left = k1;
     k1->parent = k2;

     if (k1->right != NULL)
     {
         NodePointer tmpK1Right = k1->right;
         tmpK1Right->parent = k1;
     }

     return k2;
 }

rightRightRotation

2.3 LR的旋转

　　LR失去平衡的情况，需要经过两次旋转才能让AVL树恢复平衡。如下图：

　　

　　第一次旋转是围绕"k1"进行的"RR旋转"，第二次是围绕"k3"进行的"LL旋转"。

　　代码如下：

 // LR：左右对应的情况(左双旋转)。
 template<class T>
 Node<T> * AVLTree<T>::leftRightRotation(Node<T>* k3)
 {
     k3->left = rightRightRotation(k3->left);

     return leftLeftRotation(k3);
 }

leftRightRotation

2.4 RL的旋转

　　RL是与LR的对称情况！RL恢复平衡的旋转方法如下：

　　

　　第一次旋转是围绕"k3"进行的"LL旋转"，第二次是围绕"k1"进行的"RR旋转"。

　　代码如下：

 // RL：右左对应的情况(右双旋转)。
 template<class T>
 Node<T> * AVLTree<T>::rightLeftRotation(Node<T>* k1)
 {
     k1->right = leftLeftRotation(k1->right);

     return rightRightRotation(k1);
 }

rightLeftRotation

3.代码实现

　　这里定义的AVL树的类如下：

 #include "BSTree.hpp"

 template<class T>
 class AVLTree : public BSTree<T>
 {
 public:
     AVLTree();
     virtual ~AVLTree();
     virtual bool addNode(T k, T val);                 // 覆盖BSTree中的addNode函数
     virtual bool delNode(T k);                        // 覆盖BSTree中的delNode函数

 private:
     Node<T> * findImbalanceNode(NodePointer ptr);
     // LL：左左对应的情况(左单旋转)。
     Node<T> * leftLeftRotation(NodePointer k2);
     // RR：右右对应的情况(右单旋转)。
     Node<T> * rightRightRotation(NodePointer k1);
     // LR：左右对应的情况(左双旋转)。
     Node<T> * leftRightRotation(NodePointer k3);
     // RL：右左对应的情况(右双旋转)。
     Node<T> * rightLeftRotation(NodePointer k1);

 };

　　实现程序为：

 #ifndef AVLTREE_H
 #define AVLTREE_H

 #include "BSTree.hpp"

 template<class T>
 class AVLTree : public BSTree<T>
 {
 public:
     AVLTree();
     virtual ~AVLTree();
     virtual bool addNode(T k, T val);                // 覆盖BSTree中的addNode函数
     virtual bool delNode(T k);                        // 覆盖BSTree中的delNode函数

 private:
     Node<T> * findImbalanceNode(NodePointer ptr);
     // LL：左左对应的情况(左单旋转)。
     Node<T> * leftLeftRotation(NodePointer k2);
     // RR：右右对应的情况(右单旋转)。
     Node<T> * rightRightRotation(NodePointer k1);
     // LR：左右对应的情况(左双旋转)。
     Node<T> * leftRightRotation(NodePointer k3);
     // RL：右左对应的情况(右双旋转)。
     Node<T> * rightLeftRotation(NodePointer k1);

 };

 template<class T>
 AVLTree<T>::AVLTree()
 {
     root = NULL;
 }

 template<class T>
 AVLTree<T>::~AVLTree()
 {
     destroy();
     root = NULL;
 }

 template<class T>
 bool AVLTree<T>::addNode(T k, T val)
 {
     bool isSuccess = BSTree<T>::addNode(k, val);
     if (isSuccess)
     {
         NodePointer ptr = searchNode(k);
         if (ptr != root)
         {
             NodePointer preParent = ptr->parent;
             if (preParent != root)
             {
                 NodePointer prePreParent = preParent->parent;
                 if (prePreParent == root)
                 {
                     if (getHeight(prePreParent->left) - getHeight(prePreParent->right) == )
                     {
                         if (ptr == preParent->left)
                         {
                             root = leftLeftRotation(prePreParent);
                         }
                         else
                         {
                             root = leftRightRotation(prePreParent);
                         }
                     }
                     else if (getHeight(prePreParent->right) - getHeight(prePreParent->left) == )
                     {
                         if (ptr == preParent->left)
                         {
                             root = rightLeftRotation(prePreParent);
                         }
                         else
                         {
                             root = rightRightRotation(prePreParent);
                         }
                     }
                 }
                 else
                 {
                     NodePointer prePrePreParent = prePreParent->parent;
                     if (getHeight(prePreParent->left) - getHeight(prePreParent->right) == )
                     {
                         if (prePreParent == prePrePreParent->left)
                         {
                             if (ptr == preParent->left)
                             {
                                 prePrePreParent->left = leftLeftRotation(prePreParent);
                             }
                             else
                             {
                                 prePrePreParent->left = leftRightRotation(prePreParent);
                             }
                         }
                         else
                         {
                             if (ptr == preParent->left)
                             {
                                 prePrePreParent->right = leftLeftRotation(prePreParent);
                             }
                             else
                             {
                                 prePrePreParent->right = leftRightRotation(prePreParent);
                             }
                         }
                     }
                     else if (getHeight(prePreParent->right) - getHeight(prePreParent->left) == )
                     {
                         if (prePreParent == prePrePreParent->left)
                         {
                             if (ptr == preParent->left)
                             {
                                 prePrePreParent->left = rightLeftRotation(prePreParent);
                             }
                             else
                             {
                                 prePrePreParent->left = rightRightRotation(prePreParent);
                             }
                         }
                         else
                         {
                             if (ptr == preParent->left)
                             {
                                 prePrePreParent->right = rightLeftRotation(prePreParent);
                             }
                             else
                             {
                                 prePrePreParent->right = rightRightRotation(prePreParent);
                             }
                         }
                     }
                 }
             }
         }
     }

     return isSuccess;
 }

 template<class T>
 bool AVLTree<T>::delNode(T k)
 {
     bool isSuccess = true;
     NodePointer ptr = searchNode(k);
     NodePointer preParent = NULL;
     if (ptr != NULL)
     {
         if (ptr == root)
         {
             BSTree<T>::delNode(k);
             // only left left exist
             if (getHeight(root->left) - getHeight(root->right) == )
             {
                 root = leftLeftRotation(root);
             }
         }
         else
         {
             NodePointer lNode = NULL, rNode = NULL;
             preParent = ptr->parent;
             if (preParent == root)
             {
                 BSTree<T>::delNode(k);
                 lNode = root->left;
                 rNode = root->right;
                 if (getHeight(preParent->left) - getHeight(preParent->right) == )
                 {
                     if (getHeight(lNode->left) >= getHeight(lNode->right))
                     {
                         root = leftLeftRotation(preParent);
                     }
                     else
                     {
                         root = leftRightRotation(preParent);
                     }
                 }
                 else if (getHeight(preParent->right) - getHeight(preParent->left) == )
                 {
                     if (getHeight(rNode->right) >= getHeight(rNode->left))
                     {
                         root = rightRightRotation(preParent);
                     }
                     else
                     {
                         root = rightLeftRotation(preParent);
                     }
                 }
             }
             else
             {
                 NodePointer prePreParent = NULL;
                 NodePointer lNode = NULL, rNode = NULL;
                 BSTree<T>::delNode(k);
                 // 这里需要递归查找不平衡点,以防止高层结点不平衡而低层结点平衡的情况
                 NodePointer tmpPtr = findImbalanceNode(preParent);
                 if (tmpPtr != NULL)
                 {
                     if (tmpPtr == root)
                     {
                         lNode = tmpPtr->left;
                         rNode = tmpPtr->right;
                         if (getHeight(tmpPtr->left) - getHeight(tmpPtr->right) == )
                         {
                             if (getHeight(lNode->left) >= getHeight(lNode->right))
                             {
                                 root = leftLeftRotation(tmpPtr);
                             }
                             else
                             {
                                 root = leftRightRotation(tmpPtr);
                             }
                         }
                         else if (getHeight(tmpPtr->right) - getHeight(tmpPtr->left) == )
                         {
                             if (getHeight(rNode->right) >= getHeight(rNode->left))
                             {
                                 root = rightRightRotation(tmpPtr);
                             }
                             else
                             {
                                 root = rightLeftRotation(tmpPtr);
                             }
                         }
                     }
                     else
                     {
                         prePreParent = tmpPtr->parent;
                         lNode = tmpPtr->left;
                         rNode = tmpPtr->right;
                         if (getHeight(tmpPtr->left) - getHeight(tmpPtr->right) == )
                         {
                             if (tmpPtr == prePreParent->left)
                             {
                                 if (getHeight(lNode->left) >= getHeight(lNode->right))
                                 {
                                     prePreParent->left = leftLeftRotation(tmpPtr);
                                 }
                                 else
                                 {
                                     prePreParent->left = leftRightRotation(tmpPtr);
                                 }
                             }
                             else
                             {
                                 if (getHeight(lNode->left) >= getHeight(lNode->right))
                                 {
                                     prePreParent->right = leftLeftRotation(tmpPtr);
                                 }
                                 else
                                 {
                                     prePreParent->right = leftRightRotation(tmpPtr);
                                 }
                             }
                         }
                         else if (getHeight(tmpPtr->right) - getHeight(tmpPtr->left) == )
                         {
                             if (tmpPtr == prePreParent->left)
                             {
                                 if (getHeight(rNode->right) >= getHeight(rNode->left))
                                 {
                                     prePreParent->left = rightRightRotation(tmpPtr);
                                 }
                                 else
                                 {
                                     prePreParent->left = rightLeftRotation(tmpPtr);
                                 }
                             }
                             else
                             {
                                 if (getHeight(rNode->right) >= getHeight(rNode->left))
                                 {
                                     prePreParent->right = rightRightRotation(tmpPtr);
                                 }
                                 else
                                 {
                                     prePreParent->right = rightLeftRotation(tmpPtr);
                                 }
                             }
                         }
                     }
                 }
             }
         }
     }
     else
     {
         isSuccess = false;
     }

     return isSuccess;
 }

 template<class T>
 Node<T> * AVLTree<T>::findImbalanceNode(NodePointer ptr)
 {
     unsigned int lHeight = getHeight(ptr->left), rHeight = getHeight(ptr->right);
     if (ptr == NULL)
     {
         return NULL;
     }
     else
     {
         if (lHeight - rHeight ==  || rHeight - lHeight == )
         {
             return ptr;
         }
         else
         {
             findImbalanceNode(ptr->parent);
         }
     }
 }

 // LL：左左对应的情况(左单旋转)。
 template<class T>
 Node<T> * AVLTree<T>::leftLeftRotation(Node<T>* k2)
 {
     NodePointer k1 = NULL, k2ParentPtr = NULL;

     k1 = k2->left;
     if (k2 != root)
     {
         k2ParentPtr = k2->parent;
         if (k2ParentPtr->left == k2)
         {
             k2ParentPtr->left = k1;
         }
         else
         {
             k2ParentPtr->right = k1;
         }
         k1->parent = k2ParentPtr;
     }
     else
     {
         k1->parent = NULL;
     }

     k2->left = k1->right;
     k1->right = k2;
     k2->parent = k1;

     if (k2->left != NULL)
     {
         NodePointer tmpK2Left = k2->left;
         tmpK2Left->parent = k2;
     }

     return k1;
 }

 // RR：右右对应的情况(右单旋转)。
 template<class T>
 Node<T> * AVLTree<T>::rightRightRotation(Node<T>* k1)
 {
     NodePointer k2 = NULL, k1ParentPtr = NULL;

     k2 = k1->right;
     if (k1 != root)
     {
         k1ParentPtr = k1->parent;
         if (k1ParentPtr->left == k1)
         {
             k1ParentPtr->left = k2;
         }
         else
         {
             k1ParentPtr->right = k2;
         }
         k2->parent = k1ParentPtr;
     }
     else
     {
         k2->parent = NULL;
     }

     k1->right = k2->left;
     k2->left = k1;
     k1->parent = k2;

     if (k1->right != NULL)
     {
         NodePointer tmpK1Right = k1->right;
         tmpK1Right->parent = k1;
     }

     return k2;
 }

 // LR：左右对应的情况(左双旋转)。
 template<class T>
 Node<T> * AVLTree<T>::leftRightRotation(Node<T>* k3)
 {
     k3->left = rightRightRotation(k3->left);

     return leftLeftRotation(k3);
 }

 // RL：右左对应的情况(右双旋转)。
 template<class T>
 Node<T> * AVLTree<T>::rightLeftRotation(Node<T>* k1)
 {
     k1->right = leftLeftRotation(k1->right);

     return rightRightRotation(k1);
 }

 #endif 

AVLTree.hpp

　　Boost单元测试程序为：

 #include "stdafx.h"
 #include "../AVLTree/AVLTree.hpp"

 struct AVLTree_Fixture
 {
 public:
     AVLTree_Fixture()
     {
         testAVLTree = new AVLTree<int>();
     }
     ~AVLTree_Fixture()
     {
         delete testAVLTree;
     }

     AVLTree<int> * testAVLTree;

 };

 BOOST_FIXTURE_TEST_SUITE(AVLTree_Test_Suite, AVLTree_Fixture)

 BOOST_AUTO_TEST_CASE( AVLTree_addNode_Test )
 {
     // add node next next to root and cause "left left/right" imbalance
     // left left
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     testAVLTree->destroy();
     // left right
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     testAVLTree->destroy();
     // add node next next to root and cause "right left/right" imbalance
     // right left
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     testAVLTree->destroy();
     // right right
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     testAVLTree->destroy();

     // add node not next next to root and cause "left left/right" imbalance
     // left left
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     testAVLTree->destroy();

     // left right
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     testAVLTree->destroy();

     // add node next next to root and cause "right left/right" imbalance
     // right left
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     testAVLTree->destroy();

     // right right
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     BOOST_REQUIRE(testAVLTree->addNode(, ) == true);
     testAVLTree->destroy();

 }

 BOOST_AUTO_TEST_CASE(AVLTree_delNode_Test)
 {
     // delete root and cause "right right" imbalance --------------------------------
     // actually, only "right right" imbalance will be caused at such condition ------
     int key1[] = { , , ,  };
     int value1[] = { , , ,  };
     unsigned len1 = sizeof(key1) / sizeof(int);
     testAVLTree->creatTree(key1, value1, len1);
     BOOST_REQUIRE(testAVLTree->delNode() == true);
     testAVLTree->destroy();

     // delete right node of 'root' and cause "left left/right" imbalance ----------------
     // left left
     int key31[] = { , , , , , ,  };
     int value31[] = { , , , , , ,  };
     unsigned len31 = sizeof(key31) / sizeof(int);
     testAVLTree->creatTree(key31, value31, len31);
     BOOST_REQUIRE(testAVLTree->delNode() == true);
     testAVLTree->destroy();

     // left right
     int key32[] = { , , , , , ,  };
     int value32[] = { , , , , , ,  };
     unsigned len32 = sizeof(key32) / sizeof(int);
     testAVLTree->creatTree(key32, value32, len32);
     BOOST_REQUIRE(testAVLTree->delNode() == true);
     testAVLTree->destroy();

     // delete left node of 'root' and cause "right left/right" imbalance -------------------
     // right left
     int key21[] = { , , , , , ,  };
     int value21[] = { , , , , , ,  };
     unsigned len21 = sizeof(key21) / sizeof(int);
     testAVLTree->creatTree(key21, value21, len21);
     BOOST_REQUIRE(testAVLTree->delNode() == true);
     testAVLTree->destroy();
     // right right
     int key22[] = { , , , , , ,  };
     int value22[] = { , , , , , ,  };
     unsigned len22 = sizeof(key22) / sizeof(int);
     testAVLTree->creatTree(key22, value22, len22);
     BOOST_REQUIRE(testAVLTree->delNode() == true);
     testAVLTree->destroy();

     // delete node and cause "left left/right" imbalance -------------------
     // left left -- imbalanced node is at root
     int key41[] = { , , , , , ,  };
     int value41[] = { , , , , , ,  };
     unsigned len41 = sizeof(key41) / sizeof(int);
     testAVLTree->creatTree(key41, value41, len41);
     BOOST_REQUIRE(testAVLTree->delNode() == true);
     testAVLTree->destroy();

     // left right -- imbalanced node is at root
     int key42[] = { , , , , , ,  };
     int value42[] = { , , , , , ,  };
     unsigned len42 = sizeof(key42) / sizeof(int);
     testAVLTree->creatTree(key42, value42, len42);
     BOOST_REQUIRE(testAVLTree->delNode() == true);
     testAVLTree->destroy();

     // left left -- imbalanced node is not at root
     int key43[] = { , , , , , , ,  };
     int value43[] = { , , , , , , ,  };
     unsigned len43 = sizeof(key43) / sizeof(int);
     testAVLTree->creatTree(key43, value43, len43);
     BOOST_REQUIRE(testAVLTree->delNode() == true);
     testAVLTree->destroy();

     // left right -- imbalanced node is not at root
     int key44[] = { , , , , , , ,  };
     int value44[] = { , , , , , , ,  };
     unsigned len44 = sizeof(key44) / sizeof(int);
     testAVLTree->creatTree(key44, value44, len44);
     BOOST_REQUIRE(testAVLTree->delNode() == true);
     testAVLTree->destroy();

     // delete node and cause "right left/right" imbalance -------------------
     // right left -- imbalanced node is at root
     int key51[] = { , , , , , ,  };
     int value51[] = { , , , , , ,  };
     unsigned len51 = sizeof(key51) / sizeof(int);
     testAVLTree->creatTree(key51, value51, len51);
     BOOST_REQUIRE(testAVLTree->delNode() == true);
     testAVLTree->destroy();

     // right right -- imbalanced node is at root
     int key52[] = { , , , , , ,  };
     int value52[] = { , , , , , ,  };
     unsigned len52 = sizeof(key52) / sizeof(int);
     testAVLTree->creatTree(key52, value52, len52);
     BOOST_REQUIRE(testAVLTree->delNode() == true);
     testAVLTree->destroy();

     // right left -- imbalanced node is not at root
     int key53[] = { , , , , , , , ,  };
     int value53[] = { , , , , , , , ,  };
     unsigned len53 = sizeof(key53) / sizeof(int);
     testAVLTree->creatTree(key53, value53, len53);
     BOOST_REQUIRE(testAVLTree->delNode() == true);
     testAVLTree->destroy();

     // right right -- imbalanced node is not at root
     int key54[] = { , , , , , , , ,  };
     int value54[] = { , , , , , , , ,  };
     unsigned len54 = sizeof(key54) / sizeof(int);
     testAVLTree->creatTree(key54, value54, len54);
     BOOST_REQUIRE(testAVLTree->delNode() == true);
     testAVLTree->destroy();

 }

 //BOOST_AUTO_TEST_CASE(AVLTree_CopyConstructor_Test)
 //{
 //    // leave blank
 //}
 //
 //BOOST_AUTO_TEST_CASE(AVLTree_EqualOperator_Test)
 //{
 //    // leave blank
 //}

 BOOST_AUTO_TEST_SUITE_END()

AVTreeUnitTest

　　本篇博文的代码均托管到Github.