数据结构之AVL树

1，概述

　　AVL树是最早提出的自平衡二叉树，在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。AVL树中查找、插入和删除在最坏情况下是O（log n），平均情况下针对随机键列表构造的AVL树的高度大约是1.011log₂n+0.1（《算法设计与分析，P167》）。因此在平均情况下，查找一棵AVL树需要的比较次数和用折半查找法查找一个有序组几乎是相同的。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。本文介绍了AVL树的设计思想和基本操作。

2，基本术语

　　节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

3，基本操作

　　AVL树的插入、删除、查找节点操作与普通未平衡的二叉查找树一样。耗费O(log n)时间。与普通二叉查找树的区别是当插入、删除节点时需要保证平衡性。

　　有四种种情况可能导致二叉查找树不平衡，分别为：

（1）LL：插入一个新节点到根节点的左子树（Left）的左子树（Left），导致根节点的平衡因子由1变为2

（2）RR：插入一个新节点到根节点的右子树（Right）的右子树（Right），导致根节点的平衡因子由-1变为-2

（3）LR：插入一个新节点到根节点的左子树（Left）的右子树（Right），导致根节点的平衡因子由1变为2

（4）RL：插入一个新节点到根节点的右子树（Right）的左子树（Left），导致根节点的平衡因子由-1变为-2

　　如图所示，对应的处理方法是：（1）右单转（2）左单转（3）左右双转（4）右左双转。如果有若干节点的平衡因子为±2，先找出最靠近新插入叶子的不平衡节点，然后旋转以该节点为根的树。

4，C++实现

View Code

  1 #include<iostream>
  2 using namespace std;
  3 
  4 #define max(X,Y) ((X > Y) ? X : Y)
  5 
  6 class AVLtree{
  7 public:
  8     AVLtree();
  9     
 10     void insert_node(const int &);        //插入节点
 11     void del_node(const int &);            //删除节点
 12     bool find_node(const int &);        //查找节点
 13     void print();                    //中序遍历，相当于顺序打印
 14     void make_empty();
 15 
 16 private:
 17     struct AVLnode{
 18         int data;
 19         struct AVLnode *left,*right;
 20         int height;            //节点高度
 21     };
 22     struct AVLnode * head;    //根节点
 23     void insert_node(const int &,AVLnode * &);
 24     bool find_node(const int &,AVLnode * &);
 25     void clear(AVLnode * &);
 26 
 27     int height(AVLnode *);        //返回指定节点高度信息
 28 
 29     void single_left(AVLnode * &);                //左单转
 30     void single_right(AVLnode * &);                //右单转
 31     void double_LR(AVLnode * &);                //左右双转
 32     void double_RL(AVLnode * &);                //右左双转
 33     void print(AVLnode * &);
 34     void make_empty(AVLnode * &);
 35 };
 36 
 37 AVLtree::AVLtree()
 38 {
 39     head = NULL;
 40 }
 41 
 42 void AVLtree::insert_node(const int & para)
 43 {
 44     insert_node(para,head);
 45 }
 46 
 47 bool AVLtree::find_node(const int & para)
 48 {
 49     return find_node(para,head);
 50 }
 51 
 52 void AVLtree::print()
 53 {
 54     print(head);
 55 }
 56 
 57 void AVLtree::make_empty()
 58 {
 59     make_empty(head);
 60 }
 61 
 62 void AVLtree::insert_node(const int & para,AVLnode * &root)
 63 {
 64     if(!root)    //空树
 65     {
 66         AVLnode *p = (AVLnode *)malloc(sizeof(AVLnode));
 67         p->data = para;
 68         p->left = NULL;
 69         p->right = NULL;
 70         p->height = 0;
 71 
 72         root = p;    //使父节点指针指向新插入的节点
 73     }
 74     else
 75     {
 76         if(para < root->data)    //插入左子树
 77         {
 78             insert_node(para,root->left);
 79             if(height(root->left) - height(root->right) == 2)//不平衡，两种情况，(1)插入左子树的左子树，(3)插入左子树的右子树
 80             {
 81                 if(para < root->left->data)        //情况(1)
 82                     single_right(root);
 83                 else
 84                     double_LR(root);            //情况(3)
 85             }
 86         }
 87         else if(para > root->data)    //插入右子树
 88         {
 89             insert_node(para,root->right);
 90             if(height(root->left) - height(root->right) == -2)//不平衡，两种情况，(4)插入右子树的左子树，(2)插入右子树的右子树
 91             {
 92                 if(para < root->right->data)    //情况(4)
 93                     double_RL(root);
 94                 else
 95                     single_left(root);            //情况(2)
 96             }
 97         }
 98         else    //该值已存在，不作处理
 99         {}
100 
101         //更新节点高度信息
102         root->height = max(height(root->left),height(root->right)) + 1;
103     }
104 }
105 
106 bool AVLtree::find_node(const int &para,AVLnode * &root)
107 {
108     if(root->data == para)
109         return true;
110     else if(root->data > para && (root->left))
111         find_node(para,root->left);
112     else if(root->data < para && (root->right))
113         find_node(para,root->right);
114     else
115         return false;
116 }
117 
118 void AVLtree::single_left(AVLnode * &root)
119 {
120     AVLnode * temp = root->right;
121     root->right = temp->left;
122     temp->left = root;
123 
124     //修改节点高度
125     root->height = max(height(root->left),height(root->right)) + 1;
126     temp->height = max(height(temp->left),height(temp->right)) + 1;
127 
128     root = temp;    //更新根节点指针
129 }
130 
131 void AVLtree::single_right(AVLnode * &root)
132 {
133     AVLnode * temp = root->left;
134     root->left = temp->right;
135     temp->right = root;
136 
137     //修改节点高度
138     root->height = max(height(root->left),height(root->right)) + 1;
139     temp->height = max(height(temp->left),height(temp->right)) + 1;
140 
141     root = temp;    //更新根节点指针
142 }
143 
144 void AVLtree::double_LR(AVLnode * &root)
145 {
146     single_left(root->left);
147     single_right(root);
148 }
149 
150 void AVLtree::double_RL(AVLnode * &root)
151 {
152     single_right(root->right);
153     single_left(root);
154 }
155 
156 int AVLtree::height(AVLnode * root)
157 {
158     if(!root)
159         return -1;
160     else
161         return root->height;
162 }
163 
164 
165 void AVLtree::print(AVLnode * &root)
166 {
167     if(!root)
168         return;
169     else
170     {
171         print(root->left);
172         cout<<root->data<<endl;
173         print(root->right);
174     }
175 }
176 
177 void AVLtree::make_empty(AVLnode * &root)
178 {
179     if(!root)
180         return;
181     else
182     {
183         make_empty(root->left);
184         make_empty(root->right);
185         delete(root);
186     }
187     root = NULL;        //缺少这条语句会忘记释放父节点指向本节点的指针，导致重复释放内存，导致错误
188 }
189 
190 int main()
191 {
192     AVLtree a;
193     int array[7] = {5,6,8,3,2,4,7};
194     for(int i=0;i<7;i++)
195         a.insert_node(array[i]);
196     a.print();        //顺序输出数据
197 
198     cout<<a.find_node(7)<<endl;
199     cout<<a.find_node(5)<<endl;
200     cout<<a.find_node(11)<<endl;
201     a.make_empty();
202     return 0;
203 }

　　没有实现删除的算法。