清华邓俊辉数据结构学习笔记（4） - 二叉搜索树、高级搜索树_d元全树

第七章 二叉搜索树

（a）概述

循关键码访问：数据项之间，依照各自的关键码彼此区分（call-by-key），条件是关键码之间支持大小比较与相等比对，数据集合中的数据项统一地表示和实现为词条entry形式。
词条

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;}//不等
}
1
2
3
4
5
6
7
8
9
10

二叉搜索树：节点~ 词条~ 关键码
顺序性：任一节点均不小于其左后代，不大于其右后代，等效于任一节点均不小于/不大于其左/右孩子。为简化起见，禁止重复词条，这种简化应用中不自然，算法上无必要。（顺序性虽然只是对局部特征的刻画，但由此却可导出某种全局特征）
单调性：BST的中序遍历序列，必然单调非降，这一性质也是BST的充要条件。
BST模板类

template <typename T> class BST:  public BinTree<T>{//由BinTree派生
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
2
3
4
5
6
7
8
9
10
11
12
13

（b）算法及实现

查找算法：从根节点出发，逐步地缩小查找范围，直到发现目标（成功），或查找范围缩小至空树（失败），对照中序遍历序列可见，整个过程可视作是在仿效有序向量的二分查找。
实现

template <typename T> BinNodePosi(T) & BST<T>::search(const T & e)
{return searchIn( _root, e, _hot = NULL); } //从根节点启动查找
static BinNodePosi(T) & searchIn(
	BinNodePosi(T) & v, //当前子根
	const T & e, //目标关键码
	BinNodePosi(T) & hot) //记忆热点
{
	if (!v || (e == v-> data)) return v; //足以确定失败、成功
	hot = v; //记下当前非空节点
	return searchIn(((e < v->data) ? v->lChild : v->rChild),e,hot); 
}//运行时间正比于返回节点v的深度，不超过树高O(h)
1
2
3
4
5
6
7
8
9
10
11

查找：接口语义
返回的引用值：成功时，指向一个关键码为e且真实存在的节点；失败时，指向最后一次试图转向的空节点NULL，不妨假想此空节点，转换为一个数值为e的哨兵节点，如此依然满足BST的充要条件。
无论成功与否，返回值总是等效地指向命中节点，而**_hot**总是指向命中节点的父亲。
插入算法：先借助search(e)确定插入位置及方向，再将新节点作为叶子插入。若e尚不存在，则 _hot为新节点的父亲，v = search(e)为_hot对新孩子的引用。
实现

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 
} //O(h) 对于首个节点插入之类的边界情况，均可正确处置
1
2
3
4
5
6
7
8

删除算法

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;
}//删除成功与否，由返回值指示
1
2
3
4
5
6
7
8

删除：情况一
若x的某一子树为空，则可将其替换为另一子树，如此操作之后二叉树的拓扑结构依然完整，顺序性依然满足。

template <typename T> static BinNodePosi(T) removeAt( BinNodePosi(T) & x, BinNodePosi(T) & hot){
	BinNodePosi(T) w = x; //被摘除的节点
	BinNodePosi(T) succ = NULL; //被删除节点的接替者
	if (!HasLChild( *x )) succ = x = x->rChild; //左子树为空
	else if (!HasRChild( *x )) succ = x = x->lChild; //右子树为空
	else{/*...左右子树并存...*/}
	hot = w->parent; //被删除节点的父亲
	if (succ) succ->parent = hot; //将被删除节点的接替者与hot相联
	release(w->data); release(w); //释放被删除的节点
	return succ; //返回被接替者
} // O(1)
1
2
3
4
5
6
7
8
9
10
11

删除：情况二
被删除节点两子树都不为空。

template <typename T> static BinNodePosi(T) removeAt( BinNodePosi(T) & x, BinNodePosi(T) & hot){
	/*......*/
	else{
		w = w->succ(); swap( x->data, w->data); //令*x与其后继*w互换数据
		BinNodePosi(T) u = w->parent; //原问题转化为摘除非二度节点w
		( u==x ? u->rChild : u->lChild )= succ = w->rChild;
	}
	/*......*/
}
1
2
3
4
5
6
7
8
9

（c）平衡与等价

