1 ********二叉树及其遍历*********
  2 二叉树
  3 树 每一个节点有多个节点
  4 二叉树 每一个节点最多有两个节点 而且节点之间是有顺序的
  5 下面来分辨几个二叉树 只是通常的定义 可能不同教材的定义不一样
  6 
  7 满二叉树(Full Binary Tree)
  8 要么没有儿子,要么有两个儿子
  9 
 10 完全二叉树(Complete Binary Tree)
 11 从根节点到最后一个节点(注意是这二叉树的最后一个节点) 一直都有连续的点 没有空掉一个位置 的二叉树
 12 
 13 完美二叉树(Perfect BT)
 14 每个节点都塞满的二叉树,在不增加层数的情况下不可能再增加节点的二叉树,有的书也叫满二叉树
 15 
 16 为什么要区分这些?
 17 因为越接近完美的树性能越好,越接近链表的树(就拉直了变成一链表)性能越差。
 18 
 19 ****树与二叉树的顺序实现****
 20 我们要清楚,如果我们要去实现一个数据结构,逻辑上要能看得出这个结构原来的样子
 21 比如我们用数组实现一棵树的话,我们就得能从数组的结构上能脑补出来这棵树原来的样子
 22 那么怎样的树比较好用顺序存储,当参差不全的树存进数组的话,我们没法分清哪个点是谁的儿子,
 23 因为中间会有断开的点,那么我们干脆就把这棵树给补全成一棵完全二叉树,就没有断了
 24 然后又因为是二叉树,一个点后面两个点,就是它的儿子了,就能很容易看出来。
 25 那不完全行不行,也可以,那个位置没有点的话,就空着,那就完事了,但是这样会很浪费空间。
 26 所以如果不太接近完全二叉树的一般的树,不适合用数组去存储,接近完全二叉树的才会去用顺序实现。
 27 
 28 
 29 ****树与二叉树的链式实现****
 30 一般的树:我们不能确定有多少个节点,指针域的数目安排会有问题
 31          即使确定了,也可能有问题,比如根节点有一百个节点,但是下面的节点都最多只有4个,
 32          但是指针域只能安排最多的,所以100个会有96个浪费。
 33          那么我们想能不能用子节点去找父节点?每一个节点只要给一个指针域就好了,
 34          但是找儿子找孙子就很难了。
 35 
 36 至此,我们发现,一般的树这玩意真的很烦人,我们无比的怀念二叉树。
 37 采用一种方法,左下角的是儿子右下角的是兄弟,把一般的树变成二叉树就好了。
 38 这样的话我们就不用再纠结到底有几个儿子这样的问题了。
 39 
 40 二叉树:每个节点有两个指针域left right,其实也可以加多一个节点指向父亲,最终还是根据需求来决定结构。
 41 
 42 ****二叉树的遍历****
 43 巧记:前中右的区别就是根节点的访问次序
 44 前序遍历:先访问根节点,再按照前序遍历的顺序访问左子树,再按照前序遍历的顺序访问右子树
 45 中序遍历:用中序遍历的顺序访问左子树,然后访问树根,接着用中序遍历的顺序访问右子树
 46 后序遍历:先按照后序遍历的顺序访问左子树,然后后序遍历的顺序访问右子树,最后访问根节点
 47 
 48 还有一种访问遍历方式:层序遍历:每一层来访问 用队列存储访问过的点就好了 因为要先进先出(画个图走一遍就能看出来)
 49                               创建一个队列,然后把节点的指针入队...最后输出 就完事了
 50 
 51 ****二叉树的迭代遍历(非递归)****ps:迭代即循环
 52 递归的书写比较方便,逻辑容易懂。但是递归是函数不断调用自己来实现,会占用操作系统的栈内存,栈内存容量较少
 53 可能会栈溢出,不能递归的话我们就来模拟递归的过程。函数调用是压栈的过程,函数返回是弹栈的过程。
 54 那么我们自己写一个栈不就完了?确实。自己写的栈可以自定义空间大小,比操作系统调用栈要调用的层次要深。
 55 我们来看看三种遍历的实质是什么?实际上,三种递归其实都是从树根走下去的,但是第几次走过树根的时候才对其进行访问
 56 这就是遍历的实质,你可能路过这个节点,但是不一定就是这一次见面就要访问它,所以实际上三种遍历从走路顺序上都一样。
 57 故,我们只要适时保存走过的点,然后保存,并在应该访问的时候弹出,就好了。
 58 但是,如果按照上面说的,要到一定时候,就是第几次走过的时候才访问的话,就需要保存地址了,因为我们只有左右指针,
 59 而没有回去的指针。那用栈来保存我们的来路就好了。
 60 
 61 
 62 *******************
 63 ****二叉树的C++实现****(其实和JAVA差不多的,面向对象语言写出来的东西都差不多,JAVA的就不写了)
 64 #include<iostream>
 65 #include<stack>
 66 
 67 using namespace std;
 68 
 69 template<class Element>//二叉树的元素类型 类似于JAVA的泛型
 70 struct BinNode{
 71     Element data;
 72     BinNode<Element> *left;
 73     BinNode<Element> *right;
 74     BinNode(Element x){
 75         data = x;
 76         left = right = NULL;
 77     }
 78 };
 79 
 80 template<class Element>
 81 class BinTree{
 82     //有树根 我们就能抓住整一棵树
 83     protected:
 84         BinNode<Element> *root;//树根
 85         
 86         //中序遍历 先左子树后根节点最后右子树
 87         void rinprint(BinNode<Element> *r){
 88             if(r == NULL) return;
 89             rinprint(r->left);
 90             cout << r->data << ' ';
 91             rinprint(r->right);
 92         }
 93         //复习递归 递归,要有递归关系式,要有递归终止条件
 94         //另外要记住:凡是指针都可能出现NullPointerExcpetion,传入一个指针之后首先就要判断是不是空的
 95         void rpreprint(BinNode<Element> *r){
 96             if(r == NULL) return; //写了这个之后下面的递归不用判断是不是空的了
 97             cout << r->data << ' ';
 98             rpreprint(r->left);//即使在这里写上if(left),也照样要判断一次,反正空的时候进去就会直接return
 99             rpreprint(r->right);//判不判断其实省不了时间
100         }
101         //查找的内部递归函数
102         BinNode<Element> * rfindX(Element x, BinNode<Element> *r){
103             if(!r){//树是空的
104                 return NULL;
105             }
106             if(r->data == x) return r;
107             BinNode<Element> *found;
108             found = rfindX(x, r->left);
109             //如果在left找到了,就可以返回了,否则就找右树就完事
110             return found ? found : rfindX(x,r->right);
111         }
112 
113         
114         void rprint(BinNode<Element> *r, int depth){
115             for(int i = 0; i < depth; i ++){
116                 //多一层就多两个空格
117                 cout << "  ";
118             }
119             if(r == NULL) {
120                 cout << "[/]" << endl;
121                 
122             }
123             else{
124             cout << r->data << endl;
125             rprint(r->left, depth + 1);
126             rprint(r->right, depth + 1);
127             }
128         }
129 
130         //非递归
131         //迭代实现前序遍历
132         void ipreprint(BinNode<Element> *r){
133             //访问点 压栈 向左访问 这样的顺序
134             //用栈的目的,找到来路 希望栈弹出来元素之后下一步往哪里走
135             //如果stack<int>,弹出来之后,还要find这个int是在哪个位置,就不方便了
136             //如果压一个结点进去的话,不知道会压的是什么东西,可能会很低效,干脆就压一个地址就好了
137             stack<BinNode<Element>*> st;
138             if(r == NULL) return ;
139 
140             //for比较难写 可以先写while 条件也可以先假设 后期再改 写代码不是一蹴而就的
141             while(r){
142                 //前序遍历,走过去的时候就要打印了
143                 //打印 压栈 打印 压栈 不断循环...
144                 //顺序:每一个节点的根节点左子树右子树
145                 cout << r->data << ' ';
146                 st.push(r);
147                 r = r->left;
148                 //当左子树再往左走为空的时候 就开始弹出(注意弹的栈可能会空!!!就会失败)
149                 //if(r == NULL){ 为什么要把if改成while? 因为左子树走到底是空的之后
150                 //就要回到根节点,因为它的右儿子可能不是空的,要一直弹栈弹回去
151                 //而用if之后,当r是NULL就结束循环,下一步就把r赋值给了while,就终止了
152                 //而那个可能存在的整一棵树的树根的右儿子就打印不出来了
153                 //另外,为什么要加上st.empty()?就像上面说的,树根有一个右儿子,当这个右儿子最后一个入栈
154                 //同时,它也是最后一个弹出来的,然后就空了,遍历就结束了。
155                 while(r == NULL && !st.empty()){
156                     //要找到右边 先得到这个父节点
157                     //找到右边之后 就 访问点 压栈 向左访问 这样的顺序
158                     r = st.top();
159                     st.pop();
160                     r = r->right;
161                 }
162             }
163         }
164 
165         //中序遍历 迭代实现
166         //拿前序遍历的稍作修改就能实现了
167         //中序遍历和前序遍历的非递归都走的同样的路径,只是什么时候访问不一样
168         void ipreprint(BinNode<Element> *r){
169             stack<BinNode<Element>*> st;
170             if(r == NULL) return ;
171 
172             while(r){
173             //cout << r->data << ' '; 中序遍历是第二次经过才访问的
174                 st.push(r);
175                 r = r->left;
176                 //注意下面这个循环是直至左边为空的时候才会进入
177                 while(r == NULL && !st.empty()){
178                     r = st.top();
179                     st.pop();
180                 //当左边为空了,在我们向右走之前,就是第二次走到一棵树的树根,这时候就要访问了
181                     cout << r->data << ' ';
182                     r = r->right;
183                 }
184             }
185         }
186 
187         //后序遍历 迭代实现 留作练习
188         //这个就和前序和中序的那个函数很大不一样了
189         //因为每个元素要入栈两次,出栈两次,还需要压栈次数,如果是第二次弹栈,才需要访问
190         //解决方案:除了存指针的栈以外再stack<int> count这么一个次数栈
191         //第二个方法是,重新写一个struct,里面加入次数和结点的指针
192 
193     public:
194         BinTree(){root = NULL;}
195         BinTree(Element r){
196             //传入树根节点 类型应不应该是Element,还是BinNode?
197             //作为用户,我们只想要传入一个数据,而不会想去创建一个节点,所以,我们传入的是Elem
198             root = new BinNode<Element>(r);
199         }
200         //析构函数 释放树占用的内存
201         ~BinTree(){}
202         
203         //找到这个点并且返回地址
204         BinNode<Element>* findX(Element x){
205             // //查找就是一个遍历的过程
206             // //空树异常
207             // if(root != NULL) return NULL;
208             // //树根就是要找的
209             // if(root->data == x) return root;
210             // BinNode<Element> *found;
211             // // found = find()... 同时我们也要知道到底遍历的左右顺序,所以我们按照遍历的套路,写一个内部递归函数
212             // //由于我们有了rfindX,所以。。。上面写的东西全部作废.
213             return rfindX(x, root);
214         }
215 
216         //因为插入会有失败的情况 所以用bool
217         //父节点元素 插入位置 要插入的元素
218         bool insert(Element p, int LorR, Element x){
219             //首先我们要找到这个节点,然后再判断那个位置是不是能插入
220             //由于查找的操作比较频繁,所以我们要干脆封装成一个findX函数
221             BinNode<Element> *found;
222             //记住 找的是父节点 
223             found = findX(p);
224             if(!found) return false;
225             if(LorR == 0){
226                 if(found->left) return false;
227                 found->left = new BinNode<Element>(x);
228             }
229             else{
230                 if(found->right) return false;
231                 found->right = new BinNode<Element>(x);
232             }
233             return true;
234         }
235 
236         //遍历,就是打印,所以不用返回值
237         //参数在用户角度也是不需要提供的,因为我们就是调用一棵特定的树的前序遍历
238         //但是没有参数的话,我们在递归实现时候就会有麻烦,因为递归,必须有参数
239         //所以我们选择在内部实现前序遍历 rpreprint, preprint的话就只需要去调用就完事了
240         //前序遍历
241         void preprint(){
242            //递归实现遍历 rpreprint(root);
243            /***非递归 迭代实现遍历**/
244            ipreprint(root);
245            cout << endl;
246         }
247         //中序遍历
248         void inprint(){
249             //调用递归中序遍历函数
250             rinprint(root);
251         }
252 
253         void print(){
254             //因为要打印出不同节点的一定数量的空格,所以要知道节点的深度
255             rprint(root, 0);
256         }
257 
258         
259 
260 };
261 
262 int main(){
263     BinTree<int> bt(11);
264     //bt.preprint();//前序遍历打印树
265     bt.insert(11, 0, 22);//插入哪一个节点的子节点位置?左二子还是右儿子?现在规定flag左二子是0,右儿子是1
266     bt.insert(11, 1, 33);
267     bt.insert(22, 0, 44);
268     bt.insert(33, 0, 55);
269     //bt.preprint();
270     bt.preprint();//打印得比preprint打印得好看点 便于观察
271     /*打印成如图所示
272     11
273       22
274         44
275         [/]
276       33
277         55
278         [/]
279     */
280    bt.inprint();
281     return 0;
282 }
283 
284 实例:数叶子节点的个数 需要遍历整一棵树 看看哪些节点没有儿子
285     遍历:要么就递归,要么就循环迭代
286     protected:
287         int countLeaves(BinNode<Element> *r){
288             //空树无叶子
289             if(r == NULL){
290                 return 0;
291             }
292             //注意:当树只有树根自己一个 那么就只有它一个叶子
293             if(r->left == NULL && r->right == NULL){
294                 return 1;
295             }
296             //否则等于左子树的叶子+右子树的叶子
297             return countLeaves(r->left) + countLeaves(r->right);
298         }
299     public: 
300         int count(){
301             return countLeaves(root);
302         }
303 
304 ***二叉树一般用于查找操作,那么接下来来讲二叉搜索树(Binary Search Tree)***
305 左子树元素比树根小,右子树元素比树根大,左右子树都是BST
306 二叉树的查找效率是O(N),因为你可能要遍历到最后一个元素才能找到你要找的指定元素
307 而BST呢,来分析一下,首先要记住一个前提,所有的树都是从树根出发的。
308 FindMax FindMin FindX 实际都是同一个方法,不断的比较
309 当一棵树长的比较匀称的时候,左右两边的点都差不多的比较满,每次都是折半查找,是O(logN)
310 如果退化成一维的,比如只有右子树,实际上就已经是链表了,此时查找效率为O(N)
311 所以后来也衍生出来了一种树,会自动去调节平衡,叫平衡二叉搜索树,我们先说完二叉搜索树再去讲。
312 **插入与删除**
313 只要注意一个就好了:BST一般是不能存放重复的值的,如果插入的值里面有,就失败
314 另外的,插入一个数,如果找到了那个位置,那么这个位置本身是NULL的,插入就比较麻烦了
315 我们就要就地创建一个结点,然后给递归回去,返回当前这个新创建节点的地址,
316 然后赋值地址给父亲的儿子,才能挂上去父亲那里
317 我们也可以直接就找到这个位置的父亲,站在这个父亲节点,创建一个左儿子或者右儿子,然后再进行赋值,这样就好办多了
318 
319 删除,当父亲只有一个儿子,把父亲删除,就直接把后代继承过来就好了。
320 那么有两个儿子的怎么办?还有孙子呢?儿子直接拿过来就会直接一连串位置给空掉
321 那我们要找一个点代替这个父亲的话,肯定是从下面的点里取一个大小差不多中间的一个,
322 找左树的最大出来,那么原先的右树也是符合BST的大小规律的,原先的左树剩余的点也是符合大小规律的
323 右树的最小也是可以的。但,不论是左树最大还是右树最小,都有可能最多还有一个儿子(为什么是最多?
324 因为左树最大,它不可能还有右孩子,右树最小,也不可能还有左孩子是吧,由BST的大小排序确定)
325 那么我们就可以这样干,因为只有一个点了嘛,我们把这个父亲的数据往上一个删除的位置给覆盖之后,
326 再拿它的儿子来覆盖,就完事啦!因为只有一个儿子!!!
327 
328 
329 那么下面就来说一下二叉搜索树的代码
330 因为二叉搜索树是一棵二叉树,在CPP这种语言下,可以把上门写过的二叉树的代码作为.h文件引入来用就好
331 记得改为.h文件的时候删掉函数的具体实现,然后最开始加上预编译指令
332 #ifndef bintree_h
333 #define bintree_h
334 最后一行加上
335 #endif 
336 避免头文件被多次包含,多次展开
337 
338 
339 ********二叉搜索树实现********
340 //下面的代码的Elem可能会有点问题,因为上面用的是Element,有问题改一下就好了
341 #include<iostream>
342 #include"bintree.h"
343 
344 using namespace std;
345 
346 //同样地,元素类型也不是确定的,所以用模板(泛型)
347 template <class Elem>
348 //冒号是CPP的继承的语法 JAVA用extends就完事
349 class BSTree : public Bintree<Elem>{
350     protected:
351         //递归地寻找最大值
352         BinNode<Elem>* rfindMax(BinNode<Elem>* r){
353             if(r->right == NULL){//没儿子你不就是最大的吗hh
354                 return r;
355             }
356             return rfindMax(r->right); 
357             //这种在返回部分递归的,叫尾递归,效率较低
358             //如果修改不太麻烦,一般都可以改成循环
359         }
360 
361         //返回要插入的地址
362         BinNode<Elem>* rinsert(Elem x, BinNode<Elem>* r){
363            // r->left = rinsert(x, r->left); 这种写法不好,要是插入失败,返回空的时候,整一左树没了
364         //思路也是小于往左找,大于右边找,等于就失败,因为BST一般不要有相同的元素
365         //root 空呢?空就直接插入就完了
366             if(r == NULL){
367                 r = new BinNode<Elem>(x);
368                 if(!r) throw -1; //当因为内存不够时候,可能会在new的时候返回空
369             }
370             else if(x < r->data){
371                 r->left = rinsert(x, r->left);
372             }
373             else if(x > r->data){
374                 r->right = rinsert(x, r->right);
375             }
376             else throw -2;//用-1和-2分辨是插入失败还是内存太少创建失败
377             return r;
378         }
379 
380         BinNode<Elem>* remove(Elem x, BinNode<Elem> * r){
381             BinNode<Elem>* tmp;
382             //逻辑和查找是一样的 就小于往左边 大于往右边 等于直接删呗
383             //永远要记住!!!指针可能是空的
384             if(!r) throw -1;//空指针异常
385             else if(x < r->data){
386                 r->left = remove(x, r->left);
387             }
388             else if(x > r->data){
389                 r->right = remove(x, r->right);
390             }
391             else if(x == r->data){
392                 //return NULL; 注意 有可能有一个儿子,有可能两个儿子,有可能没有儿子
393                 if(r->left && r->right){
394                     //有两个儿子
395                     tmp = rfindMax(r->left);//tmp一定不为空 因为左儿子存在
396                     r->data = tmp->data;//拿左树最大覆盖要删除的位置
397                     r->left = remove(tmp->data, r->left)//然后把这个最大的值给删除 并且要更新左儿子!!!
398                 }
399                 else{
400                     //有儿子 或者 没有儿子
401                     //有一个儿子,不论是左儿子还是右儿子,先把左儿子or右儿子拿来覆盖,接着
402                     //都是把儿子的儿子节点挂过去给这个儿子
403                     //没有儿子,可以把它视为做拥有NULL儿子,道理是一样的,也是拿过来覆盖
404                     //所以可以不用那么多else if 全部合并到这个else里面 不需要分类讨论
405                     tmp = r;//因为要删除它 先暂时存一下地址
406                     r = r->left ? r->left : r->right;//全空时候也是NULL的
407                     //当执行完上一句之后,树根的地址就变成了左儿子or右儿子或者NULL
408                     //即使左儿子OR右儿子还有儿子!!! 因为变的是地址!!!不用再进行操作了
409                     //原来是连着的点依然是连着的!!!
410                     delete tmp;
411                 }
412             }
413 
414             return r;
415         }
416     public:
417         BSTree(){
418             this->root = NULL;
419         }
420         //如果返回值是Elem,返回一个值,就不能给这个节点做一个改动
421         //另外还有一个弊端,如果是空的,只能抛出异常,而不能返回一个NULL值
422         //所以把返回值改为了返回节点的地址,但是改为地址也有弊端,可能会改动树的结构..
423         BinNode<Elem>* findMax(){//findMax不需要参数,因为就是在这棵树上面进行findMax
424            // return rfindMax(this->root); 尾递归效率较低
425            //修改为循环版本
426            //一路向右,怎样才会向右,指针不空
427            //用一个临时指针保存树根 因为我们不能改变树根
428            //if(this->root == NULL) return NULL;//空树 直接返回 写在下面循环语句也行 效率差不太多
429            BinNode<Elem>* tmp = this->root;
430            //谨记用指针之前要保证指针不空 因为有可能一开始就是空的,所以要增加tmp &&
431            while(tmp && tmp->right){
432                tmp = tmp->right;
433            }
434            return tmp;
435         }
436         //找最小和找最大是完全对称的,照着上面写就完事了
437         BinNode<Elem>* findMin(){
438             if(this->root == NULL) return NULL;
439             BinNode<Elem> *tmp = this->root;
440             while(tmp->left){
441                 tmp = tmp->left;
442             }
443             return tmp;
444         }
445         //找特定的值
446         BinNode<Elem>* findX(Elem x){
447             //findMin findMax肯定能找出来值,找特定值findX的话不一定
448             BinNode<Elem>* tmp = this->root;
449             //要确定root是不是空的
450             //但是没必要写的像上面一开始就判断树根是不是为空
451             //因为我们还有可能找不到这个x,那时候也是返回空,集中起来写,尽量避免多个return(多出口)
452             while(tmp){
453                 if(x == tmp->data) break;//写在循环条件也行 && x != tmp->data
454                 if(x < tmp->data) tmp = tmp->left;
455                 if(x > tmp->data) tmp = tmp->right;
456             }
457 
458             return tmp;
459         }
460         bool insert(Elem x){
461             //因为只有元素x,一棵树的操作要和树根挂钩,所以要在内部写一个函数
462             //注意,肯定是赋值给this->root,因为你有可能是从一棵不空树去insert变成一棵树
463             try{
464                 this->root = rinsert(x, this->root);
465             }
466             catch(int e){
467                 return false;
468             }
469             return true;
470         }
471         //找不到这个要删除的点的话就会失败 所以bool作为返回值
472         //下面写的是递归的remove 迭代的留作练习
473         bool remove(Elem x){
474             try{
475                 //删除以后返回树根地址 更新一下树
476                 //在这里函数名字一样是可以的,重载(overload)就完事
477                 this->root = remove(x, this->root);
478             }
479             catch(int e){
480                 //为什么不以返回空指针作为删除失败的标志?当树根只有一个点的话,你删除了不就NULL了
481                 //所以返回NULL 不一定就是删除失败
482                 return false;
483             }
484             return true;
485         }
486 };
487 
488 int main(){
489     BSTree<int> bt;
490     cout << bt.findMax() << endl;
491     bt.insert(10);//作为使用者,当然希望只有一个参量,就是插入的参量
492     bt.insert(5);
493     bt.insert(20);
494     bt.insert(8);
495     bt.insert(15);
496     bt.insert(2);
497     bt.insert(6);
498     bt.print();
499     cout << bt.findX(6) << endl;
500     cout << "-----------" << endl;
501     //bt.remove(20);
502     //bt.remove(15);
503     //bt.remove(10);
504     //bt.remove(5);
505     return 0;
506 }
507 
508 *********平衡二叉搜索树(AVL树)**********
509 为什么需要这种东西?AVL树可以加快搜索的速度,而且这棵树经常会被删除和插入进行修改
510 首先是一棵二叉搜索树,然后是自平衡的一棵树。
511 那么我们来看一下平衡的定义:
512                         1.空树是平衡的
513                         2.当树是非空的时候,左右子树平衡且左右子树高度差绝对值<=1时候也是平衡的
514 平衡因子:这个节点的左右子树的高度差; 空树的高度定义为-1
515 所以,AVL树每个节点的平衡因子为-1 0 1三个
516 在此,我们定义树根深度为0,每个叶子高度为0,向上生长,所以一棵树的高度就是这个节点到它的叶子节点的最高的高度
517 也就是每一棵树的高度为节点树根的高度
518 AVL树的查找效率为O(lnN)
519 
520 插入和删除,AVL树的插入和删除会时刻保持平衡,这就是它的特点
521 那么如何调节平衡,这就是问题了。我们可以去想象,一棵树的节点是可以拉起来的,
522 例如   20   
523     10
524 插入5,5会在左边插入,也即左子树的左子树插入,导致20这个节点的平衡因子会变成2
525        20                             10
526     10                          5           20 
527   5             拉起来,                         这样的话每个节点的平衡因子都变成了0
528 又因为是左子树的左子树上插入的节点导致不平衡,调节的方式就定义叫左左单旋,记成LL单旋就好,
529 因为这命名方式有点反人类,明明是clockwise顺时针往右边旋转,却叫TMD左左单旋(LL Rotation)。。。
530 左左单旋的一般情况如图   A                                      B 
531                     B      AR(A的RIGHT)  ->把B转上去       BL       A
532                 BL    BR                                  插入    BR   AR 
533                插入                        原先的BR就由A来收养,A降级变成B的右儿子,由图就能看到高度相对平衡
534 由上述的方法可以衍生出一堆方法,就是观察每个节点的平衡因子,然后尽量把高的给拧下来,低的上去,而且不能破坏BST结构(左小右大)
535 拧到这棵树能平衡,注意上面在左子树的左子树插入时候,左子树的右子树并没有升高高度.
536 示意图如图所示:注意图形带高度
537 
538 又例如:      10
539           5      20
540        2    9           ->观察到10的平衡因子在插入之后变成了2,把5移上去是行不通的,当5上去的时候,把9给10当左儿子
541           6(新插入)        接着,5的平衡因子又会因为6的插入变成了-2,那么我们的目的依然是,要把10拉下来,还可以拉谁上去?
542                             毕竟我们不能破坏BST左小右大的结构,我们可以尝试把9拉上去
543 该操作叫做左右双旋(LR双旋),因为在树根的左子树的右子树发生,9和10都要旋转,然后把新插入9的6扔给了9原先的父节点5,
544              9
545           5     10
546         2   6      20
547 
548 一般情况示意图如图所示,我们要插入CL或者CR位置,然后的话那个图形就会变高,接着要想办法把这两位置变高的点拉上去
549 但是BL不改变高度,把B拉上去,BL会提高,目的达不到,所以只能把C拉上去,实际上就是一个,先把B左子树给拉平衡,
550 然后把A给拉平衡,也就是B为根节点的右右单旋后(注意动的只是左子树),然后进行A为根节点的左左单旋,就完事啦!
551 
552 同理RL双旋和LR双旋是对称了,就不讲了。故一共有左左 右右 左右 右左 这四种(在哪个位置)旋转方式实现AVL的自平衡。
553 
554 最后来讲一下AVL树的删除,一般不推荐说AVL树进行删除,因为可能会破坏AVL树的平衡性,然后又要调
555 当AVL树的删除不太频繁的时候,我们采取一种lazy deletion的操作,也就是在BinNode中加入一项标志删除的flag
556 如果要删除,这个点不用做替换,也不用做平衡,只要把删除flag标记上true就好。
557 一般来说AVL树大多是用来增加和查找,也就是插入和遍历。。删除的话比较少。
558 如果是经常需要删除,那还不推荐用AVL树这种结构。
559 
560 *****AVL树的代码实现*****
561 事先把BST弄成BSTREE.h
562 
563 #include<iostream>
564 #include<algorithm>
565 #include"bstree.h"
566 
567 using namespace std;
568 
569 template<class Elem>
570 class AVLTree : public BSTree<Elem>{
571     //要计算高度
572     /*
573     在bstree.h中的BinNode结构体增加高度
574     struct BinNode{
575         Elem data;
576         int h;
577         BinNode<Elem> *left;
578         BinNode<Elem> *right;
579         BinNode(Elem x){
580             data = x;
581             left = right = NULL;
582             h = 0;
583         }
584     }
585     */
586    protected:
587             //计算高度函数 内部使用 不用public
588             int height(BinNode<Elem> *r){
589                 if(!r) return -1;//空树
590                 return r->h;
591             }
592             //虚函数 动态联编(说实话我也不知道是什么反正看得懂逻辑代码就完事了。。。)
593             virtual BinNode<Elem>* rinsert(Elem x, BinNode<Elem>* r){
594                 //大的框架是一样的,不一样的是,插入之后要调节平衡
595                 //把调平衡的单独拎出去作为函数使用
596                 if(r == NULL){
597                     //在空树插入不会导致不平衡
598                     r = new BinNode<Elem>(x);
599                     if(!r) throw -1;//空的 内存不够 创建失败
600                 }
601                 else if(x < r->data) {
602                     r->left = rinsert(x, r->left);
603                     //在左边插入,会让左边高,所以用左子树高度减去右子树的高度
604                     if(height(r->left) - height(r->right) == 2){
605                         //不平衡
606                         //然后判断是左子树的左边还是左子树的右边插入
607                         if (x < r->left->data)//在左子树的左边
608                         {
609                             r = LLrotate(r);
610                         }
611                         else //在左子树的右边
612                         {
613                             r = LRrotate(r);
614                             //这么一看,把操作定义为在哪里插入而进行的操作命名还挺方便的。。。
615                         }
616                     }
617                 }
618                 else if(x > r->data) {
619                     r->right = rinsert(x, r->right);
620                     //同理,在右边插入,会让右边的高度可能大于左边的高度
621                     if(height(r->right) - height(r->left) == 2){
622                         if(x < r->right->data){
623                             //在右子树的左边
624                             r = RLrotate(r);
625                         }
626                         else{
627                             //否则就在右子树的右边咯
628                             r = RRrotate(r);
629                         }
630                     }
631                 }
632                 else throw -2;
633                 //记得计算节点的高度
634                 //rinsert是个递归函数,只要递归下去,就会从头到尾把所有节点高度计算一遍
635                 //所以下面的不只是计算当前根节点的高度,递归调用时候就会把每个节点的高度计算好
636                 r->h = max(height(r->left),height(r->right)) + 1;
637                 return r;
638             }
639 //忘了怎么写就画图 自己转一下
640             BinNode<Elem>* LLrotate(BinNode<Elem>* r){
641                 //把child顶上去 把r弄下来 顺时针旋转
642                 BinNode<Elem>* child;
643                 child = r->left;
644                 //首先,在左子树,所有的节点数据会比树根小,所以是放给树根的左儿子
645                 //其次,可能会疑惑,直接丢给它,那原来的左儿子呢,诶,这就要看上一句啦!
646                 //child=r->left;已经临时保存了树根的左儿子,所以左儿子的东西不会丢失!
647                 r->left = child->right;
648                 child->right = r;
649                 //****注意!!!转好了 但是高度已经发生变化了
650                 //为什么非得用height?不直接用r->h?因为懒- -懒得分析r是不是空的,r是空的话,r->h就没了。。
651                 r->h = max(height(r->left),height(r->right)) + 1;
652                 child->h = max(height(child->left),height(child->right)) + 1;
653                 /****返回平衡后的树根!!!***/
654                 return child;
655             }
656             BinNode<Elem>* RRrotate(BinNode<Elem>* r){//逆时针旋转
657                 //RR和LL左右对称,反着写就完事了
658                 BinNode<Elem>* child;
659                 child = r->right;
660                 r->right = child->left;
661                 child->left = r;
662                 r->h = max(height(r->left),height(r->right)) + 1;
663                 child->h = max(height(child->left),height(child->right)) + 1;
664                 /****返回后来的树根!!!!!***/
665                 return child;
666             }
667             BinNode<Elem>* LRrotate(BinNode<Elem>* r){
668                 //先进行一下左子树的右右旋转
669                 //然后进行一下整一棵树的树根的左左旋转
670                 //高度不用再进行计算了,因为在RR/LL rotate中都已经算过一次了 所以不用再进行计算
671                 r->left = RRrotate(r->left);
672                 r = LLrotate(r);
673                 //因为上面LL的时候已经把树根更新了 所以下面直接返回的是r
674                 /****返回r!!!***/
675                 return r;
676             }
677             BinNode<Elem>* RLrotate(BinNode<Elem>* r){
678                 r->right = LLrotate(r->right);
679                 r = RRrotate(r);
680                 /****返回r!!!***/
681                 return r;
682     public:
683             AVLTree(){
684                 this->root = NULL;
685             }
686             //原先的insert不用重写 逻辑都是递归逻辑插入 但是rinsert要重写
687             //记得写析构函数...
688             ~AVLTree(){
689                 //...不写了 我是懒狗
690             }
691 };
692 
693 int main(){//调试
694     AVLTree<int> t;
695     t.insert(10);
696     t.insert(20);
697     t.print();
698     cout << "----------" << endl;
699     t.insert(30);
700     return 0;
701 }

 

内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/GDUFdebuger/p/15057126.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!