1. AVL 树本质上还是一棵二叉搜索树，它的特点是：
- 本身首先是一棵二叉搜索树。
- 带有平衡条件： 每个结点的左右子树的高度之差的绝对值（平衡因子） 最多为 1。
2. 数据结构定义
AVL树节点类：
1 template2 class AVLTreeNode {3 public:4 T key;5 AVLTreeNode * parent;6 AVLTreeNode * left;7 AVLTreeNode * right;8 AVLTreeNode():key(T()), parent(NULL), left(NULL), right(NULL) {}9 };
AVL树类：
1 template2 class AVLTree { 3 public: 4 AVLTree():root(NIL) {}; 5 void inorder_tree_walk(AVLTreeNode * proot); //中序遍历整棵树, 参数为AVL树的根节点 6 int insert_key(const T& k); 7 int delete_key(const T& k); 8 AVLTreeNode * tree_search(const T& k) const; //根据关键字k搜索AVL树，返回对应的节点指针 9 AVLTreeNode * get_root() const;10 ~AVLTree();11 12 private:13 AVLTreeNode * root;14 static AVLTreeNode * NIL;15 int getDepth(const AVLTreeNode * pnode) const; //获取以pnode为根节点的树的深度16 int insert_Key(const T& k, AVLTreeNode * pnode);17 int delete_key(const T& k, AVLTreeNode * pnode);18 AVLTreeNode * tree_minimum(AVLTreeNode * pnode); //获取最小值节点（最左边节点）19 void make_empty(AVLTreeNode * proot);20 void avl_translate(AVLTreeNode * node_u, AVLTreeNode * node_v);21 void singleRotateWithL(AVLTreeNode * pnode); //左单旋22 void singleRotateWithR(AVLTreeNode * pnode); //右单旋23 void avl_delete_fixup(AVLTreeNode * pnode, int flag); //节点删除后调整AVL树, 使其满足AVL树的性质24 inline void rotateWithLR(AVLTreeNode * pnode); //先左后右双旋25 inline void rotateWithRL(AVLTreeNode * pnode); //先右后左双旋26 };
3. 假设有一个结点的平衡因子为 2（在 AVL 树中， 最大就是 2， 因为结点是一个一个地插入到树中的， 一旦出现不平衡的状态就会立即进行调整， 因此平衡因子最大不可能超过 2），那么就需要进行调整。由于任意一个结点最多只有两个儿子，所以当高度不平衡时，只可能是以下四种情况造成的：
- 对该结点的左儿子的左子树进行了一次插入。
- 对该结点的左儿子的右子树进行了一次插入。
- 对该结点的右儿子的左子树进行了一次插入。
- 对该结点的右儿子的右子树进行了一次插入。
情况 1 和 4 是关于该点的镜像对称，同样，情况 2 和 3 也是一对镜像对称。因此，理论上只有两种情况，当然了，从编程的角度来看还是四种情况。第一种情况是插入发生在“外边” 的情况（即左-左的情况或右-右的情况），该情况可以通过对树的一次单旋转来完成调整。 第二种情况是插入发生在“内部”的情况（即左-右的情况或右-左的情况），该情况要通过稍微复杂些的双旋转来处理。
左单旋：1 template2 void AVLTree ::singleRotateWithL(AVLTreeNode * pnode) { 3 AVLTreeNode *tmpnode_x = pnode->right; 4 pnode->right = tmpnode_x->left; 5 if(tmpnode_x->left != NIL) 6 tmpnode_x->left->parent = pnode; 7 tmpnode_x->parent = pnode->parent; 8 if(pnode->parent == NIL) 9 root = tmpnode_x;10 else if(pnode == pnode->parent->left)11 pnode->parent->left = tmpnode_x;12 else13 pnode->parent->right = tmpnode_x;14 tmpnode_x->left = pnode;15 pnode->parent = tmpnode_x;16 }
右单旋：
1 template2 void AVLTree ::singleRotateWithR(AVLTreeNode * pnode) { 3 AVLTreeNode *tmpnode_x = pnode->left; 4 pnode->left = tmpnode_x->right; 5 if(tmpnode_x->right != NIL) 6 tmpnode_x->right->parent = pnode; 7 tmpnode_x->parent = pnode->parent; 8 if(pnode->parent == NIL) 9 root = tmpnode_x;10 else if(pnode == pnode->parent->left)11 pnode->parent->left = tmpnode_x;12 else13 pnode->parent->right = tmpnode_x;14 tmpnode_x->right = pnode;15 pnode->parent = tmpnode_x;16 }
双旋可以直接复用单旋的代码：
1 template2 void AVLTree ::rotateWithLR(AVLTreeNode * pnode) { 3 singleRotateWithL(pnode->left); 4 return singleRotateWithR(pnode); 5 } 6 7 template 8 void AVLTree ::rotateWithRL(AVLTreeNode * pnode) { 9 singleRotateWithR(pnode->right);10 return singleRotateWithL(pnode);11 }
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))，“外边”，要做单旋转。
1 template2 int AVLTree ::insert_Key(const T& k, AVLTreeNode * pnode) { 3 if(root == NIL) { 4 AVLTreeNode * newnode = new AVLTreeNode ; 5 newnode->key = k; 6 newnode->left = NIL; 7 newnode->right = NIL; 8 newnode->parent = NIL; 9 root = newnode;10 }11 else {12 if(k < pnode->key) {13 if(pnode->left == NIL) {14 AVLTreeNode * newnode = new AVLTreeNode ;15 newnode->key = k;16 newnode->left = NIL;17 newnode->right = NIL;18 newnode->parent = pnode;19 pnode->left = newnode;20 }21 else22 insert_Key(k, pnode->left);23 if(2 == (getDepth(pnode->left) - getDepth(pnode->right))) {24 if(k < pnode->left->key)25 singleRotateWithR(pnode);26 else27 rotateWithLR(pnode);28 }29 }30 else {31 if(pnode->right == NIL) {32 AVLTreeNode * newnode = new AVLTreeNode ;33 newnode->key = k;34 newnode->left = NIL;35 newnode->right = NIL;36 newnode->parent = pnode;37 pnode->right = newnode;38 }39 else40 insert_Key(k, pnode->right);41 if(2 == (getDepth(pnode->right) - getDepth(pnode->left))) {42 if(k > pnode->right->key)43 singleRotateWithL(pnode);44 else45 rotateWithRL(pnode);46 }47 }48 }49 return 0;50 }
5. AVL删除
1 template2 int AVLTree ::delete_key(const T& k) { 3 int flag; 4 AVLTreeNode * delnode = tree_search(k); 5 AVLTreeNode * tmpnode_x = delnode->parent; 6 if(delnode == tmpnode_x->left) 7 flag = LC; 8 else 9 flag = RC;10 if(delnode->left == NIL)11 avl_translate(delnode, delnode->right);12 else if(delnode->right == NIL)13 avl_translate(delnode, delnode->left);14 else {15 AVLTreeNode * tmpnode_y = tree_minimum(delnode->right);16 tmpnode_x = tmpnode_y->parent;17 if(tmpnode_y == tmpnode_x->left)18 flag = LC;19 else20 flag = RC;21 if(tmpnode_y->parent != delnode) {22 avl_translate(tmpnode_y, tmpnode_y->right);23 tmpnode_y->right = delnode->right;24 tmpnode_y->right->parent = tmpnode_y;25 }26 avl_translate(delnode, tmpnode_y);27 tmpnode_y->left = delnode->left;28 tmpnode_y->left->parent = tmpnode_y;29 }30 avl_delete_fixup(tmpnode_x, flag);31 return 0;32 }
1 template2 void AVLTree ::avl_delete_fixup(AVLTreeNode * pnode, int flag) { 3 int tmpflag = flag; 4 AVLTreeNode * tmpnode_x = pnode; 5 while(tmpnode_x != NIL) { 6 if(tmpflag == LC) { 7 if(2 == (getDepth(tmpnode_x->right) - getDepth(tmpnode_x->left))) { 8 if(LH == (getDepth(tmpnode_x->right->left) - getDepth(tmpnode_x->right->right))) 9 rotateWithRL(tmpnode_x);10 else11 singleRotateWithL(tmpnode_x);12 break;13 }14 }15 else if(tmpflag == RC) {16 if(2 == (getDepth(tmpnode_x->left) - getDepth(tmpnode_x->right))) {17 if(RH == (getDepth(tmpnode_x->left->left) - getDepth(tmpnode_x->left->right)))18 rotateWithLR(tmpnode_x);19 else20 singleRotateWithR(tmpnode_x);21 break;22 } 23 }24 if(tmpnode_x == tmpnode_x->parent->left)25 tmpflag = LC;26 else if(tmpnode_x == tmpnode_x->parent->right)27 tmpflag = RC;28 tmpnode_x = tmpnode_x->parent;29 }30 }
简单测试：
==========================我是华丽的分割线=================================
源码猛戳{
}！
=====================================================================
参考资料：