java - RedBlackTree Mark Allen Weis 移除（x）顶部底部方法

Question

来自Data Structures and Problem Solving Using Java的原始 Mark Allen Weis RedBlackTree 实现在这里找到。

我似乎无法理解从树中删除节点的问题。在阅读了维基百科资源后，我注意到“is_leaf()”函数。这个和 Mark Weis 实现的问题是没有办法分辨哪个节点是叶子，哪个不是叶子

void delete_one_child(struct node *n)
{
    /*
     * Precondition: n has at most one non-null child.
     */
    struct node *child = is_leaf(n->right) ? n->left : n->right;

    replace_node(n, child);
    if (n->color == BLACK) {
            if (child->color == RED)
                    child->color = BLACK;
            else
                    delete_case1(child);
    }
    free(n);
}

Is_Leaf java实现

public boolean isLeaf(){
if(left == null && right == null){
return false;
}
return true;
}

控制台输出

value=1 color=1 leaf=true left=null right=14
value=2 color=1 leaf=true left=null right=5
value=5 color=0 leaf=true left=null right=null
value=7 color=0 leaf=true left=2 right=11
value=8 color=0 leaf=true left=null right=null
value=11 color=1 leaf=true left=8 right=null
value=14 color=1 leaf=true left=7 right=15
value=15 color=1 leaf=true left=null right=null

树格式（来自控制台）

└── (1) 1
    └── (1) 14
        ├── (0) 7
        │   ├── (1) 2
        │   │   └── (0) 5
        │   └── (1) 11
        │       └── (0) 8
        └── (1) 15

规则：

1. 根是黑色的
2. 每个红色节点都有一个黑色父节点
3. 红色节点的任何子节点都是黑色的 - 红色节点不能有红色子节点
4. 从根到叶的每条路径都包含相同数量的黑色节点

所以我的问题是如何实现从这个红树和背树的实现中删除？

Answer 1

我认为这是正确的 isLeaf() 代码：

public boolean isLeaf(RedBlackNode<AnyType> t ){
    if(t.left.element == null && t.right.element == null){
        return true;
    }
    return false;
}

Answer 2

您是在问如何实现 isLeaf() 吗？如果是这样，您应该传递 isLeaf 您要检查的节点。

public boolean isLeaf(RedBlackNode<AnyType> t ){
if(t.left == null && t.right == null){
return false;
}
return true;
}

否则，算法本身看起来是正确的，唯一真正的工作是将 C 翻译成 Java，这很容易。

Answer 3

您必须检查nullnode而不是null：

public boolean isLeaf() {
    if(left == nullnode && right == nullnode) {
        return false;
    }
    return true;
}