BST = Vector + List
n个节点的BST若随机组成成，有n!种（catalan(n)），若能缩小到O(logn)，甚至O(n^(1/2))，则理想。
理想平衡：节点数目固定时，兄弟子树高度越接近平衡，全树也将倾向于更低，由n个节点组成的二叉树，高度不低于[log2n]，恰好为[log2n]时称作理想平衡（CBT）。
适度平衡：理想平衡出现概率低，维护成本高，可适当放松标准，当高度渐进地不超过O(logn)，可称作适度平衡，适度平衡的BST称作平衡二叉搜索树（BBST）。
等价BST：上下可变（联结关系不尽相同，承袭关系可能颠倒），左右不乱（中序遍历序列一致，全局单调非降）。
等价变换+旋转调整：zig(v)，zag(v)

（d）AVL树

平衡因子：balFac(v) = height( lc(v) ) - height( rc(v) )，对任意的v，|balFac(v)|≤1。
AVL = 适度平衡
（1）height(AVL) = O(logn)，n = Ω( 2 ^ height(AVL) )
（2）高度为h的AVL树，至少包含S(h) = fib(h+3) - 1个节点。数学归纳：S(h) = 1 + S(h - 1) + S(h - 2)，令T(h) = S(h) + 1，则T(h) = T(h-1) + T(h-2) = fib(h+3)。
AVL：接口

#define Balanced(x) \ //理想平衡
	(stature((x).lChild)==stature((x).rChild))
#define BalFac(x) \ //平衡因子
	(stature((x).lChild)-stature((x).rChild))
#define AvlBalanced(x) \ //AVL平衡条件
	((-2 < BalFac(x))&&(BalFac(x)<2))
template <typename T> class AVL: public BST<T>{
public: //BST::search()等接口可直接沿用
	BinNodePosi(T) insert( const T & ); //插入重写
	bool remove( const T & );//删除重写
}
1
2
3
4
5
6
7
8
9
10
11

插入：单旋（zigzig / zagzag，同时可能有多个失衡节点，最低者g不低于x祖父，g经单旋调整后复衡，子树高度复原；更高祖先也必平衡，全树复衡）；
插入：双旋（zigzag/zagzig）
插入：实现

template <typename T> BinNodePosi(T) AVL<T>::insert( const T & e){
	BinNodePosi(T) & x = search(e);if(x) return x; //若目标尚不存在
	x = new BinNode<T>(e,_hot); size_++; BinNodePosi(T) xx = x; //则创建x
	//从x的父亲出发逐层向上，依次检查各代祖先g
	for ( BinNodePosi(T) g = x->parent; g; g = g->parent)
		if (!AvlBalanced(*g)){//一旦发现g失衡
			FromParentTo(*g)=rotateAt(tallerChild(tallerChild(g)));
			break;//g复衡后局部子树高度必复原，其祖先也如此
		}else//否则（在依然平衡的祖先处）
			updateHeight(g);//更新其高度（平衡性虽不变，高度却有可能改变）
	return xx;//返回新节点：至多只需一次调整
}
1
2
3
4
5
6
7
8
9
10
11
12

删除：单旋（同时至多一个失衡节点g，首个可能就是x的父亲_hot，g经单旋调整后复衡，子树高度未必复原，更高祖先仍可能失衡，因有失衡传播现象，可能需要做O(logn)次调整）
删除：实现

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); //更新其高度
	}//可能做Ω(logn)次调整；无论是否做调整，全树高度均可能下降
	return true; //删除成功
}
1
2
3
4
5
6
7
8
9
10

3+4重构：算法
设g(x)为最低的失衡节点，考察祖孙三代g ~ p ~ v，按中序遍历次序，将其命名为a<b<c，它们共拥有互不相交的四棵（可能为空的）子树，按中序遍历次序，将其命名为T0<T1<T2<T3。
实现

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->lChild = T0, if (T0) T0->parent = a;
	a->rChild = T1, if (T1) T1->parent = a; updateHeight(a);
	c->lChild = T2, if (T2) T2->parent = c;
	c->rChild = T3, if (T3) T3->parent = c; updateHeight(c);
	b->lChild = a; a->parent = b;
	b->rChild = c; c->parent = b; updateHeight(b);
	return b;//该子树新的根节点
}
1
2
3
4
5
6
7
8
9

统一调整：实现

