我有一个链表/二叉树方法库，可以在标准容器不适合的情况下使用，例如，当存在不同类型的节点时，或者当我需要从二叉树转换到列表并再次转换时。它包括红黑树处理。
其中一个方法在O(n)时间内从双链表转换为完全平衡的简单二叉树（假设预先知道项目的数量）。这个算法被称为“折叠”——这是一个二叉树再平衡算法的后半部分，这个算法曾经发表在Dobbs博士的文章中。步骤基本上是…
给定树的大小，决定左子树和右子树的大小
为左子树递归
从列表中弹出一个节点用作根节点
为右子树递归
将子树链接到根
我还有一个创建红黑树的类似方法。原理是相同的，但是递归跟踪节点高度-高度0节点创建为红色，所有其他节点都为黑色。开始高度的计算是基于树大小中的最高设置位的，并且经过修改，使得完全平衡的(2^n)-1大小的树只有黑色节点（递归只降到高度1）。
这里的要点是，在叶级别上，我只有红色节点，并且正好有一半的节点是红色的。
问题是，虽然这是一种生成有效红黑树的简单方法，但并不是唯一的选择。在一棵完全平衡的树上避免所有的叶子都变成红色是一个任意的选择。我可以有红黑相间的节。或者在某些情况下，我可以通过发现完全平衡的子树（如果它需要红色节点）使子树的根变红而不是所有的叶子来显著减少红色节点的数量。
问题是-是否有任何实际的理由选择一个有效的红黑树形式而不是另一个？
这纯粹是好奇-我知道我没有任何实际的理由-但有谁知道一个专业的应用程序，这个选择是重要的？
最佳答案
在使用Pysicist方法修改红黑树的摊余成本的标准分析中，具有零个或两个红色子节点的黑色节点被赋予一个正电位，这意味着它们代表了树中可能需要做额外工作的有问题的地方。红色节点和只有一个红色子节点的黑色节点被赋予零的电位。
因此，为了降低修改的成本，给每个黑色节点一个红色的子节点。
有一个红色子节点的黑色节点被祝福的原因最好通过与冗余二进制数的类比来解释。我将首先解释如何将红黑树与二进制数关联起来，然后解释为什么一个红色子节点是有用的。
如您所知，红黑树是表示2-4棵树的一种方法，在这种方法中，从根到叶的每条简单路径都具有相同的长度，但节点有2、3或4个子节点。在2-4树中添加或移除节点的最简单算法与从冗余二进制数中添加或减去节点的算法相同。
冗余二进制数是第i个数字表示2i的数字，与标准二进制数相同，但第i个数字可以是0、1或2。它们之所以被称为冗余，是因为有多种方法可以写出给定的数字。4dec可以是100、20或12。
若要向冗余二进制数中添加一个，则增加最低有效位；如果是3，则将其设置为1并增加下一个最低有效位，依此类推。当遇到0或1时，算法停止。
若要将叶添加到2-4树，请将子级添加到其目标父级。如果父how有五个子节点，则将其拆分为两个节点，并使它们成为其父how的子节点。继续，直到到达不需要拆分的节点因此，当它遇到一个有两个或三个子节点的节点时，指向根的路径将停止。
要限制增加一个冗余二进制数的摊余成本，请使用物理学家的方法，并为每两个数字分配1的势。一个触及k位的xall-to增量释放了k-1潜力，使其摊余成本为o（1）。
这种分析类似于增加标准二进制数的摊余成本，但标准二进制数不能同时支持O（1）摊余时间的增量和减量：考虑2K-1。它是k 1数字。增量成本（k）。如果随后是递减，则该对的成本为_（k），并将数字恢复到原来的状态。
冗余二进制特别之处在于1位数字停止了递增和递减的级联操作。2-4树的特殊之处在于3个节点停止了insert和delete的级联操作。
在红黑树中，具有一个红色子节点的节点只是2-4树中3个节点的表示。这些节点是特殊的，并且对其子树中的插入或删除具有健壮性，因此在构建红黑树时，您应该支持它们，因为红黑树会看到很多更新。
如果您知道您将只看到插入，请支持有两个黑色子节点的节点。如果你知道你只会看到删除，支持有两个红色子节点的节点。