数据结构-7.二叉搜索树

写在前面

本篇文章整理《数据结构(C++语言版)》关于二叉树这种线性结构知识点。

二叉搜索树

设计初衷:高效的动态修改(如insert, remove)与高高效的静态查找(search)能否兼顾?

循关键码访问

类似于python中的dict类型,词条对象拥有关键码key与值value并通过key来寻找对应节点。

1
2
3
4
5
6
7
8
9
10
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与中序遍历
从上图可以看出,二叉搜索树(BST)中序遍历序列形式上与有序向量相同。
BST模板类
这里假定基本元素类型T或者直接支持比较和判别操作,或者已经重载过对应操作符。

1
2
3
4
5
6
7
8
9
10
11
12
template<typename T> class BST : public BinTree {  //由二叉树(BT)派生
public: //以virtual修饰,强制要求派生类根据各自规则重写接口
virtual BinNodePosi(T) & search( cosnt 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) ); //旋转调整
}

关于虚函数virtual
当基类Base指针ptr指向派生类Derived的成员函数时,调用派生类对应的成员函数而不是基类成员函数(一般情况下,ptr是Base指针,其指向应为Base成员函数)
>>>
class Base {
public:
void echo1() { std::cout << “called from Base” << endl; }
virtual void echo2() { std::cout << “called from Base” << endl; }
}
class Derived : public Base {
public:
void echo1() { std::cout << “called from Derived” << endl; }
void echo2() { std::cout << “called from Derived” << endl; }
}
int main() {
Base * ptr1 = new Derived;
ptr->echo1; //调用Base成员函数,打印–called from Base
ptr->echo2; //调用Derived成员函数,打印–called from Derived
}

search接口

与二分查找类似,BST节点的中序遍历即为单调有序向量形式。
如下图,待查找节点e与当前节点比较,若e较大,则深入该节点右子树…依次递归。
查找算法
若查找失效,则将此空节点视作哨兵节点
这样无论是否查找成功,命中节点v都指向e应当存在的位置,_hot指向v的父亲
接口语义

1
2
3
4
5
6
7
8
9
template<typename T> BinNodePosi(T) & BST<T>::search(const T& e) {
return searchIn(_root, e, _hot = NULL);
}
template<typename T>
static BinNodePosi(T) & searchIn(BinNodePosi(T) & v, const T& e, BInNodePosi(T) & hot){
if( !v || ( e == v->data ) ) return v; //待search值e已找到或递归节点v为空
hot = v; //hot指向“命中节点”的父亲
return searchIn( ( ( e < v->data ) ? v->lc : v->rc ), e, hot);
}

插入操作

根据search接口,命中节点v即为待查找节点e应当存在的位置,因此只需将待插入节点作为命中节点v父亲_hot的孩子插入即可。

1
2
3
4
5
6
7
template<typename T> BinNodePosi(T) BST<T>::insert( const T& e) {
if( search(e) ) return search(e); //若待插入节点存在,则停止插入
BinNodePosi(T) & x = new BinNode<T> (e, _hot); //创建新节点x,以e为关键码,_hot为父
_size++;
updateHeightAbove(x);
return x;
}

删除操作

与插入操作类似,首先通过search接口查找需要删除节点位置。
以下是删除操作的代码框架

1
2
3
4
5
6
7
8
template<typename T> bool BST<T>::remove( cosnt T& e ) {
BinNodePosi(T) & x = search(e);
if(!x) return false; //待删除元素不存在,返回
removeAt(x, _hot); //删除操作,需考虑两种情况。
size--;
updateHeightAbove(_hot);
return true;
}

分为两种情况考虑,待删除节点只有一个分支或有两个分支。
出现这种分歧的原因是BST是按照中序遍历序列排列的,插入或删除操作都需要维持原始BST的有序性。
对于单分支,待删除节点下只有比它大(小)的节点,将其孩子直接代替删除位置,不影响BST有序性。
对于多分支,待删除节点的左(右)孩子替换删除位置后,可能会导致新节点的左(右)子树中存在比当前节点大(小)的元素。
如下图,若直接将58代替36会导致40、46、53等比58小的节点存在右子树中。
例
1 单分支
这种情况下,直接删除节点,并将其孩子替换掉原在位置。
2 多分支
保持BST有序性的核心在于将距离待删除节点最近的节点代替删除位置,随后重复单分支操作情况。
综上所述,removeAt()实现代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static BinNodePosi(T) removeAt( BinNodePosi(T) & x, BinNodePosi & hot ) {
BinNodePosi(T) w = x;
BinNodePosi(T) succ = NULL;
if( ! HasLChild(*x) ) succ = x = x->rc; //直接将rc覆盖x即可删除x节点
else if( ! HasRChild(*x) ) succ = x =x->lc;
else {
w = w->succ(); //通过中序遍历获得x的直接后继,即大于x的最小节点
swap( x->data, w->data ); //只将两节点data交换,节点对应的左右孩子指向未变
BinNodePosi(T) u = w->parent;
( ( u == x) ? u->rc : u->lc ) = succ = w->rc;
}
hot = w->parent;
if(succ) succ->parent = hot;
release( w->data ); release(w);
return succ;
}