template <typename T> BinNodePosi(T) BST<T>::rotateAt(BinNodePosi(T) v){
	BinNodePosi(T) 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->lChild,v->rChild,p->rChild,g->rChild);
		}else{//zig-zag
			v->parent = g->parent;//向上联接
			return connect34(p,v,g,p->lChild,v->lChild,v->rChild,g->rChild);
		}
	else{/*...zag-zig & zag-zag...*/}
}
1
2
3
4
5
6
7
8
9
10
11
12

综合评价
优点：无论查找、插入或删除，最坏情况下的复杂度均为O(logn)，O(n)的存储空间。
缺点：借助高度或平衡因子，为此需改造元素结构或额外封装（splay）；实测复杂度与理论值有差距（插入/删除后的旋转成本不菲，删除操作后最多需旋转Ω(logn)次，若需频繁进行插入删除未免得不偿失）；单次动态调整后，全树拓扑结构变化量可能高达Ω(logn)。

第八章 高级搜索树

（a）伸展树

局部性：刚被访问过的数据，极有可能很快地再次被访问，这一现象在信息处理过程中屡见不鲜，如BST，下一个将要被访问的节点，极有可能就在刚被访问过节点的附近。连续的m次查找（m>>n=|BST|），采用AVL共需 O(mlogn) 时间，利用局部性能否更快？（仿效自适应链表）
逐层伸展：节点v一旦被访问，随即转移至树根。一步一步往上爬，自下而上，逐层单旋（zig( v->parent )，zag( v->parent )），直到v最终被推送至根。
最坏情况：在分别访问1~5后，全树复原。每一周期累计Ω(n^2)，分摊Ω(n)。
双层伸展：向上追溯两层，而非一层，反复考察祖孙三代 g = parent( p), p = parent(v), v，根据它们的相对位置经两次旋转使v上升两层，成为子树根。
zig-zag / zag-zig与AVL树双旋完全等效，与逐层伸展别无二致。折叠效果：一旦访问最坏节点，对应路径长度随即减半，最坏情况不致持续发生，单趟伸展操作分摊 O(logn) 时间。
特殊情况：若v只有父亲，没有祖父，此时必有parent(v) == root(T)，且每轮调整这种情况最多在最后出现一次，视具体形态做单次旋转zig( r )或zag( r )。
实现：伸展树接口

template<typename T> class Splay:: public BST<T>{//由BST派生
protected: BinNodePosi(T) splay(BinNodePosi(T) v); //将v伸展至根
public: //伸展树的查找会引起树的结构调整，故重写
	BinNodePosi(T) & search( const T & e);//查找重写
	BinNodePosi(T) insert( const T & e); //插入重写
	bool remove( const T & e); //删除重写
}
1
2
3
4
5
6
7

实现：伸展算法

