平衡二叉树【学习笔记】

一、引文

　　二叉搜索树的查找效率取决于平均搜索长度，而这又取决去树的形状。当二叉搜索树退化为一个链表时，查找效率非常低。理想的形状是任何结点的左右子树的高度最多相差1，而这样的二叉树我们也称之位平衡二叉树。

二、分析

平衡二叉树的最核心的地方就在于四种旋转情况

左左情况：右旋

即相对根结点的左子树的高度比右子树高2，且插入的点为左子树的左孩子，不满足条件，所以右旋。

左右情况：先左再右

但如果插入的数是3，如果再只右旋，就会发现有问题，所以这里需要先以2为根结点左旋再以4为根结点右旋。

右右情况：左旋

即相对根节点的右子树的高度比左子树高2，且插入的点为右子树的右孩子，不满足条件，所以左旋

右左情况：先右再左

如果插入的为5，那么如果只左旋也会出现问题，所以先右旋再左旋。

三、具体代码实现

  1 #ifndef AVL_H
  2 #define AVL_H
  3 
  4 using namespace std;
  5 
  6 template<class T>
  7 class AvlTree
  8 {
  9 private:
 10     typedef struct AvlNode
 11     {
 12         T data;                           //数据
 13         int height;                             //结点深度
 14         struct AvlNode *lchild, *rchild;    //左右孩子
 15         AvlNode(const T &item):data(item),height(0),lchild(NULL),rchild(NULL){}
 16     }AvlNode;
 17     AvlNode *Root;
 18     int size;
 19     void R_Rotate(AvlNode * &root);        //右旋
 20     void L_Rotate(AvlNode * &root);        //左旋
 21     void LR_Rotate(AvlNode * &root);       //先左再右
 22     void RL_Rotate(AvlNode * &root);       //先右再左
 23     int Height(AvlNode * &root){ return (root == NULL?-1:root->height);};      //-1是因为根的深度为0
 24     void Print(AvlNode * root);
 25 public:
 26     AvlTree(void):Root(NULL),size(0){};
 27     ~AvlTree(void){Clear(Root); size = 0;};
 28     void Insert(const T &x, AvlNode * &root);
 29     void Insert(const T&x){Insert(x, Root);};
 30     int Size(){return size;};
 31     void Clear(AvlNode *&root);
 32     void Print(){Print(Root);puts("");};
 33     
 34 };
 35 
 36 template<class T>
 37 void AvlTree<T>::R_Rotate(AvlNode * &root)
 38 {
 39     AvlNode *p = NULL;
 40     p = root->lchild;
 41     root->lchild = p->rchild;
 42     p->rchild = root;
 43     root->height = max(Height(root->lchild), Height(root->rchild)) + 1;
 44     p->height = max(Height(p->lchild), Height(p->rchild)) + 1;
 45     root = p;
 46 }
 47 template<class T>
 48 void AvlTree<T>::L_Rotate(AvlNode * &root)
 49 {
 50     AvlNode *p = NULL;
 51     p = root->rchild;
 52     root->rchild = p->lchild;
 53     p->lchild = root;
 54     root->height = max(Height(root->lchild), Height(root->rchild)) + 1;
 55     p->height = max(Height(p->lchild), Height(p->rchild)) + 1;
 56     root = p;
 57 }
 58 template<class T>
 59 void AvlTree<T>::LR_Rotate(AvlNode * &root)
 60 {
 61     L_Rotate(root->lchild);
 62     R_Rotate(root);
 63 }
 64 template<class T>
 65 void AvlTree<T>::RL_Rotate(AvlNode * &root)
 66 {
 67     R_Rotate(root->rchild);
 68     L_Rotate(root);
 69 }
 70 template<class T>
 71 void AvlTree<T>::Insert(const T &x, AvlNode * &root)
 72 {
 73     if(root == NULL)
 74     {
 75         root = new AvlNode(x);
 76         size++;
 77         return;
 78     }
 79     else if(x < root->data)
 80     {
 81         Insert(x, root->lchild);
 82         if(Height(root->lchild) - Height(root->rchild) == 2)
 83         {
 84             if(x < root->lchild->data)
 85                 R_Rotate(root);
 86             else
 87                 LR_Rotate(root);
 88         }
 89     }
 90     else if(x > root->data)
 91     {
 92         Insert(x, root->rchild);
 93         if(Height(root->rchild) - Height(root->lchild) == 2)
 94         {
 95             if(x > root->rchild->data)
 96                 L_Rotate(root);
 97             else
 98                 RL_Rotate(root);
 99         }
100     }
101     root->height = max(Height(root->lchild), Height(root->rchild) ) + 1;
102     
103 }
104 
105 template<class T>
106 void AvlTree<T>::Clear(AvlNode * &root)
107 {
108     if(root == NULL)
109         return;
110     Clear(root->rchild);
111     Clear(root->lchild);
112     delete root;
113     root = NULL;   
114 }
115 
116 #endif

View Code