DSA - 高级搜索树

早上考了 OOP 感觉还好，只是录屏有点意料之中的问题可能会被批判。

Splay 树

局部性：节点一旦被访问很可能继续被访问。考虑访问一个节点就把节点推送到根方便下次访问。

深度为 d 的节点经过 d 次旋转一定能到达根节点。

对于每次操作，最坏情况需要 O (n) 的时间。

双层伸展：向上追溯两层而不是只考虑一层。每次根据祖孙三代的相对位置进行两次旋转。

LR / RL：和单层伸展相同

LL / RR：上面是单层下面是双层。看到双层是先转爷爷再转爸爸。

L / R：没有祖父，只会在最后一步出现。只需单次旋转。

均摊分析

定义势能：$\Phi (S)=\sum_{v \in S}\Phi (v)=\sum {log (size (v))}=log (size (S))$，越平衡的树势能越小

考查查找操作，在规模固定为 n 的伸展树中查找 v，设 v 深度 d，总共伸展⌈d / 2⌉步, 每一步只有三种情况

总之，均摊复杂度 O (logn) 而且局部性强，如果反复访问任一个子集均摊成本为常数

插入

首先查找 search (e)，把 e 的临近者伸展到根。创建新的根节点作为插入节点。看情况当左父亲还是右父亲。

0001 template <typename T> BNP<T> Splay<T>::insert( const T& e ) { //将关键码e插入伸展树中
0002    if ( !_root ) { _size = 1; return _root = new BinNode<T>( e ); } //原树为空
0003    search( e ); if ( e == _root->data ) return _root; //查找成功（否则，_p已伸展至根）
0004    if ( _p->data < e ) //在右侧嫁接（rc或为空，lc == _p必非空）
0005       { _root = new BinNode<T>( e, nullptr, _p, _p->rc ); _p->rc = nullptr; }
0006    else  //e < _p->data：在左侧嫁接（lc或为空，rc == _p必非空）
0007       { _root = new BinNode<T>( e, nullptr, _p->lc, _p ); _p->lc = nullptr; }
0008    _p->updateHeightAbove(); _size++; return _root;
0009 } //insert

删除

先 search (e) 并拿走伸展到根的节点 e。此时在右子树中 search (e) 必然找不到，而会让右子树中最小的节点伸展到右子树根。这个点没有左子树。把这个节点和左子树连接在一起。

0001 template <typename T> bool Splay<T>::remove( const T& e ) {
0002    search(e); //首先做一次查找
0003    if ( !_root || e != _root->data ) return false; //若成功，则命中节点必已伸展至根
0004    BNP<T> L = _root->lc, R = _root->rc; delete _root; _size--; //记下子树L、R后，释放之
0005    if ( !R ) {
0006       if ( _root = L ) //若R空，则
0007          _root->parent = nullptr; //L即是余树
0008    } else { //否则，在R中再次查找e：尽管这次查找必然失败...
0009       (_root = R)->parent = nullptr; search( e ); //...但R的最小节点会伸展为根，且无左孩子
0010       _root->attachLc( L ); _root->updateHeight(); //故只需令L作为其左子树，便成一棵完整的树
0011    } //else
0012    return true;
0013 } //remove

B 树

分级存储的现实背景：高速、小容量的存储层级到慢速，大容量的存储层级。需要尽可能利用空间局部性，尽可能访问连续的内容。

把 g 代合并成一个多路节点，存储 2^g-1 个关键码，有 2^g 个分支

要求内部节点在满载和半载之间，即限制分支数上下限：⌈b / 2⌉=a<=way<=b，称 (a,b) 树

根节点至少两只手，除非节点不够。

理想平衡：所有外部节点都处于同一深度。

每个节点实际都是一个有序向量，内部每一层都满足层次遍历有序：同一个节点内部的分支子树满足左小右大

0001 template <typename T> struct BTNode;
0002 template <typename T> using BTNP = BTNode<T>*; //B-Tree Node Position
0003 template <typename T> struct BTNode {
0004    BTNP<T> parent; Rank height; //Height(nullptr) = 0，其余递推
0005    Vector<T> key; Vector<BTNP<T>> way; //关键码向量、孩子向量（后者长度总是多一个单位）
0006    BTNode( Rank b, Rank h = 1, BTNP<T> c = nullptr ) //b阶
0007       : key(b), way(b+1), parent(nullptr), height(h) //初始时，无关键码
0008       { if (c) { way.insert(c); c->parent = this; } } //但可能会有个分支
0009 }; //BTNode

查找

从根节点开始在当前节点中顺序查找，找到关键码就返回；没找到就找到对应的分支继续向下

