AVL树解析(基于查找二叉树(dynamicSearchTree))
平衡二叉树:
在查找二叉树的基础上要求每个节点左右字节点的高度差不能超过一。
于是对于节点多了一个数据成员高度来实现这一功能。
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 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209
| #include "dynamicSearchTable.h"
template <class KEY, class OTHER> struct SET { KEY key; OTHER other; };
template <class KEY,class OTHER> class AvlTree :public dynamicSearchTable<KEY, OTHER> { struct AvlNode { SET<KEY, OTHER>data; AvlNode* left; AvlNode* right; int height;
AvlNode(const SET<KEY, OTHER>& element, AvlNode* lt, AvlNode* rt, int h = 1):data(element),left(lt),right(rt),height(h){} };
AvNodee* root;
public: AvlTree() { root = NULL;} ~AvlTree() { makeEmpty(root);} SET<KEY, OTHER>* find(const KEY& x)const; void insert(const SET<KEY, OTHER>& x); void remove(const KEY& x); private: void insert(const SET<KEY, OTHER>& x, AvlNode*& t); bool remove(const KEY& x, AvlNode*& t); void makeEmpty(AvlNode* t); int height(AvlNode* t)const { return t == NULL ? 0 : t->height;} void LL(AvlNode*& t); void LR(AvlNode*& t); void RL(AvlNode*& t); void RR(AvlNode*& t); int max(int a, int b) { return (a > b) ? a : b;} bool adjust(AvlNode*& t, int subTree); };
template <class KEY, class OTHER> SET<KEY, OTHER>* AvlTree<KEY, OTHER>::find(const KEY& x)const { AvlNode* t = root;
while (t != NULL && t->data.key != x) { if (t->data.key > x)t = t->left; else t = t->right; } if (t == NULL)return NULL; else return (SET<KEY, OTHER>*)t; }
template <class KEY, class OTHER> void AvlTree<KEY, OTHER>::LL(AvlNode*& t) { AvlNode* t1 = t->left; t->left = t1->right; t1->right = t; t->height = max(height(t->left), height(t->right)) + 1; t1->height = max(height(t->left), height(t)) + 1; t = t1; }
template <class KEY, class OTHER> void AvlTree<KEY, OTHER>::RR(AvlNode*& t) { AvlNode* t1 = t->right; t->right = t1->left; t1->left = t; t->height = max(height(t->left), height(t->right)) + 1; t1->height = max(height(t->right), height(t)) + 1; t = t1; }
template <class KEY, class OTHER> void AvlTree<KEY, OTHER>::LR(AvlNode*& t) { RR(t->left); LL(t); }
template <class KEY, class OTHER> void AvlTree<KEY, OTHER>::RL(AvlNode*& t) { LL(t->right); RR(t); }
template <class KEY, class OTHER> void AvlTree<KEY, OTHER>::insert(const SET<KEY, OTHER>& x) { insert(x, root); }
template <class KEY, class OTHER> void AvlTree<KEY,OTHER>::insert(const SET<KEY, OTHER>&x, AvlNode*& t) { if (t == NULL) t = new AvlNode(x, NULL, NULL); else if (x.key < t->data.key) { insert(x, t->left); if (height(t->left) - height(t->right) == 2) if (x.key < t->left->data.key)LL(t); else LR(t); } else if (t->data.key < x.key) { insert(x, t->right); if (height(t->right) - height(t->left) == 2) if (t->right->data.key < x.key)RR(t); else LR(t); } t->height = max(height(t->left), height(t->right)) + 1; }
template<class KEY,class OTHER> void AvlTree<KEY, OTHER>::remove(const KEY& x) { remove(x, root); }
template<class KEY, class OTHER> bool AvlTree<KEY, OTHER>::remove(const KEY& x, AvlNode* & t) { if (t == NULL)return true; if (x == t->data.key) { if (t->left == NULL || t->right == NULL) { AvlNode* oldNode = t; t = (t->left != NULL) ? t->left : t->right; delete oldNode; return false; } else { AvlNode* tmp = t->right; while (tmp->left != NULL)tmp = tmp->left; t->data = tmp->data; if (remove(tmp->data.key, t->right))return true; return adjust(t, 1); } }
if (x < t->data.key) { if (remove(x, x->left))return true; return adjust(t, 0); } else { if (remove(x, t->right))return true; return adjust(t, 1); } }
template<class KEY, class OTHER> bool AvlTree<KEY, OTHER>::adjust(AvlNode*& t, int subTree) { if (subTree) { if (height(t->left) - height(t->right) == 1)return true; if (height(t->right) == height(t->left)) { --t->height; return false; } if (height(t->left->right) > height(t->left->left)) { LR(t); return false; } LL(t) if (height(t->right) == height(t->left))return false; else return true; } else { if (height(t->right) - height(t->left) == 1)return true; if (height(t->right) == height(t->left)) { --t->height; return false; } if (height(t->right->left) > height(t->right->right)) { RL(t); return false; } RR(t) if (height(t->right) == height(t->left))return false; else return true; } }
template<class KEY, class OTHER> void AvlTree<KEY, OTHER>::makeEmpty(AvlNode* t) { if (t == NULL)return; makeEmpty(t->left); makeEmpty(t->right); delete t; }
|
基本组成成员
1 2 3 4 5 6 7 8 9 10
| struct AvlNode { SET<KEY, OTHER>data; AvlNode* left; AvlNode* right; int height;
AvlNode(const SET<KEY, OTHER>& element, AvlNode* lt, AvlNode* rt, int h=1):data(element),left(lt),right(rt),height(h){} };
|
多了一个高度,构造函数默认为1(指只有自己)
AVL类的基本数据成员和函数
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
| template <class KEY,class OTHER> class AvlTree :public dynamicSearchTable<KEY, OTHER> { struct AvlNode { SET<KEY, OTHER>data; AvlNode* left; AvlNode* right; int height; AvlNode(const SET<KEY, OTHER>& element, AvlNode* lt, AvlNode* rt, int h = 1):data(element),left(lt),right(rt),height(h){} }; AvNodee* root;
public: AvlTree() { root = NULL;} ~AvlTree() { makeEmpty(root);} SET<KEY, OTHER>* find(const KEY& x)const; void insert(const SET<KEY, OTHER>& x); void remove(const KEY& x); private: void insert(const SET<KEY, OTHER>& x, AvlNode*& t); bool remove(const KEY& x, AvlNode*& t); void makeEmpty(AvlNode* t); int height(AvlNode* t)const { return t == NULL ? 0 : t->height;} void LL(AvlNode*& t); void LR(AvlNode*& t); void RL(AvlNode*& t); void RR(AvlNode*& t); int max(int a, int b) { return (a > b) ? a : b;} bool adjust(AvlNode*& t, int subTree); };
|
其实private类的函数都是公有类函数的工具函数
函数的实现分析
1 2 3 4 5 6 7 8 9 10 11 12
| template <class KEY, class OTHER> SET<KEY, OTHER>* AvlTree<KEY, OTHER>::find(const KEY& x)const { AvlNode* t = root; while (t != NULL && t->data.key != x) { if (t->data.key > x)t = t->left; else t = t->right; } if (t == NULL)return NULL; else return (SET<KEY, OTHER>*)t; }
|
还是基于二叉查找树的特性,只是没有使用递归函数,这种方式被称为迭代实现
在介绍函数之前理解一些东西,关于插入的一些特性:
1. 首先插入还是和二叉查找树一样插入在叶子节点上
2. 一次插入后,只有在插入点到根的路径上的节点才有可能发生平衡度的变化
3. AVL的平衡策略最多只要调整一个节点就可以了
主要分析LL和LR俩种情况
注意:
对于旋转策略的核心是保证节点的高度不发生变化,就是通过旋转变为原来的高度,从而保证对上面节点安全的保证。
一旦改变了数的高度,那需要不断往上检索,直到那个节点的高度没有发生变化
LL:原来A的左子树比右子树高,插入发生在A的左儿子的左子树中,使A的左子树增高
(注意(仅仅对于插入而言,对于删除这个结论反而相反):平衡度只是一种高度是否平衡的表现形式,真正影响的是节点的高度,主要体现在平衡度向零趋近高度不变,而向俩边增长表明节点高度发生改变)
此图有图
节点平衡度从-1到0但是并不影响上面的节点,因为这个节点的高度并未发生改变,反而0到1表明当前节点的高度发生改变
现在来分析LL的情况
此处有图
首先分析一下一些情况:
1. **首先B的平衡度一定原来是0,然后变为1,
因为我们上面解释过如果是-1到0表明是向零趋近,B的高度不会发生变化,进而不会影响A
若是原来是1,变成2,显然B才是危机节点,处理就不是A了
对于LL解决办法就是向右旋转
此处有图
显然我们发现在旋转后我们发现我们处理的这个树的高度与插入前的高度完全一样,于是不用担心上面节点的平衡度了
思考:
对于这种旋转必然是左右子树未实现满二叉树或者完全二叉树导致,就是有空缺的位置来保证旋转后高度不发生变化
那么假设是满二叉树插入,我们会发现并不影响平衡度都从(0到1或者0到-1)
(其实这就是插入点后的检索过程,虽然高度发生了变化,但是一直向上检索发现平衡度没有打破规则,那么就会检索到根节点结束)
现在附上LL代码图
1 2 3 4 5 6 7 8 9 10
| template <class KEY, class OTHER> void AvlTree<KEY, OTHER>::LL(AvlNode*& t) { AvlNode* t1 = t->left; t->left = t1->right; t1->right = t; t->height = max(height(t->left), height(t->right)) + 1; t1->height = max(height(t->left), height(t)) + 1; t = t1; }
|
有心情的话 可以在这个补一个过程图,看我以后记不记的住吧
*1.*我们发现指针还是引用传递,主要是我要旋转A点,那么就需要修改A的父节点对应的指针从。原理和二叉查找树的原理相同
RR也是同理只是向左旋转
附上RR的代码
1 2 3 4 5 6 7 8 9 10
| template <class KEY, class OTHER> void AvlTree<KEY, OTHER>::RR(AvlNode*& t) { AvlNode* t1 = t->right; t->right = t1->left; t1->left = t; t->height = max(height(t->left), height(t->right)) + 1; t1->height = max(height(t->right), height(t)) + 1; t = t1; }
|
现在来分析LR的情况
为什么要单独讨论这种情况?
因为我们发现仅仅如果使用LL右旋发现只是不过对这个树镜像对称过去了而已,A点仍然是失衡点,只不过是现在是右子树高了
此处有图
我们相对于之前多了一个参考C节点,对于CL和CR谁的高度为h-1并不重要
为了保证根节点的高度不发生变化,我们选择LR的双旋转的方法,对B点进行左旋转(RR),再对A点进行右旋转(LL)
不难发现,C点占据了原来的根节点,且平衡度恢复了0,因为是1到0我们便可认定节点的高度没有发生变化,从而无需再向上检索
过程如下图显示
其实逻辑也很好理解就是让根节点的右边多一个高度来平衡多的那个节点
代码如下
1 2 3 4 5 6
| template <class KEY, class OTHER> void AvlTree<KEY, OTHER>::LR(AvlNode*& t) { RR(t->left); LL(t); }
|
RL也完全是同理,就是对称了一下
1 2 3 4 5 6
| template <class KEY, class OTHER> void AvlTree<KEY, OTHER>::RL(AvlNode*& t) { LL(t->right); RR(t); }
|
以上我们分析了四种旋转情况接下来就来分析插入函数
前面我们提到了一个关键词回溯
对于代码里面的回溯就是在修改后往回检查,最好想的就是树了,我修改了叶节点,我需要对查找路径上的每一个点进行检查,那么我们在代码中如何往回实现这个功能呢?
答案就是利用
递归
假如我们要进行修改,并检查,可以用如下伪代码实现
1 2 3 4 5 6 7 8 9 10
| 插入函数 { 检查当前节点是不是插入点,是就插入 不是就根据于当前节点的大小调用“函数(左节点)/函数(右节点)”
//因为是递归调用,执行到这一样表示递归所有的修改已完成开始回溯了 检查当前节点的平衡度来看是否需要调整,若失衡分类讨论
重新计算高度 }
|
附上代码
其实我们发现这个回溯必须全部走完,因为要更改高度(尤其是满二叉树那种虽然不影响平衡度,但是路径上所有节点高度都需要+1)
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
| template <class KEY, class OTHER> void AvlTree<KEY, OTHER>::insert(const SET<KEY, OTHER>& x) { insert(x, root); }
template <class KEY, class OTHER> void AvlTree<KEY,OTHER>::insert(const SET<KEY, OTHER>&x, AvlNode*& t) { if (t == NULL) t = new AvlNode(x, NULL, NULL); else if (x.key < t->data.key) { insert(x, t->left); if (height(t->left) - height(t->right) == 2) if (x.key < t->left->data.key)LL(t); else LR(t); }
else if (t->data.key < x.key) { insert(x, t->right); if (height(t->right) - height(t->left) == 2) if (t->right->data.key < x.key)RR(t); else LR(t); }
t->height = max(height(t->left), height(t->right)) + 1; }
|
删除节点很有可能导致树变矮,导致二叉树失衡,所以必须要在删除后不断回溯调整平衡
首先这是一个回溯的过程,还有一个关键点就是是否需要再网上回溯的关键是:
的当前节点的高度在调整后或者未调整高度是否发生变换,注意我说的是高度不是平衡度,若往回检索发现有节点高度未发生变化就可以停止检查调整步骤直接return。
这也表明了虽然删除是递归,但是返回值是一个bool表示当前节点高度是否发生变化从而决定上面的节点是否需要检查
删除过程
这一个和二叉查找树没什么区别其实,依旧是分为三种情况(无儿子,一个儿子,俩个儿子)
前俩个可以用一个表达式来代替
1
| t=(t->left!=NULL):t->left?t-right;
|
相对后面的情况显示是迭代找到可替换的叶子节点,然后删除叶子节点啦。
检查过程
删除的时候没有插入那么幸运,删除时的调整很有可能导致整棵树高度下降,从而影响路上的所有父节点。
停止条件:只有当某个节点读的高度在删除后不变才无需向上检查调整了
导致树的高度发生变化有以下几种情况
(注意:这里平衡度是在向两边增长节点高度不变,向零靠近节点高度发生变化,因为是删除
(与插入的结论恰恰相反,插入是有可能增高,而删除是有可能降低高度))
此处有五种情况(假设都是在左子树上删除的节点)
此处有图
对于(a)的平衡度既没有失衡,高度也没有发生变化
对于(b)平衡度没有失衡,但是根据平衡度的变化可以发现节点的高度发生变换,需要检查父节点
对于(c)只需要节点P使用左旋(RR)即可,这样根节点的高度就变成了0,虽然平衡了但是平衡度从-1变为0,节点高度发生变化,需要检查父节点
对于(d)显然左旋仍然导致失衡,就像前面的RL的情况一样发生在内侧,这个时候就需要先对P的右子节点先右旋(LL)再对P进行左旋(RR),就会使根节点平衡度变为0.不需要对父节点进行检查
对于(e)对P使用简单的左旋(RR)根节点(原来P的位置)的平衡度变为1(注意平衡度从-1到1,节点的高度并未发生变化,可以认为就像交换了一样);当然可以使用RL,这样的话根节点的平衡度仍为-1,高度未发生变化。所以俩种方法都不需要检查父节点
对于添加在右子节点的方法对称就好了
附上代码
(指针参数还是引用,原因上面解释过了)
(true表示不用检查,false表示节点的高度发生变化,需要检查节点的高度)
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
| template<class KEY,class OTHER> void AvlTree<KEY, OTHER>::remove(const KEY& x) { remove(x, root); }
template<class KEY, class OTHER> bool AvlTree<KEY, OTHER>::remove(const KEY& x, AvlNode* & t) { if (t == NULL)return true; if (x == t->data.key) { if (t->left == NULL || t->right == NULL) { AvlNode* oldNode = t; t = (t->left != NULL) ? t->left : t->right; delete oldNode; return false; } else { AvlNode* tmp = t->right; while (tmp->left != NULL)tmp = tmp->left; t->data = tmp->data; if (remove(tmp->data.key, t->right)) return true; return adjust(t, 1); } }
if (x < t->data.key) { if (remove(x, x->left))return true; return adjust(t, 0); } else { if (remove(x, t->right))return true; return adjust(t, 1); } }
|
这段逻辑其实挺绕人的,remove函数的返回值主要三种:
1:删除的是只有一个字节点或者无子节点(直接返回true,必然改变高度)
2:向下递归调用remove,如果调用返回的是true,则自己不用调整,也返回true
3:如果调用的remove返回false,则需要返回adjust,一边检查高度是否发生变换+调整,调整后如果高度变化返回false,反之true(具体就是我们讨论的几个调整情况)
参数subTree(subtract Tree)1表示删除的右子树,0表示删除的左子树
0则是我们讨论的那五种情况
1则是完全对称的五种情况
调用adjust不一定高度有变化,但是平衡度一点是发生变化了
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
| template<class KEY, class OTHER> bool AvlTree<KEY, OTHER>::adjust(AvlNode*& t, int subTree) { if (subTree) { if (height(t->left) - height(t->right) == 1)return true; if (height(t->right) == height(t->left)) { --t->height; return false; } if (height(t->left->right) > height(t->left->left)) { LR(t); return false; } LL(t) if (height(t->right) == height(t->left))return false; else return true; } else { if (height(t->right) - height(t->left) == 1)return true; if (height(t->right) == height(t->left)) { --t->height; return false; } if (height(t->right->left) > height(t->right->right)) { RL(t); return false; } RR(t) if (height(t->right) == height(t->left)) return false; else return true; } }
|
到此难的地方已经处理好了其他的构造析构都是完全继承完全二叉树,所以不再赘述了
有时间再补补性能分析吧