赞
踩
基本结构 | 查找 | 插入/删除 |
---|---|---|
无序向量 | O(n) | O(n) |
有序向量 | O( log n \log n logn) | O(n) |
无序列表 | O(n) | O(1) |
有序列表 | O(n) | O(n) |
各数据项依所持关键码 而彼此区分:call-by-KEY
当然,关键码之间必须同时支持比较(大小)与比对(相等)
数据集中的数据项,统一地表示和实现为词条(entry)形式
template struct Entry { //词条模板类
K key; V value; //关键码、数值
Entry( K k = K(), V v = V() ) : key(k), value(v) {}; //默认构造函数
Entry( Entry const & e ) : key(e.key), value(e.value) {}; //克隆
// 比较器、判等器(从此,不必严格区分词条及其对应的关键码)
bool operator< ( Entry const & e ) { return key < e.key; } //小于
bool operator> ( Entry const & e ) { return key > e.key; } //大于
bool operator==( Entry const & e ) { return key == e.key; } //等于
bool operator!=( Entry const & e ) { return key != e.key; } //不等
}
2.1 顺序性
2.2 重复关键码
为简化起见,暂且 禁止词条的关键码重复
当然,这种简化
2.3 单调性
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>); //旋转调整
}
1.1 减而治之
从根节点出发,逐步地缩小查找范围,直到发现目标(成功),或抵达空树(失败)
对照中序遍历序列可见,整个过程可视作是在 仿效有序向量的二分查找
template<typename T> BinNodePosi<T> & BST<T>::search( const T & e ) {
if ( !_root || e == _root->data ) //空树,或恰在树根命中
{ _hot = NULL; return _root; }
for ( _hot = _root; ; ) { //否则,自顶而下
BinNodePosi<T>& v = ( e < _hot->data ) ? _hot->lc : _hot->rc; //深入一层
if ( !v || e == v->data ) return v;
_hot = v; //一旦命中或抵达叶子,随即返回
} //返回目标节点位置的引用,以便后续插入、删除操作
} //无论命中或失败,_hot均指向v之父亲(v是根时,hot为NULL)
1.2 返回的引用值
先借助search(e) 确定插入位置及方向
若e尚不存在,则再 将新节点作为叶子插入
于是,只需令_hot通过v指向新节点
template <typename T> BinNodePosi<T> BST<T>::insert( const T & e ) {
BinNodePosi<T> & x = search( e ); //查找目标(留意_hot的设置)
if ( ! x ) { //既禁止雷同元素,故仅在查找失败时才实施插入操作
x = new BinNode<T>( e, _hot ); //在x处创建新节点,以_hot为父亲
_size++; updateHeightAbove( x ); //更新全树规模,更新x及其历代祖先的高度
}
return x; //无论e是否存在于原树中,至此总有x->data == e
} //验证:对于首个节点插入之类的边界情况,均可正确处置
3.1 单分支
若*x(69)的某一子树为空,则可将其替换为另一子树(64)(可能亦为空)
验证:如此操作之后,二叉搜索树的拓扑结构依然完整;顺序性依然满足
3.2 双分支
若:x(36)左、右孩子并存,则调用BinNode::succ()找到x的直接后继 (必无左孩子);交换x(36)与*w(40)
于是问题转化为删除w,可按前一情况处理
尽管顺序性在中途曾一度不合 但最终必将重新恢复
3.3 算法
template<typename T> bool BST<T>::remove( const T & e ) { BinNodePosi<T> & x = search( e ); //定位目标节点 if ( !x ) return false; //确认目标存在(此时_hot为x的父亲) removeAt( x, _hot ); //分两大类情况实施删除,更新全树规模 _size--; //更新全树规模 updateHeightAbove( _hot ); //更新_hot及其历代祖先的高度 return true; } //删除成功与否,由返回值指示 template<typename T> static BinNodePosi<T> removeAt( BinNodePosi & x, BinNodePosi & hot ) { BinNodePosi w = x; //实际被摘除的节点,初值同x BinNodePosi succ = NULL; //实际被删除节点的接替者 //单分支 if ( ! HasLChild( *x ) ) succ = x = x->rc; //左子树为空 else if ( ! HasRChild( *x ) ) succ = x = x->lc; //右子树为空 //此类情况仅需O(1)时间 //双分支 else {//若x的左、右子树并存,则 w = w->succ(); swap( x->data, w->data ); //令*x与其后继*w互换数据 BinNodePosi u = w->parent; //原问题即转化为,摘除非二度的节点w ( u == x ? u->rc : u->lc ) = succ = w->rc; //兼顾特殊情况:u可能就是x } //时间主要消耗于succ(),正比于x的高度——更精确地,search()与succ()总共不过O(h) hot = w->parent; //记录实际被删除节点的父亲 if ( succ ) succ->parent = hot; //将被删除节点的接替者与hot相联 release( w->data ); release( w ); return succ; //释放被摘除节点,返回接替者 }
1.1 树高:最坏情况与平均情况
由以上的实现与分析,BST主要接口search()、insert()和remove()的运行时间,在最坏情况下,均线性正比于其高度O(h)
若不能有效地控制树高,就无法体现出BST相对于向量、列表等数据结构的明显优势
比如在最(较)坏情况下,二叉搜索树可能彻底地(接近地)退化为列表,此时的性能不仅没有提高,而且因为结构更为复杂,反而会(在常系数意义上)下降
1.2 随机生成:n个词条{ e 1 , e 2 , . . . , e n e_1,e_2,...,e_n e1,e2,...,en}按随机排列σ={ e i 1 , e i 2 , . . . , e i n e_{i_1},e_{i_2},...,e_{i_n} ei1,ei2,...,ein}依次插入
1.3 随机组成:n个互异节点,在遵守顺序性的前提下,随机确定拓扑联接关系
由n个互异节点随机组成的BST,若共计S(n)棵,则有 S ( n ) = ∑ k = 1 n S ( k − 1 ) ⋅ S ( n − k ) = c a t a l a n ( n ) = ( 2 n ) ! / ( ( n + 1 ) ! ⋅ n ! ) S(n)=\sum_{k=1}^{n}S(k-1)·S(n-k)=catalan(n)=(2n)!/((n+1)! · n!) S(n)=∑k=1nS(k−1)⋅S(n−k)=catalan(n)=(2n)!/((n+1)!⋅n!)
假定所有BST等概率地出现,则其平均高度为 Θ ( n ) Θ(\sqrt{n}) Θ(n )
在Huffman编码之类的应用中,二叉树(尽管还不是BST)的确是逐渐拼合而成的
1.4 logn vs. sqrt(n)
2.1 理想平衡
2.2 渐近平衡
3.1 等价BST
3.2 限制条件 + 局部性
3.3 等价变换 + 旋转调整:序齿不序爵
刚刚失衡的BST,必可迅速转换为一棵等价的BBST——为此,只需O( log n \log n logn)甚至O(1)次旋转
zig和zag:仅涉及常数个节点,只需调整其间的联接关系;均属于局部的基本操作
调整之后:v/c深度加/减1,子(全)树高度的变化幅度,上下差异不超过1
实际上,经过不超过O(n)次旋转,等价的BST均可相互转化
1.1 平衡因子
1.2 AVL = 渐近平衡
1.3 最小生成树(Fibonaccian Tree)
2.1 接口
#define Balanced(x) ( stature( (x).lc ) == stature( (x).rc ) ) //理想平衡
#define BalFac(x) (stature( (x).lc ) - stature( (x).rc ) ) //平衡因子
#define AvlBalanced(x) ( ( -2 < BalFac(x) ) && (BalFac(x) < 2 ) ) //AVL平衡条件
template class AVL : public BST { //由BST派生
public: //BST::search()等接口,可直接沿用
BinNodePosi insert( const T & ); //插入(重写)
bool remove( const T & ); //删除(重写)
};
2.2 失衡
2.3 重平衡
3.1 单旋:黄色方块恰好存在其一
3.2 双旋
3.3 代码
template <typename T> BinNodePosi<T> AVL<T>::insert( const T & e ) {
BinNodePosi<T> & x = search( e ); if ( x ) return x; //若目标尚不存在
BinNodePosi<T> xx = x = new BinNode<T>( e, _hot ); _size++; //则创建新节点
// 此时,若x的父亲_hot增高,则祖父有可能失衡
for ( BinNodePosi<T> g = _hot; g; g = g->parent ) //从_hot起,逐层检查各代祖先g
if ( ! AvlBalanced( *g ) ) { //一旦发现g失衡,则通过调整恢复平衡
FromParentTo(*g) = rotateAt( tallerChild( tallerChild( g ) ) );
break; //局部子树复衡后,高度必然复原;其祖先亦必如此,故调整结束
} else //否则(g仍平衡)
updateHeight( g ); //只需更新其高度(注意:即便g未失衡,高度亦可能增加)
return xx; //返回新节点位置
}
4.1 单旋:黄色方块至少存在其一;红色方块可有可无
4.2 双旋
4.3 代码
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及祖先均有可能失衡
// 以下,从_hot出发逐层向上,依次检查各代祖先g
for ( BinNodePosi<T> g = _hot; g; g = g->parent ) {
if ( ! AvlBalanced( *g ) ) //一旦发现g失衡,则通过调整恢复平衡
g = FromParentTo( *g ) = rotateAt( tallerChild( tallerChild( g ) ) );
updateHeight( g ); //更新高度(注意:即便g未曾失衡或已恢复平衡,高度均可能降低)
} //可能需做过Ω(logn)次调整;无论是否做过调整,全树高度均可能下降
return true; //删除成功
}
5.1 返璞归真
设g为最低的失衡节点,沿最长分支考察祖孙三代:g ~ p ~ v,按中序遍历次序,重命名为:a < b < c
它们总共拥有四棵子树(或为空) 按中序遍历次序,重命名为: T 0 < T 1 < T 2 < T 3 T_0 < T_1 < T_2 < T_3 T0<T1<T2<T3
将原先以g为根的子树S,替换为一棵新子树S’
等价变换,保持中序遍历次序: T 0 < a < T 1 < b < T 2 < c < T 3 T_0 <a< T_1 <b< T_2 <c< T_3 T0<a<T1<b<T2<c<T3
5.2 代码
template BinNodePosi BST::connect34(
BinNodePosi a, BinNodePosi b, BinNodePosi c,
BinNodePosi T0, BinNodePosi T1, BinNodePosi T2, BinNodePosi T3
){
a->lc = T0; if (T0) T0->parent = a;
a->rc = T1; if (T1) T1->parent = a;
c->lc = T2; if (T2) T2->parent = c;
c->rc = T3; if (T3) T3->parent = c;
b->lc = a; a->parent = b; b->rc = c; c->parent = b;
updateHeight(a); updateHeight(c); updateHeight(b); return b;
}
5.3 统一调整
template<typename T> BinNodePosi<T> BST<T>::rotateAt( BinNodePosi v ) { BinNodePosi 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->lc, v->rc, p->rc, g->rc ); } else { //zig-zag v->parent = g->parent; //向上联接 return connect34( p, v, g, p->lc, v->lc, v->rc, g->rc ); } else if ( IsLChild( * v ) ) { //zig-zig p->parent = g->parent; //向上联接 return connect34( v, p, g, v->lc, v->rc, p->rc, g->rc ); } else { //zig-zag v->parent = g->parent; //向上联接 return connect34( p, v, g, p->lc, v->lc, v->rc, g->rc ); }
5.4 AVL:综合评价
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。