0001 template <typename T> BTNP<T> BTree<T>::search( const T& e ) {
0002    for ( _x = _root; ; _x = _x->way[_k+1] ) { //自根而下，逐层深入（I/O）
0003       _k = _x->key.search( e ); //简便起见用了二分查找，但此时改用顺序查找亦无妨
0004       if ( (-1 != _k) && (e == _x->key[_k]) ) return _x; //命中于节点_x->key[_k]
0005       if ( !_x->way[_k+1] ) return nullptr; //失败于叶节点_x
0006    }
0007 } //search

性能取决于读磁盘的 IO 树，也就是向下找分支的次数，不超过树高。而最高的 B 树也比 BST 矮的多。

插入

0001 template <typename T> bool BTree<T>::insert( const T& e ) {
0002    if ( search( e ) ) return false; //确认e尚不存在（查找终止于叶节点_x->key[_k]）
0003    _x->key.insert( _k+1, e );  _x->way.insert( nullptr ); //插入关键码，并增加一个外部节点
0004    _N++; solveOverflow(); return true; //如上溢，则修复之
0005 } //insert

如果一个节点内部的关键码超了就修复上溢。由于都是在叶子处插入新点，所以外部节点始终处于叶子脚下保持同一高度。

每次发生上溢就分裂，这样保证分支不丢但能让一个节点到上一层去。把中位节点放到上层。而放到上层节点的位置恰好是通向该层分支的位置。

0001 template <typename T> struct LinkParent {
0002    BTNP<T> parent; LinkParent(BTNP<T> p) : parent(p) {}
0003    void operator() (BTNP<T> x) { if (x) x->parent = parent; }
0004 }; //LinkParent
0005 
0006 template <typename T> void BTree<T>::solveOverflow() { //修复上溢
0007    while (_b < _x->way.size()) { //_x上溢：|way|-1 == b == |key|
0008       Rank s = _b - _a + 1; //_x将以中位数为界，将后缀转移至
0009       BTNP<T> u = new BTNode<T>(_b, _x->height); //分裂出来的新节点u
0010       u->key.insert(0, _x->key, s, _b); _x->key.remove(s, _b); //关键码
0011       u->way.insert(0, _x->way, s, _b+1); _x->way.remove(s, _b+1); //孩子
0012       u->way.traverse(LinkParent<T>(u)); //u的孩子们统一指向u
0013       BTNP<T> p = _x->parent; //_x的父亲p：若为空，则创建之，且
0014       if (!p) _root = p = new BTNode<T>(_b, 1 + _x->height, _x); //全树长高一层
0015       _k = p->way.find(_x); //确定_x在p中的秩
0016       p->key.insert(_k, _x->key.remove(s - 1)); //轴点上升
0017       p->way.insert(_k+1, u); u->parent = p; //u与p互联
0018       _x = p; //上升一层，继续修复——至多可能上溯O(logn)层、分裂O(logn)次
0019    } //while
0020 } //solveOverflow

删除

找对应右分支的左藤蔓终点交换，删除 e 和其下的外部节点。让删除操作都是在最底层进行，维护平衡性。

下溢：

情况 1L: 有一个足够胖的左兄弟，通过旋转向兄弟借关键码。

0010       BTNP<T> ls  =  (0 < _k) ? p->way[_k-1] : nullptr; //左兄弟
0011       if (ls && (_a < ls->way.size())) { //情况#1L：_x有个足够“胖”的左兄弟
0012          _x->key.insert(0, p->key[_k-1]); //p的轴点关键码转入_x（作为最小关键码）
0013          p->key[_k-1] = ls->key.remove(); //ls的最大关键码转入p
0014          _x->way.insert(0, ls->way.remove()); //ls的最大孩子过继给_x
0015          if (_x->way[0]) _x->way[0]->parent = _x; //作为_x的最小孩子
0016          break; //随即收工
0017       } //情况#1L

情况 1R: 找右兄弟借，省略。

情况 2：合并，有可能触发连锁合并，需要 while

0026       //情况#2：左、右兄弟均或不存在或不够“胖”，但至少存在其一
0027       if (ls) rs = _x; else { ls = _x; _k++; } //以ls、rs命名之后，以下将rs归入ls
0028       ls->key.insert(p->key.remove(_k-1)); p->way.remove(_k); //p吐还轴点
0029       rs->way.traverse(LinkParent<T>(ls)); //rs的孩子们统一指向ls
0030       ls->way.insert(rs->way); ls->key.insert(rs->key); //过继子树及关键码
0031       delete rs; //右兄弟功成身退
0032       _x = p; //上升一层，继续修复——至多可能上溯O(logn)层、合并O(logn)次

特判树根，缩小一层：

