Important-and-hard-problems⭐

红黑树

高度与深度问题

• 黑深度
  • 除去（子）树根节点本身，沿途所经黑节点的总数（包括外部节点）
  • 根节点黑深度为 0
• 黑高度
  • 除去外部节点，沿途所经黑节点的总数
  • 外部节点黑高度为 0
  • 根的黑高度称为全（子）树的黑高度，在数值上与外部节点的黑深度相等

1. 给出 n 个关键码的红黑树的黑高度的关系式。

红黑树可以视作 (2,4)-树，其中每个黑节点都是 (2,4)-树的一个超级节点，单独的一个黑节点也能满足 (2,4)-树的节点内关键码的数量要求，因此红节点并不是必须的。

从这个意义上考虑，

• 红黑树最大黑高度就是在 (2,4)-树中，每个节点只有 1 个关键码（即那个黑节点），此时黑高度为 $\lfloor {\log }_2\frac{n+1}{2}\rfloor +1$
• 红黑树的最小黑高度就是在 (2,4)-树中，每个节点有 3 个关键码（1 黑，2 红），此时黑高度为 $\lceil {\log }_4(n+1)\rceil$

2. 给出全树的高度关系式。

• 红黑树最小高度就是完全平衡的完全二叉树，此时高度自然就是 $\lceil {\log }_{2}n\rceil$
• 红黑树的最大高度比较复杂，直接记结论：$h_{max}=max\left(2\cdot (\lfloor {\log }_2(n+2)\rfloor -1),2\cdot \lfloor {\log }_2\left(\frac{n+2}{3}\right)\rfloor +1\right)$ 至于证明方法，需要对树高 h 分偶数、奇数情况考虑，分别对应 max 中的第一个参数和第二个参数。更进一步地，最大高度也要求大多数节点都只有一个黑色节点（做关键码），只有代表最大树高的那一条链才有 2 个关键码（1 黑 1 红）。示意图如下：
  • 
  • 

3. 判断：红黑树上所有节点，其黑深度与黑高度之和相同。

❌ 显然，这里需要注意到红节点和黑节点的差异：

• 黑节点的黑高度取决于其通往外部节点的通路上有多少个黑节点，并且不将自身计入数量中，黑深度取决于其通往根的通路上有多少个黑节点，同样不将自身计入计数中，因此其黑深度与黑高度之和相当于根到外部节点的通路上黑节点的总数-1；
• 红节点的黑高度和黑深度定义与上述相同，但要注意，即使不将自身计入计数中，它自己作为红节点对通路上的黑节点数是没有贡献的，因此黑深度与黑高度之和相当于根到外部节点上黑节点的总数；

以上图为例，

• 节点 11 的黑高度为 1，黑深度为 1，和为 2，而根到外部节点的通路上黑节点总数是 3；
• 而节点 8 的黑高度是 2，黑深度是 1，和为 3，恰好等于根到外部节点通路上的黑节点总数。

旋转与染色次数问题

• 看到这里，背诵一遍 双红修正、双黑修正 的具体操作。

1. 判断：若红黑树的删除操作导致了 $\Omega (\log n)$ 次重染色操作，则必然有至少一次旋转。

❌ 注意，

• 需要旋转的操作只有 BB-1 和 BB-3，且 BB-3 旋转后必然到达 BB-2R 或 BB-1 的情况。
• 而 BB-2R 调整后全树黑高度复衡，但 BB-2B 有可能下溢至根，因此完全可以 $\Omega (\log n)$ 次重染色操作都集中在 BB-2B 这一情况，最后通过 BB-2R 复衡或本身就已复衡，此时完全不需要旋转。

节点数规模问题

1. 定义左倾率为以某个节点为根的（子）树中，根的左子树的关键码规模与右子树的关键码规模之比。当全树的关键码数为 $n$ ，且 $n\to +\infty$ 时，给出根节点只有 1个关键码的红黑树的最小左偏率的关系式。

考虑全树的高度为 h（统一外部节点的高度为 0，计算关键码时不考虑外部节点）：

• 左子树的高度为 h-1，因此其包含的关键码数为: $N_L=2^{h-1}-1$；
• 右子树的高度同样为 h-1，因此其包含的关键码数为 $N_R$ ，则有如下关系式：$\lceil {\log }_4(N_R+1)\rceil \le h-1$，即 $N_R=4^{h-1}-1$；
• 而总关键码数有关系式 $N_L+N_R+1=n$，解得树高与关键码数的关系式为 $h=\frac{{\log }_{2}n+1}{2}+1$，因此代入 $N_L$ 和 $N_R$ 的关系式中，可解得 $N_L=(n+1{)}^{\frac{1}{2}}-1$，$N_R=n$ （这里看起来和前式矛盾，是因为有一步做了不恰当的截断——h 的计算是损失了部分精度的，但是无关大雅，这里也恰恰能够表明，右子树的关键码总数占据了全树的绝大部分），此时最小左偏率为 $\underset{n\to \infty }{\lim }\frac{N_L}{N_R}=\underset{n\to \infty }{\lim }\frac{\sqrt{n+1}-1}{n}=0$

