-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathlesson7
194 lines (185 loc) · 7.62 KB
/
lesson7
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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
二叉搜索树（BST）
循关键码访问
数据项之间，依照各自的关键码彼此区分
条件：大小比较 、 等于比对
数据集合中的数据项统一地表示为词条entry形式
template <typename K, typename V> struct Entry{
K key; V value; //关键码、数值
Entry( K k = K(), V v = V()): key(k), value(v){};
Entry( Entry <K, V> const & e ): key(e.key), value(e.value){};
//比较器、判等器
bool operator < (Entry<K, V> const & e ){return key < e.key;}
bool operator > (Entry<K, V> const & e ){return key > e.key;}
bool operator == (Entry<K, V> const & e ){return key == e.key;}
bool operator != (Entry<K, V> const & e ){return key != e.key;}
}
有序性
节点 ~ 词条 ~ 关键码
顺序性：任意节点不小于/不大于其左/右后代
单调性：BST中序遍历序列，单调非降（充要条件）
template <typename T> class BST : public BinTree<T>{
public: //以virtual修饰，以便派生类重写
virtual BinNodePosi(T) & search( const T &);
virtual BinNodePosi(T) insert( const T &);
virtual bool remove ( const T &);
protected:
BinNodePosi(T) _hot; //命中节点的父亲
BinNodePosi(T) connect34( //3 + 4重构
BinNodePosi(T),BinNodePosi(T),BinNodePosi(T),
BinNodePosi(T),BinNodePosi(T),BinNodePosi(T),BinNodePosi(T));
BinNodePosi(T) rotateAt( BinNodePosi(T) );//旋转调整
}
template <typename T> BinNodePosi(T) &BST<T>::search( const T & e){
return searchIn( _root, e, _hot = NULL);
}
static BinNodePosi(T) & searchIn(
BinNodePosi(T) & v, //当前（子）树根
const T & e, //目标关键码
BinNodePosi(T) & hot) //记忆热点{
if (!v || (e == v->data)) return v;
hot = v;
return seachIn(((e < v->data) ? v->lChild : v->rChild), e , hot);
}
查找成功，指向关键码为e且真实存在的节点
失败，指向最后一次试图转向的空节点NULL
插入算法
template <typename T> BinNodePosi(T) BST<T>::insert( const T & e){
BinNodePosi(T) & x = search(e);
if(!x){
x = new BinNode<T>(e, _hot);
_size++;
updateHeightAbove(x);
}
return x;
}
删除算法
template <typename T> bool BST<T>::remove( const T & e){
BinNodePosi(T) & x = search(e);
if(!x) return false;
removeAt(x, _hot);
_size--;
updateHeightAbove(_hot);
return true;
}
单分支
template <typename T> static BinNodePosi(T)
removeAt( BinNodePosi(T) & x, BinNodePosi(T) & hot){
BinNodePosi(T) w = x; //实际被摘除的节点
BinNodePosi(T) succ = NULL; //实际被删除节点的接替者
if (! HasLChild( *x)) succ = x = x->rChild;
else if (! HasRChild( *x)) succ = x = x->lChild;
else{ /*..左右子树并存的情况*/}
hot = w->parent; //记录实际被删除节点的父亲
if (succ) succ->parent = hot; //将被删除节点的接替者与hot相连
release( w ->data); //释放被摘除节点
release( w );
return succ; //返回接替者
}
template <typename T> static BinNodePosi(T)
removeAt( BinNodePosi(T) & x, BinNodePosi(T) & hot){
else{
w = w->succ();
swap( x->data, w->data);//令 *x与其后继*w互换数据
BinNodePosi(T) u = w->parent; //原问题即转化为，摘除非二度的节点w
( u == x ? u->rChild : u ->lChild) = succ = w->rChild;
//若删除的节点与直接后继即为中序遍历的直接后继，可知该节点在删除的节点的右孩子
//反之交换过的节点只有右孩子
}
}
节点数目固定，兄弟子树高度接近（平衡），全树也将倾向于更低
由n个节点组成的二叉树，高度不低于[logn] ,恰为logn，称作理想平衡
高度渐近不超过O(logn)，即可称作适度平衡
适度平衡的BST，称作平衡二叉搜索树(BBST)
等价BST：
上下可变、左右不乱。
AVL树：
平衡因子 balFac(v) = height(lc(v)) - height(rc(v));
任意v |balFac(v)| <= 1;
高度为h的AVL树,至少包含S(h) = fib(h + 3) -1个节点
S(h) = 1 + S(h-1) + S(h-2);
S(h) + 1 = [ S(h-1) + 1 ] + [ S(h-2) + 1 ];
h n S(h) + 1
0 1 2 = fib(3)
1 2 3 = fib(4)
AVL接口：
#define Balanced(x) (stature((x).lChild) == stature((x).rChild))//理想平衡
#define BalFac(x) (stature((x).lChild) - stature((x).rChild))//平衡因子
#define AvlBalanced(x) ((-2 < BalFac(x)) && (BalFac(x) < 2)) //平衡条件
template <typename T> class AVL: public BST<T>{
public :
BinNodePosi(T) insert( const T &);
bool remove( const T &);
}
插入实现：
template <typename T> BinNodePosi(T) AVL<T>::insert(const T & e){
BinNodePosi(T) & x = search(e);
if (x) return x;
x = new BinNode<T> (e, _hot);
size++;
BinNodePosi(T) xx = x;
for (BinNodePosi(T) g = x->parent; g; g = g->parent)
if(!AvlBalanced(* g)){
FromParentTo( *g) = rotateAt( tallerChild ( tallerChild(g)));
break; //g复衡后，局部高度复原；其祖先必如此。
}
else
updateHeight(g);
return xx;
}
删除实现
template <typename T> bool AVL<T>::remove(const T & e){
BinNodePosi(T) & x = search(e);
if (!x) return false;
removeAt(x, _hot);
size--;//若目标的确存在，则在按BST规则删除之后，_hot及祖先均有可能失衡
for (BinNodePosi(T) g = _hot; g; g = g->parent)
if(!AvlBalanced(* g)){
g = FromParentTo( *g) = rotateAt( tallerChild ( tallerChild(g)));
updateHeight(g);
}
}
return true;
}
3+4重构：算法
设 g(x)为最低的失衡节点，考察祖孙三代：g ~ p ~ v
按中序遍历次序，将其重命名为 a < b < c
b a b c
a c ===>> T0 T1 T2 T3
T0 T1 T2 T3
c 实现
template <typename T> BinNodePosi(T) BST<T>::connect34(
BinNodePosi(T) a, BinNodePosi(T) b ,BinNodePosi(T) c,
BinNodePosi(T) T0,BinNodePosi(T) T1,BinNodePosi(T) T2,BinNodePosi(T) T3 ){
a->lChild = T0; if (T0) T0->parent = a;
a->rChild = T1; if (T1) T1->parent = a; updateHeight(a);
c->lChild = T2; if (T2) T2->parent = c;
c->rChild = T3; if (T3) T3->parent = c; updateHeight(c);
b->lChild = a; a->parent = b;
b->rChild = c; c->parent = b; updateHeight(b);
return b;
)
统一调整：实现
template<typename T> BinNodePosi(T) BST<T>::rotateAt(BinNodePosi(T) v){
BinNodePosi(T) p = v->parent, g = p->parent; //父亲，祖父
if ( IsLChild (* p )) //zig
if (IsLChild (* v)) { //zig-zig
p->parent = g->parent; //向上联接
return connect34 (
v,p,g
v->lChild, v->rChild, p->rChild, g->rChild
);
}
else{ //zig-zag
v->parent = g->parent; //向上联接
return connect34(
p,v,g
p->lChild, v->lChild,v->rChild,g->rChild
);
}
else{ /**...zag-zig zag-zag }
}
AVL
优点：查找、插入、删除，O(logn)
O(n)的存储空间
缺点：借助高度或平衡因子，为此需要改造元素结构，或额外封装
单次动态调整后，全树拓扑结构的变化量可达omg(logn);