🌰Senjl's Digital Garden🐉

Important-and-hard-problems⭐

8分钟阅读

红黑树

高度与深度问题

  • 黑深度
    • 除去（子）树根节点本身，沿途所经黑节点的总数（包括外部节点）
    • 根节点黑深度为 0
  • 黑高度
    • 除去外部节点，沿途所经黑节点的总数
    • 外部节点黑高度为 0
    • 根的黑高度称为全（子）树的黑高度，在数值上与外部节点的黑深度相等
  1. 给出 n 个关键码的红黑树的黑高度的关系式。

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

从这个意义上考虑，

  • 红黑树最大黑高度就是在 (2,4)-树中，每个节点只有 1 个关键码（即那个黑节点），此时黑高度为
  • 红黑树的最小黑高度就是在 (2,4)-树中，每个节点有 3 个关键码（1 黑，2 红），此时黑高度为
  1. 给出全树的高度关系式。
  • 红黑树最小高度就是完全平衡的完全二叉树，此时高度自然就是
  • 红黑树的最大高度比较复杂，直接记结论： 至于证明方法，需要对树高 h 分偶数、奇数情况考虑，分别对应 max 中的第一个参数和第二个参数。更进一步地，最大高度也要求大多数节点都只有一个黑色节点（做关键码），只有代表最大树高的那一条链才有 2 个关键码（1 黑 1 红）。示意图如下：
  1. 判断：红黑树上所有节点，其黑深度与黑高度之和相同。

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

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

以上图为例，

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

旋转与染色次数问题

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

❌ 注意，

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

节点数规模问题

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

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

  • 左子树的高度为 h-1，因此其包含的关键码数为: ；
  • 右子树的高度同样为 h-1，因此其包含的关键码数为 ，则有如下关系式：，即 ；
  • 而总关键码数有关系式 ，解得树高与关键码数的关系式为 ，因此代入 和 的关系式中，可解得 ， （这里看起来和前式矛盾，是因为有一步做了不恰当的截断——h 的计算是损失了部分精度的，但是无关大雅，这里也恰恰能够表明，右子树的关键码总数占据了全树的绝大部分），此时最小左偏率为
  1. 红黑树的一条路径上有 5 个红节点，则该红黑树最少有多少个节点？

这个其实本质上与计算红黑树的最大高度那一题的思路是一致的： 单条路径上有 5 个红节点，为了保证最少节点的要求，则红节点应当是间隔分布的，则全树的树高为 2*5=10 （外部节点的树高为 0），也即，一个红节点贡献两层树高，树高总是偶数的。这样一来直接套用公式的前半部分：，因此代入 ，即可求出 个节点。

搜索长度问题

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

✅ 本质还是树高问题。 其中，AVL 树高在最坏情况下的关系式是： ，代入 ，得 红黑树的树高在最坏情况树高与节点数的关系式是： ，代入 ，得

树的遍历

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

先序遍历

递归版

// 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)时间
  • 遗憾：
    • 这种用栈消除尾递归的方式难以推广到其它递归形式
指向原始笔记的链接

Circular transclusion detected: 1-Theory/1-Algorithm/02-DataStruct/dsa-cpp-deng/D-Tree+BST+BBST/50-Tree

Circular transclusion detected: 1-Theory/1-Algorithm/02-DataStruct/dsa-cpp-deng/D-Tree+BST+BBST/50-Tree

关系图谱