2. 红黑树的一条路径上有 5 个红节点，则该红黑树最少有多少个节点？

这个其实本质上与计算红黑树的最大高度那一题的思路是一致的： 单条路径上有 5 个红节点，为了保证最少节点的要求，则红节点应当是间隔分布的，则全树的树高为 2*5=10 （外部节点的树高为 0），也即，一个红节点贡献两层树高，树高总是偶数的。这样一来直接套用公式的前半部分：${\text{h}}_{max}=2\cdot (\lfloor {\log }_2(n+2)\rfloor -1)$，因此代入 ${\text{h}}_{max}=10$，即可求出 $n=2^6-2=62$ 个节点。

搜索长度问题

1. 判断：规模同为 2023 个节点的红黑树和 AVL 树，最坏情况下红黑树的搜索长度更长。

✅ 本质还是树高问题。 其中，AVL 树高在最坏情况下的关系式是：$fib(h+3)-1\le n$ ，代入 $n=2023$，得 $h=14$ 红黑树的树高在最坏情况树高与节点数的关系式是：$h_{max}=max(2\cdot (\lfloor {\log }_2(n+2)\rfloor -1),2\cdot \lfloor {\log }_2(\frac{n+2}{3})\rfloor +1)$ ，代入 $n=2023$，得 $h_{max}=max(18,19)=19$

树的遍历

先序、中序、后序的迭代实现

先序遍历

递归版

// recursive version
template <typename T, typename VST> 
void traverse( BinNodePosi<T> x, VST & visit ) {
	if ( ! x ) return;
		visit( x->data );
	traverse( x->lc, visit );
	traverse( x->rc, visit );
} //O(n)

• 制约：使用默认的 Call Stack，允许的递归深度有限
• 如何化尾递归为迭代？

先序遍历特点——藤缠树

• 沿着左侧藤，整个遍历过程可分解为：
  • 自上而下访问藤上节点，
  • 再逆转方向，自下而上遍历各右子树，各右子树的遍历彼此递归地、独立地自成子任务；

迭代版

template <typename T, typename VST>
void travPre_I2( BinNodePosi<T> x, VST & visit ) {
	Stack < BinNodePosi<T> > S; //辅助栈
	while ( true ) { //以右子树为单位，逐批访问节点
		visitAlongVine( x, visit, S ); //访问子树x的藤蔓，各右子树（根）入栈缓冲
		if ( S.empty() ) break; //栈空即退出
		x = S.pop(); //弹出下一右子树（根），作为下一批的起点
	} //#pop = #push = #visit = O(n) = 分摊O(1) ，总数不过O(n)
}
 
//从当前节点出发，沿左分支不断深入，直至没有左分支的节点；沿途节点遇到后立即访问
template <typename T, typename VST>
static void visitAlongVine
( BinNodePosi<T> x, VST & visit, Stack < BinNodePosi<T> > & S ) { //分摊O(1)
	while ( x ) { //反复地
		visit( x->data ); //访问当前节点
		S.push( x->rc ); //右孩子（右子树）入栈（将来逆序出栈）
		x = x->lc; //沿藤下行
	} //只有右孩子、NULL可能入栈——增加判断以剔除后者，是否值得？——不必
}

分析

• 正确性：
  • 无遗漏：
  • 根优先：任一子树中，只有根被访问后才会访问其他节点；
  • 先左后右：同一节点的左子树先于右子树被访问；
• 复杂度 O (n)
  • 每步迭代都有一个节点出栈并被访问；
  • 每个节点入/出栈一次且仅一次
  • 每步迭代只需要 O (1)时间
• 遗憾：
  • 这种用栈消除尾递归的方式难以推广到其它递归形式

指向原始笔记的链接

中序遍历

递归版

template <typename T, typename VST>
void traverse( BinNodePosi<T> x, VST & visit ) {
	if ( !x ) return;
	traverse( x->lc, visit );
	visit( x->data );
	traverse( x->rc, visit ); //tail
}

时间复杂度：$T(n)=T(a)+O(1)+T(n-a-1)=O(n)$

中序遍历迭代版的思路