template typename<T> BinNodePosi(T) Splay(T)::splay( BinNodePosi(T) v){
	if(!v) return NULL; BinNodePosi(T) p; BinNodePosi(T) g; //父亲、祖父
	while( (p=v->parent)&&(g=p->parent)){//自下而上，反复双层伸展
		BinNodePosi(T) gg = g->parent;//每轮过后，v都将以原曾祖父为父
		if (IsLChild(*v))
			if(IsLChild(*p)){
				/*zig-zig*/
				attachAsLChild(g,p->rc);
				attachAsLChild(p,v->rc);
				attachAsRChild(p,g);
				attachAsRChild(v,p);
			} 
			else{/*zig-zag*/}
		else if(IsRChild(*p)){/*zag-zag*/}
			else{/*zag-zig*/}
		if(!gg) v->parent = NULL; //若无曾祖父，v现即为树根；否则，gg应以v为左或右孩子
		else (g==gg->lc)?attachAsLChild(gg,v):attachAsRChild(gg,v);
		updateHeight(g);updateHeight(p);updateHeight(v); 
	}//双层伸展结束时，必有g=NULL,但p可能非空
	if (p=v->parent){/*若p是真根，只需额外单旋至多一次*/}
	v->parent = NULL; return v; //伸展完成，v抵达树根
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

实现：查找算法

template <typename T> BinNodePosi(T) & Splay<T>::search( const T & e){
	//调用标准BST的内部接口定位目标节点
	BinNodePosi(T) p = searchIn(_root,e,_hot=NULL);
	//无论成功与否，最后被访问的节点伸展至根
	_root = splay(p?p:_hot);//成功、失败
	//总是返回根节点
	return _root; //局部性
}
1
2
3
4
5
6
7
8

伸展树的查找操作与常规BST::search()不同，很可能会改变树的拓扑结构，不再属于静态操作。
实现：插入算法
直观方法：调用BST标准的删除算法，再将_hot伸展至根，同样地，Splay::search()查找成功之后，目标节点即为树根，可直接在树根附近完成目标节点的摘除。（splay->release->splay->join）
综合评价：
（1）无需记录节点高度或平衡因子，编程简单易行（优于AVL树），分摊复杂度O(logn)（与AVL树相当）；
（2）局部性强，缓存命中率极高时（即k<<n<<m），效率甚至可以更高，自适应的O(logk)，任何连续的m次查找，都可以在O(mlogk + nlogn)时间内完成；
（3）仍不能保证单次最坏情况的出现，不适用于对效率敏感的场合；
（4）复杂度的分析稍微复杂，好在有初等的方法。

（b1）B-树：动机

内存越来越小，系统存储容量的增长速度远小于问题规模的增长速度。
高速缓存 - 事实1：不同容量的存储器，访问速度差异悬殊，多数存储系统都是分级组织的，最常用的数据尽可能放在更高层、更小的存储器中，实在找不到才向更低层、更大的存储器索取。
事实2：从磁盘中读写1B，与读写1KB一样快，批量式访问以页或块为单位，使用缓冲区。

#define BUFSIZ 512 //缓冲区默认容量
int setvbuf( //定制缓冲区
	FILE* fp,//流
	char* buf, //缓冲区
	int _Mode, //_IO F BF | _IO L BF | _IO N BF
	size_t size); //缓冲区容量
int fflush(FILE* fp);//强制清空缓冲区
1
2
3
4
5
6
7

（b2）B树：结构

平衡的多路搜索树，经适当合并，得到超级节点：每两代合并（4路）、每三代合并（8路）、每d代合并m=2^d路，m-1个关键码，逻辑上与BBST等价。
优点：多级存储系统中使用B-树，可针对外部查找，大大减少I/O次数（AVL树每次只读出一个关键码，得不偿失），B树可以充分利用外存对批量访问的高效支持，每下降一层，以超级节点为单位读入一组关键码。
m阶B树：m阶平衡搜索树（m≥2），外部节点的深度统一相等，所有叶节点的深度统一相等，树高h = 外部节点的深度。
内部节点各有不超过m-1个（n个）关键码，m个（n+1个）分支，内部节点分支数n+1也不能太小，具体树根：2 ≤ n + 1，其余[m/2] ≤ n + 1，故亦称作（[m/2], m）-树。
BTNode

template <typename T> struct BTNode{//B树节点
	BTNodePosi(T) parent; //父
	Vector<T> key; //数值向量
	Vector<BTNodePosi(T)> child;//孩子向量（长度比key多1）
	BTNode(){parent = NULL;child.insert(0,NULL);}
	BTNode(T e,BTNodePosi(T) lc = NULL,BTNodePosi(T) rc = NULL){
	parent = NULL; //作为根节点，初始时一个关键码，两个孩子
	key.insert(0,e);//仅一个关键码
	child.insert(0,lc);child.insert(1,rc);//两个孩子
	if (lc) lc->parent = this;
	if (rc) rc->parent = this;
	} 
}
1
2
3
4
5
6
7
8
9
10
11
12
13

BTree

#define BTNodePosi(T) BTNode<T>* //B-树节点位置
template <typename T> class BTree{//B树
protected:
	int _size; int _order; BTNodePosi(T) _root; //关键码总数、阶次、根
	BTNodePosi(T) _hot; //search()最后访问的非空节点位置
	void solveOverflow(BTNodePosi(T));//因插入而上溢后的分裂处理
	void solveUnderflow(BTNodePosi(T));//因删除而下溢后的合并处理
public:
	BTNodePosi(T) search(const T & e); //查找
	bool insert(const T & e);//插入
	bool remove(const T & e);//删除
};
1
2
3
4
5
6
7
8
9
10
11
12

（b3）B-树：查找

实现

template <typename T> BTNodePosi(T) BTree<T>
::search(const T & e){
	BTNodePosi(T) v = _root;_hot = NULL; //从根节点出发
	while (v) //逐层查找
		Rank r = v->key.search(e);//在当前节点对应向量中顺序查找
		if( 0<=r && e == v->key[r]) return v;//若成功则返回
		_hot = v; v=v->child[r+1];//沿引用转至对应的下层子树，并载入其根I/O
}//若因!v退出，意味着抵达外部节点
return NULL; //失败
}
1
2
3
4
5
6
7
8
9
10

