马来西亚的网站后缀,seo优化大公司排名,用ip地址做网站,宜昌住房与城乡建设部网站本文目录 00.BBST——平衡二叉搜索树01.AVL树02.AVL的插入2.1单旋——zig 与 zag2.2插入节点后的单旋实例2.3手玩小样例2.4双旋实例2.5小结 03.AVL的删除3.1单旋删除3.2双旋删除3.3小结 04.34重构05.综合评价AVL5.1优点5.2缺点 06.代码注意插入算法删除算法完整代码#xff1a… 本文目录 00.BBST——平衡二叉搜索树01.AVL树02.AVL的插入2.1单旋——zig 与 zag2.2插入节点后的单旋实例2.3手玩小样例2.4双旋实例2.5小结 03.AVL的删除3.1单旋删除3.2双旋删除3.3小结 04.34重构05.综合评价AVL5.1优点5.2缺点 06.代码注意插入算法删除算法完整代码AVL.h 00.BBST——平衡二叉搜索树
本文是介绍众多平衡二叉搜索树BBST的第一篇——介绍AVL树。故先来引入BBST的概念。由于上一篇介绍的二叉搜索树BST在极度退化的情况下十分不平衡不平衡到只朝一侧偏成为一条链表复杂度可达 O ( n ) O(n) O(n)所以我们要在“平衡”方面做一些约束以防我们的树结构退化得那么严重。
具体来说含 n n n个节点高度为 h h h的BST若满足 h O ( l o g 2 n ) hO(log_2 n) hO(log2n)则称为称为平衡二叉搜索树。
01.AVL树
AVL树是一种BBST稍后会证明。它约束自己是否平衡主要靠一个指标——平衡因子。定义平衡因子左子树高度-右子树高度。如果满足 − 2 全部平衡因子 2 -2全部平衡因子2 −2全部平衡因子2则该AVL树处于平衡状态否则需要靠一系列措施将其恢复平衡。
首先先证明AVL树满足BBST的要求即 h O ( l o g 2 n ) hO(log_2 n) hO(log2n)下式。我们可转而证明nΩ(Φh)即AVL的节点数不会太少
[结论] 高度为 h h h的AVL Tree 至少有 f i b ( ( h 3 ) − 1 fib((h3)-1 fib((h3)−1 个节点 [证明] 02.AVL的插入 插入一个节点会导致一串祖先的失衡,删除一个节点至多导致一个祖先失衡。但是通过后续代码就可发现删除节点比插入节点复杂的多。原因是插入节点只要调整好了一处这条路径上的所有祖先都可平衡复杂度是O(1)。而删除节点是调整好了一处平衡另一处就会不平衡自下而上层层调整复杂度是O(n)。 2.1单旋——zig 与 zag
zig 与 zag 分别对应右单旋和左单旋。单旋的操作改变的是两个节点的相对位置。改变的是三条线一上一下一子树。新树根上行指向原根新树根原子树给到原根。如下图V到Y那去Y到C那去。 2.2插入节点后的单旋实例
在下图处添加一个节点自上而下更新高度或平衡因子g会率先进入不平衡状态。观察gpv呈一条线而非“之”字所以用单旋调整之字形对应双旋。具体来说对g左单旋。
2.3手玩小样例 例题将123456依次插入空的AVL Tree最终AVL Tree长成什么样 [过程]首先正常插入12插入3时1是第一个发现不平衡的节点zag(1)即对1进行左单旋成功解决正常插入4
插入5时3是第一个发现不平衡的节点zag(3)即对3进行左单旋成功解决 插入6时2是第一个发现不平衡的节点zag(2)即对2进行左单旋成功解决
2.4双旋实例
双旋的操作改变的是三个节点的相对位置。分为两种情况——zig-zag与zag-zig。
在下图处添加一个节点自上而下更新高度或平衡因子g会率先进入不平衡状态。观察gpv呈“之”字所以用双旋。具体来说先zig§再zag(g).
2.5小结
AVL树中插入节点引发失衡经旋转调整后重新平衡此时包含节点g,p,v的子树高度是不变的子树高度复原更高祖先也必平衡全树复衡。故在AVL树中修正插入节点引发的失衡不会出现失衡传播。
03.AVL的删除 删除一个节点至多导致一个祖先失衡。 3.1单旋删除 3.2双旋删除 3.3小结
AVL树中删除节点引发失衡经旋转调整后重新平衡此时包含节点g,p,v的子树高度有可能不变也有可能减小1故在AVL树中修正删除节点引发的失衡有可能出现失衡传播。
04.34重构
通过观察以上插入和删除的结果示意图发现结构是一样的——三个节点按顺序呈三角形四个子树按原来的顺序分别挂在两个孩子节点的下边。如下图
那我们就不必关注具体的技巧了而是将三个节点和四个子树拆开像暴力组装魔方那样先拆散拼上。
template typename T
BinNodeT * BSTT::connect34(BinNodeT * a, BinNodeT * b, BinNodeT * c, BinNodeT * T1, BinNodeT * T2, BinNodeT *T3, BinNodeT * T4)
{b-left a; b-right c;a-left T1; a-right T2;c-left T3; c-right T4;a-parent b; c-parent b;if (T1) T1-parent a;if (T2) T2-parent a;if (T3) T3-parent c;if (T4) T4-parent c;a-updateHigh(); b-updateHigh(); c-updateHigh();return b;
}template typename T
BinNodeT * BSTT::rotateAt(BinNodeT * v)
{BinNodeT * p v-parent;BinNodeT * g p-parent;BinNodeT * T1, *T2, *T3, *T4, *a, *b, *c;if (p g-left v p-left){a v; b p; c g;T1 v-left; T2 v-right; T3 p-right; T4 g-right;}else if (p g-left v p-right){a p; b v; c g;T1 p-left; T2 v-left; T3 v-right; T4 g-right;} else if (p g-right v p-left){a g; b v; c p;T1 g-left; T2 v-left; T3 v-right; T4 p-right;}else{a g; b p; c v;T1 g-left; T2 p-left; T3 v-left; T4 v-right;}b-parent g-parent; //向上链接return connect34(a, b, c, T1, T2, T3, T4);}05.综合评价AVL
5.1优点
查找、插入、删除最坏时间复杂度为 O ( l o g n ) O(logn) O(logn) O ( n ) O(n) O(n)的存储空间
5.2缺点
需要额外维护高度或平衡因子这一指标后续Splay Tree可改善这一问题删除操作后最多需旋转 Ω ( l o g n ) \Omega(logn) Ω(logn)次单次动态调整后全树拓扑结构的变化量可能高达 Ω ( l o g n ) \Omega(logn) Ω(logn) RedBlack Tree可缩到 O ( 1 ) O(1) O(1)
谢谢观看~
06.代码
注意
fromParentTo()是根节点的情况connect34()向上链接别忘
插入算法
为什么不用现成的BST::insert(val) BST::insert自带更新一串高度旋转调整之后还得把这一串更新回来。
BinNodeT * insert(T const val){BinNodeT * X BSTT::search(val);if (!X){X new BinNodeT(val, BSTT::hot); BinTreeT::size;BinNodeT * X_copy X;while (X_copy AvlBalanced(X_copy)){X_copy-updateHigh();X_copy X_copy-parent;}if (X_copy) //说明是因为遇到了不平衡节点才退出了while现在解决不平衡问题{BinNodeT * tmp BinTreeT::fromParentTo(X_copy);tmp BSTT::rotateAt(tallerChild(tallerChild(X_copy))); // 内部自带单个节点更新高度}return X;}}删除算法
受限于BST::remove的返回值仅仅是bool所以用底层的removeAt. removeAt的返回值是接替者但有时接替者是NULL。还好有BST::hot存放被删节点的父亲。实际上BST::remove的更新高度也是从hot开始的
bool remove(T const val) {BinNodeT * X BSTT::search(val);if (!X) return false;else{BSTT::removeAt(X, BSTT::hot);BinTreeT::size--;// 与insert不同的是remove可能要调整很多次for (BinNodeT * g BSTT::hot; g; g g-parent){int i BF(g);if (!AvlBalanced(g)){BinNodeT * tmp BinTreeT::fromParentTo(g);tmp BSTT::rotateAt(tallerChild(tallerChild(g))); }else g-updateHigh();}return true;}}完整代码AVL.h
# pragma once
# include BST.h# define BF(x) (int)(getHigh(x-left) - getHigh(x-right))
# define AvlBalanced(x) ( -2 BF(x) BF(x) 2 )template typename T
BinNodeT * tallerChild(BinNodeT * x)
{return (getHigh(x-left) getHigh(x-right)) ? x-left : x-right;
}template typename T
class AVL :public BSTT
{public:bool remove(T const val) {BinNodeT * X BSTT::search(val);if (!X) return false;else{BSTT::removeAt(X, BSTT::hot);BinTreeT::size--;// 可优化直到到某祖先高度不变停止上行。那就要在刚刚更新高度时记录中途退出的位置以便在此处判断for (BinNodeT * g BSTT::hot; g; g g-parent){int i BF(g);if (!AvlBalanced(g)){BinNodeT * tmp BinTreeT::fromParentTo(g);tmp BSTT::rotateAt(tallerChild(tallerChild(g))); // 内部自带单个节点更新高度}else g-updateHigh();}return true;}}BinNodeT * insert(T const val){BinNodeT * X BSTT::search(val);if (!X){X new BinNodeT(val, BSTT::hot); //这一句话将两个关系连接BinTreeT::size;BinNodeT * X_copy X;while (X_copy AvlBalanced(X_copy)){X_copy-updateHigh();X_copy X_copy-parent;}if (X_copy) //说明是因为遇到了不平衡节点才退出了while现在解决不平衡问题{BinNodeT * tmp BinTreeT::fromParentTo(X_copy);tmp BSTT::rotateAt(tallerChild(tallerChild(X_copy))); // 内部自带单个节点更新高度}return X;}}
};
感谢观看~
附上前传 C数据结构之BinaryTree二叉树的实现 C数据结构之BST二叉搜索树的实现