• 右子树的递归遍历是尾递归，但左子树不是；因此不能直接套用先序遍历中使用栈直接消除尾递归的思路；
• 因此中序遍历的递归转迭代的解决思路是：找到第一个被访问的节点，将其祖先用栈保存，于是化问题为依次对若干棵右子树的遍历问题（依从最”左”节点向上的次）
• 于是问题关键在于，中序遍历任一二叉树 T 时，首先被访问的节点是哪个？如何找到它？

• 沿着左侧藤，遍历可自底向上分解为 d+1 步迭代：每访问藤上一个节点，再遍历其右子树
• 各右子树的遍历彼此独立，递归地自成子任务；

迭代版

template <typename T, typename V> 
void travIn_I1( BinNodePosi<T> x, V& visit ) {
	Stack < BinNodePosi<T> > S; //辅助栈
	while ( true ) { //反复地
		goAlongVine( x, S ); //从当前节点出发，逐批入栈
		if ( S.empty() ) break; //直至所有节点处理完毕
		x = S.pop(); //x的左子树或为空，或已遍历（等效于空），故可以
		visit( x->data ); //立即访问之
		x = x->rc; //再转向其右子树（可能为空，留意处理手法）
	}
}

template <typename T> //从当前节点出发，沿左分支不断深入，直至没有左分支
static void goAlongVine(BinNodePosi<T> x,Stack < BinNodePosi<T>> & S){
	while(x){ //当前节点入栈后随即向左侧分支深入，迭代直到无左孩子
		s.push(x);
		x=x->lc;
	}
}

分析

1. 每个节点出栈时，其左子树或不存在，或已完全遍历，而右子树尚未入栈；
2. 于是每当节点出栈，只需访问它，然后从其右孩子出发继续按先左后右子树的次序访问；
3. goAlongVine() 最多需要调用Ω(n)次，单次调用最多需要最多Ω(n)次 push 入栈。纵观整个遍历过程中所有对 goAlongVine() 的调用，实质的操作只有辅助栈的 push 和 pop：
   1. 每次调用 goAlongVine() 都恰有一次 pop，全程不超过 O (n)次
   2. goAlongVine() 过程中尽管 push 次数不定，但累计应于 pop 一个量级；

更多递归实现

//travIn_I2
template <typename T, typename VST> //元素类型、操作器
void travIn_I2( BinNodePosi<T> x, VST& visit ) { //二叉树中序遍历算法（迭代版#2）
   Stack<BinNodePosi<T>> S; //辅助栈
   while ( true )
      if ( x ) {
         S.push( x ); //根节点进栈
         x = x->lc; //深入遍历左子树
      } else if ( !S.empty() ) {
         x = S.pop(); //尚未访问的最低祖先节点退栈
         visit( x->data ); //访问该祖先节点
         x = x->rc; //遍历祖先的右子树
      } else
         break; //遍历完成
}

//travIn_I3
template <typename T, typename VST> //元素类型、操作器
void travIn_I3( BinNodePosi<T> x, VST& visit ) { //二叉树中序遍历算法（迭代版#3，无需辅助栈）
   bool backtrack = false; //前一步是否刚从左子树回溯――省去栈，仅O(1)辅助空间
   while ( true )
      if ( !backtrack && HasLChild( *x ) ) //若有左子树且不是刚刚回溯，则
         x = x->lc; //深入遍历左子树
      else { //否则――无左子树或刚刚回溯（相当于无左子树）
         visit( x->data ); //访问该节点
         if ( HasRChild( *x ) ) { //若其右子树非空，则
            x = x->rc; //深入右子树继续遍历
            backtrack = false; //并关闭回溯标志
         } else { //若右子树空，则
            if ( !( x = x->succ() ) ) break; //回溯（含抵达末节点时的退出返回）
            backtrack = true; //并设置回溯标志
         }
      }
}

//travIn_I4
template <typename T, typename VST> //元素类型、操作器
void travIn_I4( BinNodePosi<T> x, VST& visit ) { //二叉树中序遍历（迭代版#4，无需栈或标志位）
   while ( true )
      if ( HasLChild( *x ) ) //若有左子树，则
         x = x->lc; //深入遍历左子树
      else { //否则
         visit ( x->data ); //访问当前节点，并
         while ( !HasRChild( *x ) ) //不断地在无右分支处
            if ( ! ( x = x->succ() ) ) return; //回溯至直接后继（在没有后继的末节点处，直接退出）
            else visit ( x->data ); //访问新的当前节点
         x = x->rc; //（直至有右分支处）转向非空的右子树
      }
}

后继与前驱

• 直接后继：最靠左的右后代，或最低的左祖先（将节点包含于其左子树中的最低祖先）

