1.4.3.4 RB Tree Delete Implementation

完整的原始碼點我

刪除的主要邏輯:

public boolean delete(int key) {
        // 1: Find the node you want to delete
        RbNode current = root;
        RbNode parent = root;

        // The substitution of the deleted node
        RbNode substitution = null;

        current = this.findOneNode(root, key);
        if (current == null) {
            return true;
        }
        parent = current.getParent();

        // 2: If the node has no child
        if ((current.getLeft() == null || isEmptyNode(current.getLeft()))
                && (current.getRight() == null || isEmptyNode(current.getRight()))) {
            hasNoChildren(parent, current, isLeft);
            if (!current.isRed()) {
                substitution = new RbNode(SUBSTITUTION_ID, SUBSTITUTION_DATA, false);
                substitution.setParent(current.getParent());

                if (parent != null) {
                    if (isLeft) {
                        parent.setLeft(substitution);
                    } else {
                        parent.setRight(substitution);
                    }
                }

            }
            current.setParent(null);
        }
        // 3: If the node has only one child
        // 3.1: Only has left child
        else if (current.getRight() == null || isEmptyNode(current.getRight())) {
            oneLeftChild(parent, current, isLeft);
            if (!current.isRed() && current.getLeft().isRed()) {
                current.getLeft().setRed(false);
            } else if (!current.isRed() && !current.getLeft().isRed()) {
                substitution = current.getLeft();
            }
        }
        // 3.2: Only has right child
        else if (current.getLeft() == null || isEmptyNode(current.getLeft())) {
            oneRightChild(parent, current, isLeft);
            if (!current.isRed() && current.getRight().isRed()) {
                current.getRight().setRed(false);
            } else {
                substitution = current.getRight();
            }
        }
        // 4: If the node has two child
        else {
            // 4.1: Find the in-order successor
            RbNode successor = getSuccessor(current);

            /*
             * 4.2: Swap the successor and current node without copying color and changing
             * relationship
             */
            RbNode tempNode = new RbNode(successor.getId(), successor.getData(), successor.isRed());
            successor.setId(current.getId());
            successor.setData(current.getData());

            current.setId(tempNode.getId());
            current.setData(tempNode.getData());

            // 4.3: Execute delete operation again
            delete(successor.getId());
        }

        // After the delete operation, execute balance operation
        if (substitution != null) {
            balanceAfterDelete(substitution);
        }

        return true;
    }

在刪除過程中搜尋節點:

private RbNode findOneNode(RbNode node, int key) {
        if (node != null) {
            if (node.getId() == key) {
                return node;
            }

            RbNode tempNode = findOneNode(node.getLeft(), key);
            if (tempNode != null) {
                if (tempNode == tempNode.getParent().getLeft()) {
                    isLeft = true;
                } else {
                    isLeft = false;
                }
                return tempNode;
            }

            tempNode = findOneNode(node.getRight(), key);
            if (tempNode != null) {
                if (tempNode == tempNode.getParent().getLeft()) {
                    isLeft = true;
                } else {
                    isLeft = false;
                }
                return tempNode;
            }
        }
        return null;
    }

刪除之後的平衡操作:

private void balanceAfterDelete(RbNode currentNode) {
        if (currentNode.isRed()) {
            currentNode.setRed(false);
        } else if (currentNode.getParent() == null) {
            currentNode.setRed(false);
        } else if (!currentNode.isRed()) {
            RbNode bNode = (currentNode == currentNode.getParent().getLeft()) ? 
            currentNode.getParent().getRight() : currentNode.getParent().getLeft();

            if (bNode.isRed() && currentNode == currentNode.getParent().getLeft()) {
                bNode.setRed(currentNode.getParent().isRed());
                currentNode.getParent().setRed(true);
                leftRotate(currentNode.getParent());
                balanceAfterDelete(currentNode);
            } else if (bNode.isRed() && currentNode == currentNode.getParent().getRight()) {
                bNode.setRed(currentNode.getParent().isRed());
                currentNode.getParent().setRed(true);
                rightRotate(currentNode.getParent());
                balanceAfterDelete(currentNode);
            } else if (bNode.isRed() && !currentNode.getParent().isRed() 
                    && (bNode.getLeft() == null || !bNode.getLeft().isRed())
                    && (bNode.getRight() == null || !bNode.getRight().isRed())) {
                bNode.setRed(true);
                currentNode = currentNode.getParent();
                balanceAfterDelete(currentNode);
            } else if (!bNode.isRed() && currentNode.getParent().isRed() 
                    && (bNode.getLeft() == null || !bNode.getLeft().isRed())
                    && (bNode.getRight() == null || !bNode.getRight().isRed())) {
                bNode.setRed(true);
                currentNode.getParent().setRed(false);
            } else if (!bNode.isRed() && (currentNode == currentNode.getParent().getLeft())
                    && (bNode.getLeft() != null && bNode.getLeft().isRed())
                    && (bNode.getRight() == null || !bNode.getRight().isRed())) {
                bNode.setRed(true);
                bNode.getLeft().setRed(false);
                rightRotate(bNode);
                balanceAfterDelete(currentNode);
            } else if (!bNode.isRed() && (currentNode == currentNode.getParent().getRight())
                    && (bNode.getRight() != null && bNode.getRight().isRed())
                    && (bNode.getLeft() == null || !bNode.getLeft().isRed())) {
                bNode.setRed(true);
                bNode.getRight().setRed(false);
                leftRotate(bNode);
                balanceAfterDelete(currentNode);
            } else if (!bNode.isRed() && (currentNode == currentNode.getParent().getLeft())
                    && (bNode.getRight() != null && bNode.getRight().isRed())) {
                bNode.setRed(currentNode.getParent().isRed());
                currentNode.getParent().setRed(false);
                bNode.getRight().setRed(false);
                leftRotate(currentNode.getParent());
            } else if (!bNode.isRed() && (currentNode == currentNode.getParent().getRight())
                    && (bNode.getLeft() != null && bNode.getLeft().isRed())) {
                bNode.setRed(currentNode.getParent().isRed());
                currentNode.getParent().setRed(false);
                bNode.getLeft().setRed(false);
                rightRotate(currentNode.getParent());
            }
        }
    }