0

我正在学习如何在 Java 中实现红黑树，我查阅了 Sanfoundry 的源代码：https ://www.sanfoundry.com/java-program-implement-red-black-tree/ 但我不能了解插入节点的功能代码在这里：

public void insert(int item) {

        current = parent = grand = header;

        nullNode.element = item;

        while (current.element != item) {

            great = grand;

            grand = parent;

            parent = current;

            current = item < current.element ? current.left : current.right;

            // Check if two red children and fix if so            
            if (current.left.color == RED && current.right.color == RED) {
                handleReorient(item);
            }

        }

        // Insertion fails if already present
        if (current != nullNode) {
            return;
        }

        current = new RedBlackNode(item, nullNode, nullNode);

        // Attach to parent
        if (item < parent.element) {
            parent.left = current;
        } else {
            parent.right = current;
        }

        handleReorient(item);

    }

    private void handleReorient(int item) {

        // Do the color flip
        current.color = RED;

        current.left.color = BLACK;

        current.right.color = BLACK;

        if (parent.color == RED) {

            // Have to rotate
            grand.color = RED;

            if (item < grand.element != item < parent.element) {
                parent = rotate(item, grand);  // Start dbl rotate
            }
            current = rotate(item, great);

            current.color = BLACK;

        }

        // Make root black
        header.right.color = BLACK;

    }

    private RedBlackNode rotate(int item, RedBlackNode parent) {

        if (item < parent.element) {
            return parent.left = item < parent.left.element ? rotateWithLeftChild(parent.left) : rotateWithRightChild(parent.left);
        } else {
            return parent.right = item < parent.right.element ? rotateWithLeftChild(parent.right) : rotateWithRightChild(parent.right);
        }

    }

    /* Rotate binary tree node with left child */
    private RedBlackNode rotateWithLeftChild(RedBlackNode k2) {

        RedBlackNode k1 = k2.left;

        k2.left = k1.right;

        k1.right = k2;

        return k1;

    }

    /* Rotate binary tree node with right child */
    private RedBlackNode rotateWithRightChild(RedBlackNode k1) {

        RedBlackNode k2 = k1.right;

        k1.right = k2.left;

        k2.left = k1;

        return k2;

    }

谁能向我解释为什么当一个黑色节点同时有 2 个红色子节点和 handleReorient 函数的含义时我们需要修复颜色，tks all ！

4

1 回答 1

0

通常来说

  1. 您找到要插入的节点的叶子位置
  2. 您插入节点并将其着色为红色
  3. 如果这个节点有一个父节点并且它是红色的，那么这违反了红黑规则，你会沿着根节点的方向遍历树，修复这些违规，直到树被纠正。

But I have seen insertion code, particularly with Sedgewick's Left-Leaning Red-Black trees where by the Red-Black tree is "prepared" for insertion on the way down. See here Left-Leaning Red-Black Trees and look at page 20 and 21. You will find that for 2-3-4 trees, nodes with 4 elements are split on the way down. A 4-node is equivalent in Red-Black trees to a black node with 2 red children.

handleReorient() is equivalent to the code that does the splitting (which amounts to recolouration).

于 2021-11-05T19:33:22.237 回答