最大树高
含N个关键码的m阶B树，最大高度=？为此，内部节点应尽可能“瘦”，各层节点数依次为n0=1，n1=2，n2=2×[m/2]…nk=2×[m/2]^(k-1)
考察外部节点所在层 N+1 = nh ≥2×(m/2)^(h-1)，h≤1+log[m/2][(N+1)/2]=O(log(m)(N))
N个内部节点，N+1个外部节点
N种成功可能，N+1种失败可能
相对于BBST，对m=256，树高（I/O次数）约降低至1/7。
最小树高
含N个关键码的m阶B树，最小高度=？为此，内部节点应尽可能“胖”，各层节点数一次为n0=1, n1=m, n2=m ^ 2， n3= m ^ 3，nh=m^h
考察外部节点所在层 N+1=nh≤m^h，h≥log(m)(N+1)=Ω(log(m)N)
相对于BBST，对m=256，树高（I/O次数）约降至1/8。

（b4）B树：插入

算法

template <typename T> bool BTree<T>::insert(const T & e){
	BTNodePosi(T) v=search(e);
	if (v) return false; //确认e不存在
	Rank r = _hot->key.search(e);//在节点_hot中插入相应的位置
	_hot->key.insert(r+1,e);//将新关键码插至对应的位置
	_hot->child.insert(r+2,NULL); //创建一个空子树指针
	_size++; solveOverflow(_hot);//如发生上溢，需分裂
	return true; //插入成功
}
1
2
3
4
5
6
7
8
9

中位数：中值，在向量中为秩居中的元素。
分裂：设上溢节点中的关键码依次为k0,…,km-1，取中位数s=[m/2]，以关键码ks为界划分为k0,…ks-1，ks，ks+1,…,km-1，关键码ks上升一层，并分裂（split），以所得的两个节点作为左、右孩子。
再分裂：若上溢节点的父亲本已饱和，在接纳被提升的关键码后也将上溢，可能持续发生，并逐层向上传播。0(1)×h=O(h)

（b5）B树：删除

算法

template <typename T> bool BTree<T>::remove(const T & e){
	BTNodePosi(T) v=search(e);
	if (!v) return false; //确认e存在
	Rank r = v->key.search(e);//确定e在v中的秩
	if (v->child[0]){//若v非叶子，则
		BTNodePosi(T) u=v->child[r+1];//在右子树中一直向左，即可
		while (u->child[0]) u=u->child[0];//找到e的后继（必属于某叶节点）
		v->key[r]=u->key[0];v=u;r=0;//与之交换位置
	}//v必然位于最底层，第r个关键码就是待删除者
	v->key.remove(r);v->child.remove(r+1);_size--;
	solveUnderflow(v);return true; //如有必要，须做旋转或合并
}
1
2
3
4
5
6
7
8
9
10
11
12

插入导致上溢，需分裂；删除导致下溢，需合并。
旋转：节点v下溢时，必恰好包含[m/2]-2个关键码+[m/2]-1个分支。如右分支包含[m/2]-2个关键码，左分支包含关键码≥[m/2]个，经一次旋转合并。
合并：L和R或者不存在，或者所含关键码均不足[m/2]个，注意，L和R仍必有其一，且恰含[m/2]-1个关键码。O(h)

（xa1）红黑树：动机

一致性结构：支持对历史版本的访问。
蛮力实现：每个版本独立保存，各版本入口自成一个搜索结构，单次操作O(logh+logn)，累计O(h+n) 时间/空间。
挑战：能否将复杂度控制在 O(n+h*logn) 内？可以，需利用相邻版本之间的关联性。
O(1)重构：大量共享，少量更新，每个版本的新增复杂度仅为O(logn)。
进一步提高：比如总体O(n+h)，单版本O(1)？可以，任何一次动态操作引发的结构变化量不致超过O(1)，为此就树形结构的拓扑而言，相邻版本之间的差异不能超过O(1)。