0004       if (!p) { //情况#0：已到树根
0005          if ((_x->key.size() < 1) && (0 < _N)) //若树根已空（树还没空），则
0006             { _root = _x->way[0]; _root->parent = nullptr; delete _x; } //整树降低一层
0007          break; //随即收工
0008       } //情况#0

红黑树

并发优势：结构变动小

持久性：拓扑结构稳定

结构

0. 由红黑两种节点构成；1. 树根必定是黑色；2. 外部节点均为黑色；3. 红节点的孩子必定黑色（红节点必有黑父亲；没有同为红色的父子）

4. 从任何节点 x 到 x 的每一个后代 nullptr，经过的黑点数量相等，称为黑高度。

将黑节点提升到和红节点等高处，发现每一棵红黑树都对应一个 (2,4) 树。

将黑节点和红孩子视作关键码并合并，有黑/黑红/红黑/红黑红 四种可能

红黑树也是 BBST：路径总节点数 = 红节点 + 黑节点，而 r<=b，所以 h<=2b-1<2b，黑高度上限 log2 (n + 1),因为 (2,4) 树每个节点都有黑节点，而高度不超过满树。h < 2log2 (n + 1)

复用 BST 的 search 接口。

插入

0001 template <typename T> BNP<T> RedBlack<T>::insert( const T& e ) {
0002    BST::insert( e, 1 ); //先按BST规则插入_x（黑高度为1）并染红（祖先黑高度不变），则
0003    if ( _p != _x ) solveDoubleRed(); //条件1、2、4依然满足，但3未必，或需双红修正
0004    return _x; //无论原树中是否存有e，返回时总有_x->data == e
0005 } //insert

双红修正：图中第三种情况违背了条件 3。考虑 x 父亲的兄弟的颜色：

如果 u 是黑色：

旋转 g 点，按照 AVL 的失衡旋转那样，最后一定有红的被转到上面并回复平衡。根染黑把原来的根染红即可。

不能只染色不旋转：这样 g 变成红色 p 变成黑色之后，从 B 树视角，g 和上面的合并，px 在一起，被撕裂了。

u 是红色：

B 树视角相当于发生上溢。发生三次染色但是没有旋转。g 上去之后可能继续发生双红。还是当作行插入的节点继续迭代，直到所有条件都满足了。如果蔓延到根则把根染黑。

仅需 O (logn) 时间，有 O (logn) 次染色和 O (1) 次旋转

删除

删除操作先用 BST 的删除，转到只有一个子树的节点删除。

0001 template <typename T> bool RedBlack<T>::remove( const T& e ) {
0002    if ( !BST::remove( e ) ) return false; //先按BST规则删除_p的孩子_x，接替者为_r
0003    if ( !RbtBalanced(_p) ) //若失衡（即原_x为黑）
0004       if ( IsRed(_r) ) //若接替者_r为红，则
0005          _r->color = RBT_BLACK; //只需令其继承_x的黑色，黑高度随即复原
0006       else //否则（即原_x及_r均为黑色）
0007          solveDoubleBlack(); //从_p出发，做双黑修正
0008    return true;
0009 } //remove

我还是没搞清楚为什么要搞一个虚拟子树 k 出来。

如果 x 和 r 其中有一个是红，直接删掉，让 r 继承黑色不会影响黑高度。

双黑修正：删掉 x 并以 r 代之必然失衡。

B 树视角：双黑代表下溢，因为删掉了 B 树格子的代表人，需要旋转借关键码。

x 的兄弟 s，考查 s 和他的孩子。

s 黑色且孩子至少有 1 个红节点：

s 为黑且两个孩子均黑：

B 树视角，p 红的情况，说明 p 依附于上层的某个黑色节点，把 p 拉下来合并不会对上层造成影响。如果要合并的话，s 必须染红才能和 r 在一起。

B 树视角，p 黑说明上层只有 p 一个节点，拉下来会导致上层空了，继续向上传递。

因为在 x 还在的时候是平衡的，所以 r 视作带 2 个黑色权重，现在 p 的黑高度不平衡了。

s 红色：

太绕了。

跳表

逐层逐渐稀疏的列表依次叠放，横向成层，纵向成塔。

