《数据结构和算法》——平衡二叉树

luciferzf

平衡二叉树：对比于二叉排序树对于时间复杂度的不可控制，平衡二叉树有个更加稳定的时间复杂度。我们构建了一个左右子树平衡的二叉树，使每个节点的左、右二叉树的深度差值不超过1，便于遍历。
构建过程：在构建时，除了需要按照排序二叉树的构建原则，使节点的左子树的数据小于节点的数据，节点右子树的数据大于节点的数据。同时，在添加数据时，我们需要对二叉树每个节点进行一个判定，若出现一个节点的平衡因子<=-2，则将该部分进行一次左旋转，若平衡因子大于2，则进行一次右旋转。需要注意的是，若出现几个节点的平衡因子正负号不同，则需要对平衡因子正负不同的几个节点的子树进行旋转，而不能只对几个节点统一只做一次大的旋转。
代码实现：我们利用递归的办法，先根据二叉排序树的规则将新的数据插入二叉树，然后判断一次“长高”部分的节点的平衡因子是否失衡，若失衡我们则需要对失衡部分进行旋转。先对节点进行平衡因子的调整和判断，若节点的左（右）子树的平衡因子不为0，我们只需要做一次旋转即可，否则需要进行两次旋转

1. #include<cstdio>
   
2. #include<cstdlib>
   
3. #include<iostream>
   
4. using namespace std;
   
5. 
   
6. class Bitnode
   
7. {
   
8. public:
   
9.         int data;
   
10.         int bf=0;
    
11.         Bitnode *lchild = NULL, *rchild = NULL;
    
12. };
    
13. 
    
14. void L_rotate(Bitnode *&P)
    
15. {
    
16.         Bitnode *L=P->lchild;
    
17.         P->rchild = L->lchild;
    
18.         L->rchild = P;
    
19. }
    
20. void R_rotate(Bitnode *&P)
    
21. {
    
22.         Bitnode *L = P->rchild;
    
23.         P->lchild = L->rchild;
    
24.         L->lchild = P;
    
25. }
    
26. 
    
27. void LeftB(Bitnode *&T)
    
28. {
    
29.         Bitnode *L = T->lchild, *Lr = NULL;
    
30.         switch (L->bf)
    
31.         {
    
32.         case 1:
    
33.                 T->bf = L->bf = 0;
    
34.                 R_rotate(T);
    
35.                 break;
    
36.         case -1:
    
37.                 Lr = L->rchild;
    
38.                 switch (Lr->bf)
    
39.                 {
    
40.                 case 1:
    
41.                         T->bf = -1;
    
42.                         L->bf = 0;
    
43.                         break;
    
44.                 case 0:
    
45.                         T->bf = L->bf = 0;
    
46.                         break;
    
47.                 case -1:
    
48.                         T->bf = 0;
    
49.                         L->bf = 1;
    
50.                         break;
    
51.                 }
    
52.                 Lr->bf = 0;
    
53.                 L_rotate(T->lchild);
    
54.                 R_rotate(T);
    
55. 
    
56.         }
    
57. }
    
58. 
    
59. void RightB(Bitnode *&T)
    
60. {
    
61.         Bitnode *R = T->rchild, *Rl = NULL;
    
62.         switch (R->bf)
    
63.         {
    
64.         case 1:
    
65.                 T->bf = R->bf = 0;
    
66.                 L_rotate(T);
    
67.                 break;
    
68.         case -1:
    
69.                 Rl = R->lchild;
    
70.                 switch (Rl->bf)
    
71.                 {
    
72.                 case 1:
    
73.                         T->bf = -1;
    
74.                         R->bf = 0;
    
75.                         break;
    
76.                 case 0:
    
77.                         T->bf = R->bf = 0;
    
78.                         break;
    
79.                 case -1:
    
80.                         T->bf = 0;
    
81.                         R->bf = 1;
    
82.                         break;
    
83.                 }
    
84.                 Rl->bf = 0;
    
85.                 R_rotate(T->lchild);
    
86.                 L_rotate(T);
    
87. 
    
88.         }
    
89. }
    
90. 
    
91. int InsertAVL(Bitnode *&T,int e,int *is)
    
92. {
    
93.         if (T == NULL)
    
94.         {
    
95.                 T = new Bitnode;
    
96.                 T->data = e;
    
97.                 *is = true;
    
98.                 return true;
    
99.         }
    
100.         else
     
101.         {
     
102.                 if (e == T->data)
     
103.                 {
     
104.                         *is = false;
     
105.                         return false;
     
106.                 }
     
107.                 if (e < T->data)
     
108.                 {
     
109.                         if (!InsertAVL(T->lchild, e, is))
     
110.                         {
     
111.                                 return false;
     
112.                         }
     
113.                         else
     
114.                         {
     
115.                                 if (*is)
     
116.                                 {
     
117.                                         switch (T->bf)
     
118.                                         {
     
119.                                         case 1:
     
120.                                                 LeftB(T);//左旋节点
     
121.                                                 *is = false;
     
122.                                                 break;
     
123.                                         case 0:
     
124.                                                 T->bf = 1;
     
125.                                                 *is = true;
     
126.                                                 break;
     
127.                                         case -1:
     
128.                                                 T->bf = 0;
     
129.                                                 *is = false;
     
130.                                                 break;
     
131.                                         }
     
132.                                 }
     
133.                         }
     
134.                        
     
135.                 }
     
136.                 else
     
137.                 {
     
138.                         if (!InsertAVL(T->rchild, e, is))
     
139.                         {
     
140.                                 return false;
     
141.                         }
     
142.                         if (*is)
     
143.                         {
     
144.                                 switch (T->bf)
     
145.                                 {
     
146.                                 case -1:
     
147.                                         RightB(T);
     
148.                                         *is = false;
     
149.                                         break;
     
150.                                 case 0:
     
151.                                         T->bf = -1;
     
152.                                         *is = true;
     
153.                                         break;
     
154.                                 case 1:
     
155.                                         T->bf = 0;
     
156.                                         *is = false;
     
157.                                         break;
     
158.                                 }
     
159.                         }
     
160.                 }
     
161.         }
     
162. }

复制代码