0

我们被要求在 Java 中实现一棵红黑树，但我不确定这是如何完成的。如果有人能评论我的节点类以实现 r/b 树，那就太好了。开始了：

public class RBTnode {

public RBTnode(int key, RBTnode left, RBTnode right) {
    /* this is the constructor for a root node */
    color = 0;
    parent = null;
    key = this.key;
    left = this.left;
    right = this.right;
}

public RBTnode(int key, RBTnode left, RBTnode right, RBTnode parent, int color ) {
    key = this.key;
    color = this.color;
    left = this.left;
    right = this.right;
    parent = this.parent;

}

int color; // 0 black, 1 red
int key;
RBTnode parent;
RBTnode left;
RBTnode right;

}

4

1 回答 1

1

我自己还没有写过 RB 树，但我现在正在学习它们。据我所知，您似乎需要进行一些调整。

为了使 RB 树成为 RB 树，您需要遵循某些规则：

  • 每个节点都是红色或黑色
  • 根节点始终为黑色
  • 新节点始终为红色
  • RED 节点的两个孩子都是黑色的。
  • 从根到叶子或到空子节点的每条路径都必须包含相同数量的黑色节点。

话虽如此，我认为您不需要第二个构造函数，因为无论如何，您总是要将新节点初始化为 RED。

于 2012-04-17T18:35:27.860 回答