template <typename T> BinNodePosi<T> BinNode<T>::succ() { //定位节点v的直接后继
   BinNodePosi<T> s = this; //记录后继的临时变量
   if ( rc ) { //若有右孩子，则直接后继必在右子树中，具体地就是
      s = rc; //右子树中
      while ( HasLChild( *s ) ) s = s->lc; //最靠左（最小）的节点
   } else { //否则，直接后继应是“将当前节点包含于其左子树中的最低祖先”，具体地就是
      while ( IsRChild( *s ) ) s = s->parent; //逆向地沿右向分支，不断朝左上方移动
      s = s->parent; //最后再朝右上方移动一步，即抵达直接后继（如果存在）
   }
   return s;
}// 两种情况下运行时间分别为当前节点的高度和深度，总和不超过O(h)

指向原始笔记的链接

后序遍历

应用

//子树删除
template <typename T> //删除二叉树中位置x处的节点及其后代，返回被删除节点的数值
Rank BinTree<T>::remove( BinNodePosi<T> x ) { // assert: x为二叉树中的合法位置
   FromParentTo( *x ) = NULL; //切断来自父节点的指针
   updateHeightAbove( x->parent ); //更新祖先高度
   Rank n = removeAt( x ); 
   _size -= n;
   return n; //删除子树x，更新规模，返回删除节点总数
}

template <typename T> //删除二叉树中位置x处的节点及其后代，返回被删除节点的数值
static Rank removeAt( BinNodePosi<T> x ) { // assert: x为二叉树中的合法位置
   if ( !x ) return 0; //递归基：空树
   Rank n = 1 + removeAt( x->lc ) + removeAt( x->rc ); //递归释放左、右子树
   release( x->data ); release( x ); return n; //释放被摘除节点，并返回删除节点总数
} // release()负责释放复杂结构，与算法无直接关系，具体实现详见代码包

事实上，之前提到的更新高度的函数 updateHeight 、更新节点的后代规模的函数 size 也是后序遍历。

递归版

template <typename T, typename VST>
void traverse( BinNodePosi<T> x, VST & visit ) {
	if ( ! x ) return;
	traverse( x->lc, visit );
	traverse( x->rc, visit );
	visit( x->data );
}

• 时间复杂度：$T(n)=T(a)+T(n-a-1)+O(1)=O(n)$

后序遍历特点

• 左右子树的递归遍历都不是尾递归，因此解决办法是找到第一个被访问的节点，将其祖先及右兄弟用栈保存；
• 于是后序遍历分解为依次对若干棵右子树遍历的问题，此处次序是沿左侧藤最底部左节点向上的次序。此时问题的关键是找到首先被访问的节点；
• 从根出发下行，尽可能沿左分支前进，实不得以再沿右分支，左右分支都不存在，才返回；
• 第一个找到的节点，是每个子树的叶子，并且是其中序遍历次序的最靠左者；

迭代版

template <typename T, typename V> 
void travPost_I( BinNodePosi<T> x, V & visit ) {
	Stack < BinNodePosi<T> > S; //辅助栈
	if ( x ) S.push( x ); //根节点首先入栈
	while ( ! S.empty() ) { //x始终为当前节点
		if ( S.top() != x->parent ) //若栈顶非x之父（而为右兄），则
			gotoLeftmostLeaf( S ); //在其右兄子树中找到最靠左的叶子
		x = S.pop(); //弹出栈顶（即前一节点之后继）以更新x
		visit( x->data ); //并随即访问之
	}
}

template <typename T> //在以S栈顶节点为根的子树中，找到最高左侧可见叶节点
static void gotoLeftmostLeaf( Stack <BinNodePosi<T>> & S ) { //沿途所遇节点依次入栈
	while ( BinNodePosi<T> x = S.top() ) //自顶而下反复检查栈顶节点
		if ( HasLChild( * x ) ) { //尽可能向左。在此之前
			if ( HasRChild( * x ) ) //若有右孩子，则
				S.push( x->rc ); //优先入栈
			S.push( x->lc ); //然后转向左孩子
		} else //实不得已
			S.push( x->rc ); //才转向右孩子
	S.pop(); //返回之前，弹出栈顶的空节点
}

实例

分析

• 正确性：
  • 每个节点出栈后，以其为根的子树已经完全遍历，并且如果其右兄弟存在，则必恰为栈顶；
  • 后续继续遍历子树r
• 效率：
  • 分摊分析与中序遍历类似，时间是 O (n)
  • 空间是 O (height)

应用：表达式树

• 运算符一定是分支节点，操作数一定是叶子节点；
• 上图先是对原运算式添加括号，隔离运算符的优先级；
• 之后将操作数摘出，作为运算树的叶节点，将每对括号与运算符匹配；
• 最后根据深度决定优先级，去除括号，得到的就是 RPN 式，即对表达式树的后序遍历就是正确的运算：

指向原始笔记的链接