Необычная реализация Java вставки узлов красного / черного дерева
Я пишу программу для класса на Java относительно красных / черных деревьев. Я хорошо понимаю, как они обычно работают, и я должен использовать рекурсивный метод вставки. То, что я обычно использовал бы ниже, соответствует классу узла моего профессора. Что касается цвета, 0 черный, 1 красный. Данный класс Node вообще не работает с ключами.
private static void put(int val, int col)
{ root = put(root, val, col); }
private static Node put(Node n, Integer val, int col)
{
if (n == null){
Node t=new Node(val);
t.setColor(1);
return t;
}
int cmp = val.compareTo(n.getValue());
if (cmp < 0) n.setLeft(put(n.getLeft(), val, col));
else if (cmp > 0) n.setRight(put(n.getRight(), val, col));
else n.setColor(col);
if (isRed(n.getRight()) && !isRed(n.getLeft())) n = rotateLeft(n);
if (isRed(n.getLeft()) && isRed(n.getLeft().getLeft())) n = rotateRight(n);
if (isRed(n.getLeft()) && isRed(n.getRight())) flipColors(n);
return n;
}
Однако подвох заключается в том, что мы должны возвращать логическое значение - если пользователь вставляет дублирующее значение, которое уже есть в дереве, мы возвращаем false и не присоединяем узел. В противном случае мы присоединяем их и возвращаем true; приведенный ниже код для этого приведен ниже, но не является рекурсивным (часть требований проекта). И хотя я не реализовал способ балансировки или вращения должным образом, возвращенная логическая часть работает.
public boolean insertNode(Node node) {
//Here is just an example of setting colors for a node. So far, it is in green color. But you need to modify the code to dynamically adjust the color to
//either RED or BLACK according to the red-black logic
Node current_node;
// if the root exists
if (root == null) {
root = node; // let the root point to the current node
root.setColor(Node.BLACK);
return true;
} else {
current_node = root;
node.setColor(1);
while (current_node != null) {
int value = current_node.getValue();
if (node.getValue() < value){ // go to the left sub-tree
if (current_node.getLeft() != null) // if the left node is not empty
current_node = current_node.getLeft();
else{ // put node as the left child of current_node
current_node.setLeft(node);
node.setParent(current_node);
current_node = null; }
//System.out.println("Left:"+current_node);
}
else if (node.getValue() > value){ // go to the right
if (current_node.getRight() != null) // if the right node is not empty
current_node = current_node.getRight();
else{ // put node as the right child of current_node
current_node.setRight(node);
node.setParent(current_node);
current_node = null; }
//System.out.println("Right: "+current_node);
}
else{
//System.out.println("Else: "+current_node);
return false; }
//if(current_node!=null&¤t_node.getLeft()!=null&¤t_node.getRight()!=null&¤t_node.getLeft().isRed()&¤t_node.getRight().isRed())
// flipColors(node);
}
}
if(node.getParent()!=null){
node=node.getParent();
System.out.println("Case: node has parent, val="+node.getValue());
}
if(node.getLeft()!=null&&node.getRight()!=null){
if((node.getRight().isRed())&&!node.getLeft().isRed())
node=rotateLeft(node);
if((node.getLeft().isRed())&&(node.getParent()!=null)&&(node.getParent().getLeft().getLeft()!=null)&&(node.getParent().getLeft().getLeft().isRed()))
node=rotateRight(node);
if((node.getLeft().isRed()) && (node.getRight().isRed()))
flipColors(node);
}
return true;
}
Я не смог найти в сети сравнимых реализаций, и похоже, что логическое значение необходимо для правильной работы графического интерфейса программы. Если у кого-то есть хорошее предложение, с чего начать, я был бы признателен за это!
2 ответа
Для рекурсивного insertNode я бы предложил вам следующее: Создать функцию insertNode(Node node, Node current_node) который возвращает boolean значение. Идея состоит в том, чтобы всегда вызывать функцию insertNode для исследуемого в данный момент узла, начиная с корневого узла. Если узел не может быть немедленно добавлен в current_node, ответственный узел вызывается рекурсивно для обработки узла. Я предоставил вам краткий пример, основанный на вашем коде (с некоторыми комментариями относительно основной идеи, очевидно, чего-то не хватает). Надеюсь, я правильно понял ваш вопрос, и это поможет вам понять.
public boolean insertNode(Node node) {
if (root == null) {
root = node;
root.setColor(Node.BLACK);
return true;
} else {
boolean result = insertNode(node, root);
if (result) {
//Some other important stuff to do...
}
return result;
}
}
public boolean insertNode(Node node, Node current_node) {
int value = current_node.getValue();
if (node.getValue() < value) {
if (current_node.getLeft() != null) {
// Investigate left
return insertNode(node, current_node.getLeft());
} else {
// Insert node left
return true;
}
} else if (node.getValue() > value) {
if (current_node.getRight() != null) {
// Investigate right
return insertNode(node, current_node.getRight());
} else {
// Insert node right
return true;
}
} else {
return false;
}
}
Теперь у меня есть рабочие функции, как показано ниже:
public boolean insertNode(Node node) {
if(root==null){
root=node;
root.setColor(Node.BLACK);
return true;
}
else
node.setColor(Node.RED);
return insertNode(node, root);
}
public boolean insertNode(Node node, Node cur){
if(node.getValue()<cur.getValue()){
if(cur.getLeft()!=null)
return insertNode(node, cur.getLeft());
else{
cur.setLeft(node);
node.setParent(cur);
handleInsertion(node);
return true; } }
else if(node.getValue()>cur.getValue()){
if(cur.getRight()!=null)
return insertNode(node, cur.getRight());
else{
cur.setRight(node);
node.setParent(cur);
handleInsertion(node);
return true; } }
else
return false;
}