（xa2）红黑树：结构

由红、黑两类节点组成的BST，统一增设外部节点NULL，使之成为真二叉树。（1）树根：必为黑色；（2）外部节点：均为黑色；（3）其余节点：若为红，则只能有黑孩子（红之子、之父必黑）；（4）外部节点到根：途中黑节点数目相等（黑深度）。
（2-4）树：红黑树：提升各红节点，使之与其（黑）父亲等高，于是每颗红黑树，都对应于一棵（2,4）树，将黑节点与其哄孩子视作超级节点，无非四种组合（黑黑、黑红、红黑、红红），分别对应于4阶B树的一类内部节点。
RedBlack

template <typename T> class RedBlack::public BST<T>{//红黑树
public: //BST::search()等其余接口可直接沿用
	BinNodePosi(T) insert(const T & e);//插入（重写）
	bool remove(const T & e);//删除（重写）
protected: 
	void solveDoubleRed(BinNodePosi(T) x);//双红修正
	void solveDoubleBlack(BinNodePosi(T) x);//双黑修正
	int updateHeight(BinNodePosi(T) x);//更新节点x的高度
};

template <typename T> int RedBlack<T>::updateHeight(BinNodePosi(T) x){
	x->height = max(stature(x->lc),stature(x->rc));
	if (IsBlack(x)) x->height++; return x->height; //只需计黑节点
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

（xa3）红黑树：插入

现拟插入关键码e，按BST的常规算法，插入之，设x的父亲p=x->parent存在，将x染红（除非它是根），此时可能出现双红。考查：x的祖父 g = p->parent，p的兄弟（x的叔父） u = p==g->lc ? g->rc : g->lc，按u的颜色，分两种情况处理。
实现

template <typename T> BinNodePosi(T) RedBlack<T>::insert(const T & e){
//确认目标节点不存在（留意对_hot的设置）
	BinNodePosi(T) & x = search(e);if (x) return x;
//创建红节点，以_hot为父，黑高度-1
	x = new BinNode<T>(e,_hot,NULL,NULL,-1);_size++;
//如有必要，做双红修正
	solveDoubleRed(x);
//返回插入的节点
	return x ? x:_hot->parent;
}//无论原树中是否存有e，返回时总有x->data == e
1
2
3
4
5
6
7
8
9
10

RR-1：u->color == B
此时x、p、g的四个孩子全为黑，且黑高度相同。
（1）参照AVL树算法，做局部3+4重构，将节点X、p、g及其四棵子树按中序组合为Ta<a<T1<b<T2<c<T3。
（2）染色：b转黑，a或c转红。
Q：从B-树角度，如何理解这一情况？
（1）调整前之所以非法，是因为在某个三叉节点中插入红关键码，使得原黑关键码不再居中；
（2）调整之后效果相当于在新的四叉节点中，三个关键码的颜色改为RBR。
RR-2：u->color==R
在B树中，等效于超级节点发生上溢。
p与u转黑，g转红，在B树中等效于节点分裂，关键码g上升一层。
双红修正：复杂度
重构、染色均属常数时间的局部操作，故只需统计其总次数，红黑树的每一次插入操作都可在O(logn)时间内完成，其中至多做O(logn)次节点染色，一次“3+4”重构。

（xa4）红黑树：删除

首先按照BST常规算法，执行 r = removeAt( x, _hot )，x由孩子r接替，若二者之一为红，删除遂告完成；若x与r均黑，摘除x并代之以r后全树黑深度不再统一，原B-树种x所属节点下溢，在新树中，考察r的父亲 p = r->parent，r的兄弟 s = r == p->lc ? p->rc : p->lc

三种情况
BB-1：s为黑，且至少有一个红孩子t
BB-2R：s为黑，且两个孩子均为黑，p为红
BB-2B：s为黑，且两个孩子均为黑，p为黑
BB-3：s为红（其孩子均为黑）

复杂度
红黑树的每一次删除操作都可在O(logn)时间内完成，其中至多做O(logn)次重染色，一次“3+4”重构，一次单旋。