插入红黑树
Insert into Red Black Tree
我想递归地插入一个新节点,然后 return 从函数 insertRec
新插入的节点。函数调用看起来像这样
void insert(int value) {
root = insertRec(root, null, value);
root = insertRec(root, null, 15);
root = insertRec(root, null, 6);
root = insertRec(root, null, 5);
root = insertRec(root, null, 3);
root = insertRec(root, null, 4);
//insertFixup(newNode);
}
RedBlackNode insertRec(RedBlackNode current, RedBlackNode prev, int value)
{
if(current == null) {
current = new RedBlackNode(value);
current.p = prev;
}
else if(current.key < value) {
current.right = insertRec(current.right, current, value);
}
else {
current.left = insertRec(current.left, current, value);
}
return current;
}
如何在确保 insertRec
正常工作的同时做到这一点?现在,如果我不从 insertRec
return current
那么我就无法正确创建树。
在你的代码中你没有处理同样重要的节点颜色?
通常对于红黑树,您以线性方式而不是递归方式进行插入。类似于:
private void insert(int value) {
RedBlackNode parent = null;
RedBlackNode current = root;
while (current!=null){
parent = current;
if (value < current.key){
current = x.left;
//Here if you store the number of items on the left of a node increase it
}
else{
current = current.right;
//Here if you store the number of items on the right of a node increase it
}
}
RedblackNode newNode=new RedBlackNode(value);
newNode.p=parrent;
// Here if parent is null the new node is root of the tree
//if (parrent==null)
// root = newNode;
if (value < parent.key)
parent.left = newNode;
else
parent.right = newNode;
// Usually we add it as RED and then fix the tree to comply with red black tree rules
newNode.color=(RED);
fixTree(newNode);
}
这是一些伪代码,但就是这个意思。您迭代向下的树,直到达到 null。然后将新节点添加为红色,然后可能需要旋转树来修复颜色。
我想递归地插入一个新节点,然后 return 从函数 insertRec
新插入的节点。函数调用看起来像这样
void insert(int value) {
root = insertRec(root, null, value);
root = insertRec(root, null, 15);
root = insertRec(root, null, 6);
root = insertRec(root, null, 5);
root = insertRec(root, null, 3);
root = insertRec(root, null, 4);
//insertFixup(newNode);
}
RedBlackNode insertRec(RedBlackNode current, RedBlackNode prev, int value)
{
if(current == null) {
current = new RedBlackNode(value);
current.p = prev;
}
else if(current.key < value) {
current.right = insertRec(current.right, current, value);
}
else {
current.left = insertRec(current.left, current, value);
}
return current;
}
如何在确保 insertRec
正常工作的同时做到这一点?现在,如果我不从 insertRec
return current
那么我就无法正确创建树。
在你的代码中你没有处理同样重要的节点颜色?
通常对于红黑树,您以线性方式而不是递归方式进行插入。类似于:
private void insert(int value) {
RedBlackNode parent = null;
RedBlackNode current = root;
while (current!=null){
parent = current;
if (value < current.key){
current = x.left;
//Here if you store the number of items on the left of a node increase it
}
else{
current = current.right;
//Here if you store the number of items on the right of a node increase it
}
}
RedblackNode newNode=new RedBlackNode(value);
newNode.p=parrent;
// Here if parent is null the new node is root of the tree
//if (parrent==null)
// root = newNode;
if (value < parent.key)
parent.left = newNode;
else
parent.right = newNode;
// Usually we add it as RED and then fix the tree to comply with red black tree rules
newNode.color=(RED);
fixTree(newNode);
}
这是一些伪代码,但就是这个意思。您迭代向下的树,直到达到 null。然后将新节点添加为红色,然后可能需要旋转树来修复颜色。