DSA - 二叉搜索树

来看看新的表情包！
之前玩了太长时间现在真的没时间复习了。总算明白了。
今天考了史纲。

二叉搜索树

接口：

0001 template <typename T, bool H = true> //H：是否按BST规则更新高度
0002 class BST : public BinTree<T> { //由BinTree派生BST模板类
0003 protected:
0004    BNP<T> _x, _p, _r; //记忆内部操作的三个位置：查找的终点与其父亲，以及删除之后的替代者
0005    BNP<T> connect342( BNP<T>, BNP<T>, BNP<T>, BNP<T>, BNP<T> ); //“3+4-2”重构
0006    BNP<T> rotate( BNP<T> ); //局部旋转调整
0007 public: //基本接口：以virtual修饰，派生的BST变种可默认继承，也可根据各自的规则重写
0008    virtual BNP<T> search( const T& ); //查找
0009    virtual BNP<T> insert( const T&, int h = 0 ); //插入（新节点作为叶子，高度为0）
0010    virtual bool remove( const T& ); //删除
0011 }; //BST

任一节点不小于其左后代，不大于其右后代。根节点大于左子树所有节点，小于右子树所有节点（不考虑重复元素）。

经过数学归纳可得中序遍历序列必然单调非降序。

查找：

从根节点出发，逐步缩小查找范围。可以看作二分查找。

0001 template <typename T, bool H> BNP<T> BST<T, H>::search( const T& e ) { //在BST中查找关键码e
0002    for ( _p = nullptr, _x = _root; _x && ( e != _x->data );  ) { //自顶而下
0003       _p = _x; //_p紧随_x，亦步亦趋
0004       _x = ( e < _p->data ? _p->lc : _p->rc ); //向左或右，x逐层深入
0005    } //直至_x命中，或抵达nullptr
0006    return _x; //无论命中与否，_x为终点，_p为其父
0007 } //特别地，命中于树根时，_x == _root且_p == nullptr；树空时，_p == _x == nullptr

成功时，x 记忆 e 所属节点，p 是 x 的父亲；失败时，x 为空，p 记忆的节点可以把 e 当作儿子接入（树空为空）。

时间复杂度：每一步需要 O (1) 时间，累计 O (depth (x))，depth 是从根节点到 x 所经过的边数。

插入：

通过 search (e) 确定插入位置 p，再插入节点 e

返回之前需要更新全树的规模和高度。

时间复杂度和 depth 成正比。

0001 template <typename T, bool H> BNP<T> BST<T, H>::insert( const T& e, int h ) {
0002    if ( search( e ) ) return _p = _x; //有相等元素时，插入无效（用重复的_p和_x标记）
0003    _x = new BinNode<T>( e, _p, nullptr, nullptr, h ); //在_x处创建新节点，以_p为父
0004    ( _p ? ( *_x < *_p ? _p->lc : _p->rc ) : _root ) = _x; //_p以_x为子：左小右大
0005    if ( H && _p ) //更新祖先们的高度
0006       _p->updateHeightAbove(); //派生的AVL树、红黑树会重写insert()，并以自己的方式更新高度
0007    _size++; return _x; //新插入的节点，必为叶子
0008 } //无论e此前是否存在，返回时总有_x->data == e

删除：

单分支：

删除的节点 (search 之后得到的 x) 某一子树为空（或者为叶子节点），将该节点替换为另一棵子树。

双分支：

找到不小于 x 节点的最小的元素，即 x 右子树的左藤蔓的末尾，记 s。交换 s 和 x，s 必然没有左孩子，于是化归成为单分支情况删除原来 s 的位置。

时间复杂度被树高控制。

0001 template <typename T, bool H> bool BST<T, H>::remove( const T& e ) {
0002    search( e ); if ( !_x ) return false; //确认目标存在（留意_p的设置）
0003    if ( _x->lc && _x->rc ) { //双子情况，可转化为单子情况...
0004       BNP<T> s = eov(_x->rc); swap( _x->data, s->data ); //直接后继，s代_x僵
0005       _x = s; _p = s->parent; //转移删除操作的焦点
0006    } //以下，_x至多只有一个孩子（可左可右）
0007    _r = _x->lc ? _x->lc : _x->rc; //以单子r为接替者（仍可能是nullptr）
0008    if ( _r ) _r->parent = _p; //_r以_p为父
0009    ( _p ? ( _p->lc == _x ? _p->lc : _p->rc ) : _root ) = _r; //_p以_r为子
0010    delete _x; _x = nullptr; _size--; //释放_x，更新全树规模
0011    if ( H && _p ) //更新祖先们的高度
0012       _p->updateHeightAbove(); //派生的AVL树、红黑树会重写insert()，并以自己的方式更新高度
0013    return true;
0014 } //删除成功与否，由返回值指示

平衡的二叉搜索树

BST 在最坏情况下，线性正比于树高。

随机生成：等随机排列插入二叉搜索树，平均高度 O (logn)

随机组成：等随机产生各种二叉搜索树，$S (n)=\sum {S (k-1)*S (n-k)}$，卡特兰数，平均高度 $O (\sqrt {n})$

高度渐进于 O (logn) 称平衡的二叉搜索树

约定限制条件，每种操作均会产生 O (logn) 违例但能在 O (logn) 时间内修复

zig 和 zag 操作

zig / zag 均是常数操作：以 zig 为例，v 的左指针从指向 c 到指向 Tc；c 的右指针从指向 Tc 到指向 v；父节点的儿子指针修改；parent 指针修改

高度变化：子树的高度变化量不超过 1

AVL 树

平衡因子 balFac (v)=height (lc (v))-height (rc (v))，限制条件每个节点 balFac 绝对值 <=1