0001 template <typename T> struct Tower;
0002 template <typename T> using TowerPosi = LNP<Tower<T>>;
0003 template <typename T> struct Brick { //砖（塔的每一层）
0004    TowerPosi<T> pred, succ; //前、后相邻的塔
0005    Brick( TowerPosi<T> p = nullptr, TowerPosi<T> s = nullptr ) : pred(p), succ(s) {}
0006 }; //Brick
0007 #define key(t) ((t)->data.data) //快捷方式：塔对应的关键码
0008 #define tower(t) ((t)->data.tower) //快捷方式：塔身
0009 #define height(t) (tower(t).size()) //快捷方式：塔高
0010 template <typename T> struct Tower { //塔
0011    T data; Vector<Brick<T>> tower; //关键码、塔身（由砖构成的向量）
0012    Tower( T e = T{} ): data(e) {} //初建的塔，塔身均为空
0013 }; //Tower
0014 template <typename T> struct Skiplist : public List<Tower<T>> { //跳转表（由塔构成的列表）
0015    TowerPosi<T> _x; //记忆最近接受操作的塔
0016    TowerPosi<T> search( const T& ); //查找
0017    TowerPosi<T> insert( const T& ); //插入
0018    bool remove( const T& ); //删除
0019 }; //Skiplist

设 Sk 中的关键码有 p = 1 / 2 的概率在 Sk + 1 中出现。约定塔高为初始 1，逐渐生长。p 概率能继续生长一层，(1-p) 的概率停止生长。

P (h = k)=(1-p) p^(k-1),E (h)=1/(1-p)=O (1),空间成线性。

插入删除

插入：首先在底部找到对应位置，然后抛硬币盖塔（如果超过左右哨兵高度，哨兵会加盖）；寻找同一层的前驱后继，利用 h-1 层的前驱向前摸直到找到第一个高度 > h 的塔，链接。（不变性保证 h-1 层的前驱的高度一定不小于 h）

0001 template <typename T> TowerPosi<T> Skiplist<T>::insert( const T& e ) {
0002    search( e ); if ( (_x != head) && (e == key(_x)) ) return _x; //禁止重复
0003    TowerPosi<T> pred = _x, succ = _x->succ; //同层的前驱（或为head）、后继（或为tail）
0004    _x = List::insert( _x, Tower<T>( e ) ); //紧邻于_x之右侧，创建一座空塔
0005    for ( Rank h = 0; !h || (rand()&1); h++ ) { //积砖成塔（至少一层）
0006       if ( height(head) < h+1 ) { //若总高度不足h
0007          tower(head).insert( Brick<T>( nullptr, tail ) ); //则需创建
0008          tower(tail).insert( Brick<T>( head, nullptr ) ); //一层空表
0009       } //if
0010       while ( height( pred ) == h ) //踏过若干塔顶，找到前驱
0011          pred = tower( pred )[h - 1].pred;
0012       while ( height( succ ) == h ) //踏过若干塔顶，找到后继
0013          succ = tower( succ )[h - 1].succ;
0014       tower( _x ).insert( Brick<T>( pred, succ ) ); //新塔长高一层，并
0015       tower( pred )[h].succ = tower( succ )[h].pred = _x; //与前驱、后继连接
0016    } //for
0017    return _x; //返回新塔
0018 } //insert

删除比较简单。

0001 template <typename T> bool Skiplist<T>::remove( const T& e ) {
0002    search( e ); if ( (_x == head) || (e != key(_x)) ) return false; //确保目标存在
0003    for ( Rank h = height(_x) - 1; -1 != h; h-- ) { //自顶而下地
0004       Brick<T>& b = tower(_x)[h]; //对每一块砖
0005       tower(b.pred)[h].succ = b.succ; //恢复其前驱与
0006       tower(b.succ)[h].pred = b.pred; //后继之间的链接
0007       if ( head == b.pred && b.succ == tail ) //并及时地将空层
0008          { tower(head).remove(h); tower(tail).remove(h); } //清理掉
0009    } //for
0010    List::remove( _x ); return true; //最后销毁整塔，便可收工
0011 } //remove

查找

尽可能在该层向右走，走过了才考虑向下走。为什么是塔顶：因为如果不是塔顶的话，说明下一个塔在更高处还有砖块，那在更高的地方就应该跳到下一个塔了。

0001 template <typename T> TowerPosi<T> Skiplist<T>::search( const T& e ) {
0002    _x = head; //从head塔的顶层出发
0003    for ( Rank h = height(_x) - 1; -1 != h; h-- ) //逐层下降，直至底层
0004       while ( ( tower(_x)[h].succ != tail ) && ( key(tower(_x)[h].succ) <= e ) ) //在每一层
0005          _x = tower(_x)[h].succ; //都尽可能地右移
0006    return _x == head ? nullptr : _x; //最终止步于不大于e的最后一座塔
0007 } //search

复杂度：

纵向分析，单个塔到达 k 层的概率是 p^k，设有 n 座塔，有塔超过 k 层的概率 <=n * p^k，跳表的高度几乎就是 O (logn)，于是期望要走 O (logn)

横向分析，由于每一层经过的都是塔顶而且紧邻。同一层紧邻塔顶构成区间的长度记 Y，构成几何分布，长度期望是常数，O (logn) 层就是 O (logn)

于是复杂度 O (logn)