平衡二叉树:一颗空树,或者是具有以下性质的二叉树
- 左子树和右子树都是平衡二叉树
- 左子树和右子树的深度只差不超过1
把二叉树节点的平衡因子BF(Balance Factor)定义为该节点的左子树深度减去右子树深度,则平衡二叉树所有结点的平衡因子只能是-1,0,1。只要有一个结点的平衡因子绝对值大于一就是不平衡的;
平衡二叉树的构造
对二叉树结点做一下定义,bf用来记录结点的平衡因子
1 typedef struct BSTNode{
2 int val;
3 int bf;
4 struct BSTNode *lchild, *rchild;
5 }BSTNode, *BSTree;
在插入新结点的过程中,会出现平衡因子绝对值大于2的情况,这时就需要进行一定的条件,让二叉树保持平衡。失去平衡后进行的调整规律可以归纳为以下四种
- 单项右旋处理
- 单项左旋处理
- 双向(先左后右)旋转处理
- 双向(先右后左)旋转处理
单项右旋处理, p为失去平衡的结点。右旋的思路就是
1 void R_Roate(BSTree& p){
2 BSTree temp = p->lchild;
3 p->lchild = temp->rchild;
4 temp->rchild = p;
5 p = temp;
6 }
向二叉树中插入结点:先找到结点插入的位置,建立该结点。调整相关结点的平衡因子。若导致结点失去平衡则需要进行选择,让二叉树恢复平衡。 如何找到新结点插入位置? 如果val的值比当前结点的值小,则继续在当前结点的左子树中寻找插入位置。 如果val的值比当前结点的值大,则继续在当前结点的右子树中寻找插入位置。直到找到一个空的位置位置。当然如果发现存在相同的val,则表示已经存在于二叉树中, 插入失败; 那么又如何判断二叉树是否失去平衡呢? 当当前结点的平衡因子是0的时候,表示该节点左右两边的高度一致,插入一个结点并不会改变当前结点的平衡性,但是会改变当前结点的平衡因子; 当当前结点的平衡因子为1的时候,表示当前节点的左子树比右子树高, 若在当前结点左边插入结点, 必定会导致当前结点的左子树高度和右子树高度相差大于2. 引起不平衡。需要进行旋转来让二叉树恢复平衡, 如果在右子树插入结点,又会让当前结点的的平衡因子变为0;平衡因子为-1的分析过程和前面类似。 参数taller用来标志插入新结点是否让二叉树高度增加, 可以减少程序的计算量
1 bool InsertAVL(BSTree& T, int val, bool& taller){
2 if(!T){//插入新结点,树变高
3 T = (BSTree) malloc(sizeof(BSTNode));
4 T->val = val; T->bf = EH; T->lchild = T->rchild = NULL;
5 taller = true;
6 }else{
7 if(val==T->val){taller = false; return false;} //如果val存在于二叉树中, 则插入失败
8 if(val<T->val){ //若果val比当前结点的值小,则把新结点插入到当前结点的左子树中
9 if(!InsertAVL(T->lchild, val, taller)) return false;
10 if(taller){
11 switch(T->bf){ //插入新结点后要对当前结点的平衡因子做出相应的修改
12 case LH:{LeftBalance(T); taller=false; break;}
13 case EH:{taller = true; T->bf = LH; break;}
14 case RH:{taller = false; T->bf = EH; break;}
15 }}
16 }else{
17 if(!InsertAVL(T->rchild, val, taller)) return false;
18 if(taller){
19 switch(T->bf){
20 case LH:{T->bf = EH; taller = false; break;}
21 case EH:{T->bf = RH; taller = true; break;}
22 case RH:{RightBalance(T); taller = false; break;}
23 }}
24 }
25 }
26 return true;
27 }
全部代码
1 #include<iostream>
2 using namespace std;
3 /*
4 author: Lai XingYu
5 date: 2018/5/18
6 describe: AVL
7 */
8 #define LH +1
9 #define EH 0
10 #define RH -1
11
12 typedef struct BSTNode{
13 int val;
14 int bf;
15 struct BSTNode *lchild, *rchild;
16 }BSTNode, *BSTree;
17
18 void R_Roate(BSTree& p){
19 BSTree temp = p->lchild;
20 p->lchild = temp->rchild;
21 temp->rchild = p;
22 p = temp;
23 }
24
25 void L_Roate(BSTree& p){
26 BSTree temp = p->rchild;
27 p->rchild = temp->lchild;
28 temp->lchild = p;
29 p = temp;
30 }
31
32 void LeftBalance(BSTree& T){
33 BSTree temp = T->lchild;
34 switch(temp->bf){
35 case LH:{T->bf = temp->bf = EH; R_Roate(T); break;}
36 case RH:{
37 BSTree t = temp->rchild;
38 switch(t->bf){
39 case LH:{temp->bf = EH; T->bf = RH; break;}
40 case EH:{temp->bf = EH; T->bf = EH; break;}
41 case RH:{temp->bf = LH; T->bf = EH; break;}
42 }
43 t->bf = EH;
44 L_Roate(T->lchild);
45 R_Roate(T);
46 }
47 }
48 }
49
50 void RightBalance(BSTree& T){
51 BSTree temp = T->rchild;
52 switch(temp->bf){
53 case LH:{
54 BSTree t = temp->lchild;
55 switch(t->bf){
56 case LH:{T->bf = EH; temp->bf = RH; break;}
57 case EH:{T->bf = EH; temp->bf = EH; break;}
58 case RH:{T->bf = LH; temp->bf = EH; break;}
59 }
60 t->bf = EH;
61 R_Roate(T->rchild);
62 L_Roate(T);
63 }
64 case RH:{T->bf = temp->bf = EH; L_Roate(T); break;}
65 }
66 }
67
68 /*
69 taller标志插入新结点后,树的高度是否变高
70 如果val在二叉树中,则插入失败
71 如果插入结点让二叉树失去平衡,则要进行选择处理,让二叉树恢复平衡
72 */
73 bool InsertAVL(BSTree& T, int val, bool& taller){
74 if(!T){//插入新结点,树变高
75 T = (BSTree) malloc(sizeof(BSTNode));
76 T->val = val; T->bf = EH; T->lchild = T->rchild = NULL;
77 taller = true;
78 }else{
79 if(val==T->val){taller = false; return false;} //如果val存在于二叉树中, 则插入失败
80 if(val<T->val){ //若果val比当前结点的值小,则把新结点插入到当前结点的左子树中
81 if(!InsertAVL(T->lchild, val, taller)) return false;
82 if(taller){
83 switch(T->bf){ //插入新结点后要对当前结点的平衡因子做出相应的修改
84 case LH:{LeftBalance(T); taller=false; break;}
85 case EH:{taller = true; T->bf = LH; break;}
86 case RH:{taller = false; T->bf = EH; break;}
87 }}
88 }else{
89 if(!InsertAVL(T->rchild, val, taller)) return false;
90 if(taller){
91 switch(T->bf){
92 case LH:{T->bf = EH; taller = false; break;}
93 case EH:{T->bf = RH; taller = true; break;}
94 case RH:{RightBalance(T); taller = false; break;}
95 }}
96 }
97 }
98 return true;
99 }
100
101 void inorder(BSTree T){
102 if(!T) return;
103 if(T->lchild) inorder(T->lchild);
104 cout<<T->val<<" ";
105 if(T->rchild) inorder(T->rchild);
106 }
107 int main(){
108 int t[] = {1,2,3,4,5,6,7};
109 int f[] = {1,2,5,3,7,6,4};
110 BSTree T = NULL;
111 bool taller;
112 for(int i=0; i<7; i++) InsertAVL(T, f[i], taller);
113 inorder(T);
114 return 0;}
inorder()遍历一颗二叉树,得到的序列一定是单调的。
通过上面的例子可以看到,用相同的数字,不同顺序的序列来构建平衡二叉树,得到的结果是一样的。
平衡二叉树可以让二叉树的高度保持在Logn; 查找任何一个结点,需要进行的比较次数也不会超过logn。
但是如果构建avl的结点是降序的,会对二叉树进行多次选择,带来的开销也是非常大的。
原文链接: https://www.cnblogs.com/mr-stn/p/9058567.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/274298
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!