证明渐进平衡：固定高度 h 考查节点最少的 AVL 树，规模记作 S (h)

于是 S (h)=S (h-1)+S (h-2)+1，S (h)+1 构成斐波那契数列，S (h) 成指数，$h < log_\phi {n}$，高度关于 n 成对数

斐波那契树：内部节点的 balFac=±1，删除任何节点导致失衡，高度下降

失衡 / 复衡

插入

插入一个 x，导致一系列祖先失衡，最低者不低于 x 祖父（x 的父亲原先一定有一条手是空的而被 x 填上，而原来又是符合限制条件，所以不会失衡）

找到 g，然后记 p = tallerChild (g)，g 的更高的子树；v = tallerChild (p)，记 T0 = h

T2,T3 插入前一定是都是 h-1：g 是新的失衡节点，p 和 v 都没有失衡，如果 T2T3 不相等，插入一个新节点要么 v 就失衡要么高度变化不能向上传递导致 g 不能失衡

T1 插入前一定是 h：大了会让 g 失衡，小了会让 p 失衡

单旋情形：

LL / RR（图中 RR），表示 p 和 v 都是右子树角色。根据推导，新插入的黄色块一定位于图中之一。g 左转一下即可。

双旋情形：

LR / RL（图中 RL）

右转 p 左转 g

如此 g 可以复衡，更高的祖先也复衡因为树高不改变。

0001 template <typename T> BNP<T> AVL<T>::insert( const T& e ) {
0002    BST::insert( e ); if ( _p == _x ) return _x; //先按BST规则插入
0003    for ( BNP<T> g = _p; g; g = g->parent ) { //逐层上溯历代祖先g
0004       if ( !AvlBalanced( g ) ) g = rotate( g ); //一旦g失衡，则经旋转使之复衡
0005       g->updateHeight(); if ( 0 == BalFac( g ) ) break; //可能提前终止上溯
0006    } //局部子树复衡后，高度必然复原；所有祖先亦必复衡：累计至多O(1)次旋转
0007    return _x; //插入成功
0008 } //insert

删除

瞬时最多一个节点失衡，可能是 x 的父亲。但是复衡之后子树的高度不一定复原，更高的祖先可能依然失衡，删除每次都要遍历直到祖先平衡。于是最多需要左 O (logn) 次调整

单旋：

LL / RR（图中 LL）

原先 T3 高度 h，删了一个之后变 h-1, 于是 p 高度 h + 1, 黄色块一定至少存在其中一个，红色块可能有也可能没有。红色块有的话说明 p 左右子树高度相当。

红色块歧义：规定等高时与 x 同侧优先，可以增加单旋减少双旋

0001 #define TallerChild(x) ( \
0002    Height( (x)->lc ) > Height( (x)->rc ) ? (x)->lc : ( /*左高*/ \
0003    Height( (x)->lc ) < Height( (x)->rc ) ? (x)->rc : ( /*右高*/ \
0004       ( (x)->parent && ( (x) == (x)->parent->lc ) ) ? (x)->lc : (x)->rc \
0005    ) \
0006    ) \
0007 ) //在左、右孩子中取更高者；等高时，与x同侧者优先

g 右旋一次。

双旋：

LR / RL（图中 LR），黄块至少有 1 个。

由于等高时优先单旋，所以 p 的左子树严格比 v 高度小，不存在 “红色块”

0001 template <typename T> bool AVL<T>::remove( const T& e ) {
0002    if ( !BST::remove( e ) ) return false; //先按BST规则删除
0003    for ( BNP<T> g = _p; g; g = g->parent ) { //逐层上溯历代祖先g
0004       if ( !AvlBalanced( g ) ) g = rotate( g ); //每当g失衡，都经旋转使之复衡
0005       g->updateHeight(); if ( 0 != BalFac( g ) ) break; //可能提前终止上溯
0006    } //局部子树复衡后，高度未必复原；更高祖先仍或失衡：累计可能Omega(logn)次旋转
0007    return true; //删除成功
0008 } //remove

3 + 4-2 重构

只是把 zig，zag 封装起来而已。

AVL 所有旋转操作都可以用同一种方式表示。0,3 在旋转中不变。

0001 template <typename T, bool H>
0002 BNP<T> BST<T, H>::connect342( BNP<T> a, BNP<T> T1, BNP<T> b, BNP<T> T2, BNP<T> c ) {
0003    b->attachLc( a ); a->attachRc( T1 ); a->updateHeight();
0004    b->attachRc( c ); c->attachLc( T2 ); c->updateHeight();
0005    return b; //该子树新的根节点，其高度，由调用者负责更新
0006 } //connect342

0008 template <typename T, bool H> BNP<T> BST<T, H>::rotate( BNP<T> g ) { //g->height > 1
0009    BNP<T> p = TallerChild(g); int TurnP = (p == g->rc);
0010    BNP<T> v = TallerChild(p); int TurnV = (v == p->rc);
0011    BNP<T> r = ( TurnP == TurnV ) ? p : v; //子树新的根节点
0012    ( FromParentTo(g) = r )->parent = g->parent; //须保持与母树的联接
0013    switch( ( TurnP << 1 ) | TurnV ) { //视p、v的拐向，无非四种情况
0014          case  0b00   : return connect342( v, v->rc, p, p->rc, g ); //LL
0015          case  0b01   : return connect342( p, v->lc, v, v->rc, g ); //LR
0016          case  0b10   : return connect342( g, v->lc, v, v->rc, p ); //RL
0017       default/*0b11*/ : return connect342( g, p->lc, p, v->lc, v ); //RR
0018    } //switch
0019 } //rotate