java 将 2-3-4 树转换为红黑树
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/35955246/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Converting a 2-3-4 tree into a red black tree
提问by user3745602
I'm trying to convert a 2-3-4 Tree into a Red-Black tree in java, but am having trouble figuring it out.
我正在尝试在 Java 中将 2-3-4 树转换为红黑树，但无法弄清楚。
I've written these two basic classes as follows, to make the problem straightforward, but can't figure out where to go from here.
我将这两个基本类编写如下，以使问题简单明了，但无法弄清楚从哪里开始。
public class TwoThreeFour<K> {
public List<K> keys;
public List<TwoThreeFour<K>> children;
}
public class RedBlack<K> {
public K key;
public boolean isBlack;
public RedBlack<K> left,right;
public RedBlack<K key, boolean isBlack, RedBlack<K> left, RedBlack<K> right){
this.key = key; this.isBlack = isBlack; this.left = left; this.right = right;
}
}
I'm assuming the 2-3-4 tree is valid, and want to return a red black tree when the method is called.
我假设 2-3-4 树是有效的，并且希望在调用该方法时返回一棵红黑树。
I've also tried the following code with no luck:
我也尝试了以下代码但没有运气：
public convert(TwoThreeFour<K> tTF){
if (ttf.keys.size() == 3)
RedBlack<K> node = RedBlack<ttf.keys[1], true, RedBlack<ttf.keys[0], false, /* not sure what to put here for left */, /* not sure what to put here for right */), RedBlack<ttf.keys[2], false, /* not sure what to put here for left */, /* not sure what to put here for right */)
etc. for keys.size() == 2, 1....
等对于 keys.size() == 2, 1 ....
I know it has to be recursive in theory, but am having a hard time figuring it out. Any thoughts?
我知道理论上它必须是递归的，但是我很难弄清楚。有什么想法吗？
回答by Yogesh Umesh Vaity
Consider these three rules:
考虑这三个规则：
- Transform any 2-nodein the 2-3-4 tree into a black node in the
red-black tree.
- Transform any 3-nodeinto a child node and a parent node. The
child node has two children of its own: either W and X or X and Y.
The parent has one other child: either Y or W. It doesn't matter
which item becomes the child and which the parent. The child is
colored red and the parent is colored black.
- Transform any 4-nodeinto a parent and two children, the first
child has its own children W and X; the second child has children Y
and Z. As before, the children are colored red and the parent is
black.
- 将 2-3-4 树中的任意2-节点转化为红黑树中的黑色节点。
- 将任何3 节点转换为子节点和父节点。子节点有自己的两个子节点：W 和 X 或 X 和 Y。父节点有另一个子节点：Y 或 W。哪个项成为子项和哪个项成为父项并不重要。孩子是红色的，父母是黑色的。
- 将任意4个节点转化为一个父节点和两个子节点，第一个子节点有自己的子节点W和X；第二个孩子有孩子 Y 和 Z。和以前一样，孩子是红色的，父母是黑色的。
The red-black rules are automatically satisfied if you follow these rules. Here's the resulting example tree after applying the transformations.
如果您遵循这些规则，就会自动满足红黑规则。这是应用转换后的结果示例树。
Hopefully that should get you going. For easy to understand and detailed explanation, you can refer to Robert Lafore's Data Structures book.
希望这能让你继续前进。为了易于理解和详细解释，您可以参考 Robert Lafore 的 Data Structures 一书。
