ここにあるData Structures and Problem Solving Using Javaの元の Mark Allen Weis RedBlackTree 実装から。
ツリーからノードを削除することに頭を悩ませているようには見えません。ウィキペディアのリソースを読んだ後、「is_leaf()」関数に気付きました..これとマーク・ワイスの実装の問題は、どのノードがリーフで、どのノードがそうでないかを判断する方法がないことです
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
ルール:
- 根元が黒い
- すべての赤いノードには黒い親があります
- 赤のノードの子はすべて黒 – 赤のノードは赤の子を持つことはできません
- ルートからリーフへのすべてのパスには、同じ数の黒いノードが含まれます
私の質問は、このRed および Back Trees の実装からの削除をどのように実装するのですか?