AVL树

平衡二叉树—-在节点数目固定的前提下,尽可能降低树的高度,即尽可能使兄弟子树的高度彼此接近。渐进意义下树高不超过O(log n)。
平衡因子—-节点v的左右子树高度差。

balFac(v) = height(lc(v)) - height(rc(v))

AVL树—-各节点平衡因子的绝对值不超过1.
接口定义—-由BST派生得来。

1
2
3
4
5
6
7
8
9
10
11
/**********************************
#define stature(p) ((p) ? (p)->height : -1) //节点高度(与“空树高度为-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<typename T> class AVL : public BST<T> {
public:
BinNodePosi(T) insert( const T& e);
bool remove( const T& e);
}

平衡性

设高度为h的子树至少含有S(h)个节点,则根据AVL平衡条件有如下等式成立。
S(h) = S(h-1) + S(h-2) + 1
平衡性
节点删除–失衡
1.节点删除只可能会导致其父节点失衡
2.被删除节点父亲的树高未变(子树高度最大者+1),因而其祖先的平衡因子不会改变。
节点删除
节点插入–失衡
1.节点插入可能会导致其祖先发生一连串的失衡。
2.被删除节点父亲的树高可能发生变化(子树高度最大者+1),因而其祖先的平衡因子可能会打破。
节点插入

重平衡

插入重平衡
只需维护插入节点x导致第一个失衡祖先即可,其余失衡祖先可随之一并重平衡。
设g是首次失衡祖先,通过如下代码即可完成由g找到x的祖先p或v。

1
2
3
4
5
6
7
8
9
10
11
/**************************************
#define IsLChild(x) ( ! IsRoot(x) && ( & (x) == (x).parent->lc ) )
该部分在BinNode中定义
**************************************/
#define tallerChild(x) ( \
stature( (x)->lc ) > stature( (x)->rc ) ? (x)->lc : ( /*左子树高*/ \
stature( (x)->lc ) < stature( (x)->rc ) ? (x)->rc : ( /*右子树高*/ \
IsLChild( * (x) ) ? (x)->lc : (x)->rc /*等高,与父亲同侧者优先*/ \
) \
) \
)

单旋—-g, p, v同侧
BST中的等价变换为上下可变,左右不变
单旋操作
双旋—-g, p, v不在同侧
双旋

1
2
3
4
5
6
7
8
9
10
11
12
13
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++; //创建新节点
//重平衡
for(BInNodePosi(T) g = _hot; g; g = g->parent) { //查找首次遇到失衡祖先节点g
if( !AvBalanced(*g) ) { // 一旦发现g失衡,采用“3+4”算法重平衡
FromParentTo(*g) = rotateAt( tallerChild ( tallerChild(g) ) );
break;
} else //若未失衡,只需更新树高
updateHeight(g);
}
return xx;
}

删除重平衡
如下图操作,重平衡后子树的高度可能继续降低,从而导致失衡向上传播。
单旋
单旋
双旋
双旋

1
2
3
4
5
6
7
8
9
10
template<typename T> bool AVL<T>::remove( const T& e ) {
BinNodePosi(T) x = search(e); if(!x) return false; //待删除节点不存在,返回
removeAt( x, _hot); _size--;
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算法

将操作节点x与其先失衡祖先g以及g更高一侧的子树的孩子节点p, v设置为独立的模块。
整理得到如下两类模块:
3节点模块:g, p, v
4子树模块:g不含p的子树T1, p不含v的子树T2, v的两个子树T3, T4
最终只需按着满足中序遍历方法将上述模块重组为符合BST结构即可。
3+4算法

1
2
3
4
5
6
7
8
9
10
11
12
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->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(b);
}

继而可以将单旋、双旋等操作直接整合如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<typename T> BinNodePosi(T) BST<T>::rotateAt(BinNodePosi(T) v) {
BinNodePosi(T) p = v->parent;
BinNodePosi(T) g = p->parent;
//视p, v, g相对位置分为四种情况
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 /* zag*/
if( IsRChild(*v) ) { /*zag-zag*/
p->parent = g->parent;
return connect34(g, p, v, g->lc, p->lc, v->lc, v->rc);
} else { /*zag-zig*/
v->parent = g->parent;
return connect34(g, v, p, g->lc, v->lc, v->rc, p->rc);
}
}

本文标题:数据结构-7.二叉搜索树

文章作者:Lumo Wang

发布时间:2018年03月05日 - 14:03

最后更新:2018年11月07日 - 15:11

原始链接:https://luameows.github.io/2018/03/05/学习笔记-数据结构-7-二叉搜索树/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

请我喝杯咖啡,我会继续熬夜的~