Penney's Blogs

言必行，行必果

0%

树结构_平衡二叉树

发表于 分类于 Valine：
本文字数： 3.7k 阅读时长 ≈ 3 分钟

树结构 - 平衡二叉树结构及其操作

结构 AVLNode - Position - AVLTree
  1. 结点的数据Data
  2. 结点的左子树
  3. 结点的右子树
  4. 以当前结点为根的树高
将X插入平衡树(递归实现)
  1. 如果为空则说明找到需要插入的位置
  2. 动态申请新结点AVLNode,将待插值X赋值给新结点T
  3. 初始化左右子树为NULL,树高为1
  4. 如果X比结点元素值小，则向左搜索插入点
  5. 如果平衡因子(左-右)大于等于2，需要左旋
  6. 如果插入点在左子树的左边，则单左旋，在左子树的右边则进行左-右旋
  7. 如果X比结点元素值大，则向右搜索插入点
  8. 如果平衡因子(左-右)大于等于2，需要右旋
  9. 如果插入点在右子树的右边，则单右旋，在右子树的左边则进行右-左旋
左单旋
  1. 结点A必须有一个左子结点，将A与B做左单旋，更新A与B的高度
  2. 将B的右子树挂在A的左子树上，B不在为A左子树， 如果B有右子树的话
  3. A作为B的右子树，完成左旋
  4. 重新计算树A,B高度
  5. B为新的根结点
右单旋
  1. A必须有右子树，将A与B右单旋
  2. 将右子树B的左边挂在根结点A的右为，B不再为A的右结点
  3. 将A作为B的左子树
  4. 重新的计算树高度
  5. B为新的根结点
左 - 右双旋
  1. 先以左子树为根结点右旋转
  2. 后以发现者为根结点左旋转
右 - 左双旋
  1. 先以右子树为根结点进行左旋转
  2. 再以发现者为根结点右旋转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <stdlib.h>

typedef struct AVLNode *Position;
typedef Position AVLTree;
typedef int ElementType;

struct AVLNode {
    // 1.结点的数据Data
    ElementType Data;
    // 2.结点的左子树
    AVLTree Left;
    // 3.结点的右子树
    AVLTree Right;
    // 4.以当前结点为根的树高
    int Height;
};

int GetHeight(AVLTree AT);

AVLTree SingleLeftRotation(AVLTree A);

AVLTree SingleRightRotation(AVLTree A);

AVLTree DoubleLeftRightRation(AVLTree A);

AVLTree DoubleRightLeftRotation(AVLTree A);

int Max(int a, int b) {
   return a > b ? a : b;
}

/**
* 将X插入到树A中,递归实现
* @param A
* @param X
* @return
*/
AVLTree Insert(AVLTree T, ElementType X) {
   // 1.如果为空则说明找到需要插入的位置
   if (!T) {
       // 2.动态申请新结点AVLNode,将待插值X赋值给新结点T
       T = (AVLTree) malloc(sizeof(struct AVLNode));
       T->Data = X;
       // 3.初始化左右子树为NULL,树高为1
       T->Height = 1;
       T->Left = T->Right = NULL;
   } else if (X < T->Data) {
       // 4.如果X比结点元素值小，则向左搜索插入点
       T->Left = Insert(T->Left, X);
       // 5.如果平衡因子(左-右)大于等于2，需要左旋
       if (GetHeight(T->Left) - GetHeight(T->Right) == 2) {
           // 6.如果插入点在左子树的左边，则单左旋，在左子树的右边则进行左-右旋
           // T为发现者
           if (X < T->Left->Data) {
               T = SingleLeftRotation(T);
           } else {
               T = DoubleLeftRightRation(T);
           }
       }
   } else if (X > T->Data) {
       // 7.如果X比结点元素值大，则向右搜索插入点
       T->Right = Insert(T->Right, X);
       // 8.如果平衡因子(左-右)大于等于2，需要右旋
       if (GetHeight(T->Left) - GetHeight(T->Right) == 2) {
           // 9.如果插入点在右子树的右边，则单右旋，在右子树的左边则进行右-左旋
           if (X > T->Right->Data) {
               T = SingleRightRotation(T);
           } else {
               T = DoubleRightLeftRotation(T);
           }
       }
   }/* else{
       X = T->Data;// 无需要插入
   }*/

   return T;
}

/**
* 左-右双旋
* 破坏结点在发现者的左子树的右子树上，
* 先以左子树为根结点进行右旋转再发现者为根结点进行左旋转
* @param A
* @return
*/
AVLTree DoubleLeftRightRation(AVLTree A) {
   // 1.先以左子树为根结点右旋转,后以发现者为根结点左旋转
   A->Left = SingleRightRotation(A->Left);
   return SingleLeftRotation(A);
}

/**
* 右-左双旋
* 破坏者在发现者的右子树的左子树上，
* 先以右子树为根结点进行左旋转，再以发现者为根结点进行右旋转
* @param A
* @return
*/
AVLTree DoubleRightLeftRotation(AVLTree A) {
   // 1.先以右子树为根结点进行左旋转，再以发现者为根结点右旋转
   A->Right = SingleLeftRotation(A->Right);
   return SingleRightRotation(A);
}

/**
* 左单旋转
* @param A
* @return
*/
AVLTree SingleLeftRotation(AVLTree A) {
   // 1.结点A必须有一个左子结点，将A与B做左单旋，更新A与B的高度
   AVLTree B = A->Left;
   // 2.如果B有右子树的话,将B的右子树挂在A的左子树上，B不在为A左子树
   A->Left = B->Right;
   // 3.A作为B的右子树，完成左旋
   B->Right = A;
   // 4.重新计算树A,B高度
   A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
   B->Height = Max(GetHeight(B->Left), GetHeight(B->Right)) + 1;
   // 5.B为新的根结点
   return B;
}

/**
* 右单旋转
* @param A
* @return
*/
AVLTree SingleRightRotation(AVLTree A) {
   // 1.A必须有右子树，将A与B右单旋
   AVLTree B = A->Right;
   // 2.将右子树B的左边挂在根结点A的右为，B不再为A的右结点
   A->Right = B->Left;
   // 3.将A作为B的左子树
   B->Left = A;
   // 4.重新的计算树高度
   A->Height = Max(GetHeight(A->Left), GetHeight(A->Right)) + 1;
   B->Height = Max(GetHeight(B->Left), GetHeight(B->Right)) + 1;
   return B;
}

/**
* 获取平衡二叉树的高度,递归
* @param AT
* @return
*/
int GetHeight(AVLTree AT) {
   int HL, HR, Max;
   if (AT) {
       HL = GetHeight(AT->Left);
       HR = GetHeight(AT->Right);
       Max = HL > HR ? HL : HR;
       return Max + 1;
   } else
       return 0;
}