数据结构基础：红黑树中的红色节点和黑色节点的特点、查询和插入数据的具体流程

梦里梦外; 2023-10-12 09:36 4阅读 0赞

## 红黑树中的红色节点和黑色节点具有以下特点： ##

1.  红色节点：
    
     *  红色节点可以是根节点、内部节点或叶子节点。
     *  红色节点的父节点必定是黑色节点。
     *  红色节点的两个子节点都是黑色节点。
2.  黑色节点：
    
     *  黑色节点可以是根节点、内部节点或叶子节点。
     *  黑色节点的子节点可以是红色节点或黑色节点。
     *  黑色节点的子节点可以是空节点（叶子节点）。

## 查询数据的具体流程： ##

*  从根节点开始，比较目标值与当前节点的键值。
 *  如果目标值小于当前节点的键值，则沿着左子树继续查找。
 *  如果目标值大于当前节点的键值，则沿着右子树继续查找。
 *  如果目标值等于当前节点的键值，则找到目标节点，查找完成。
 *  如果到达叶子节点仍未找到目标节点，则表示目标值不存在于树中。

## 插入数据的具体流程： ##

1.  将新节点插入到红黑树中的合适位置，作为一个红色节点。
2.  根据红黑树的性质，可能需要进行一些调整来保持红黑树的平衡和性质。
    
     *  如果插入的节点是根节点，将其颜色设置为黑色，满足性质1。
     *  如果插入的节点的父节点是黑色节点，不会违反红黑树的性质，不需要进行额外操作。
     *  如果插入的节点的父节点是红色节点，需要根据父节点和叔叔节点的颜色进行调整。
3.  进行必要的旋转和变色操作，以保持红黑树的平衡和性质。
    
     *  如果插入的节点的父节点和叔叔节点都是红色节点，将父节点和叔叔节点的颜色设为黑色，将祖父节点设为红色，再以祖父节点为基准进行后续调整。
     *  如果插入的节点的父节点是红色节点，但叔叔节点是黑色节点或为空节点，需要进行旋转和变色操作，以保持红黑树的平衡。
4.  检查红黑树的性质是否被保持，如果不满足，继续进行调整，直到红黑树恢复平衡。

总结起来，查询数据时根据键值的比较逐步向下遍历红黑树，直到找到目标节点或到达叶子节点。插入数据时将新节点插入到红黑树的合适位置，然后根据红黑树的性质进行调整和修复，以保持平衡性和性质的正确性。这些调整过程涉及到旋转和变色操作，以确保红黑树的性质得到满足。

## java红黑树实现 ##

下面是一个简单的 Java 实现红黑树的代码示例：

package com.zxl.day_20230603;
    
    enum Color {
        
        RED, BLACK
    }
    
    class Node {
        
        int data;
        Node parent;
        Node left;
        Node right;
        Color color;
    
        public Node(int data) {
        
            this.data = data;
            this.color = Color.RED;
        }
    }
    
    public class RedBlackTree {
        
        private Node root;
        private Node nil;
    
        public RedBlackTree() {
        
            nil = new Node(0);
            nil.color = Color.BLACK;
            root = nil;
        }
    
        public void insert(int data) {
        
            Node newNode = new Node(data);
            Node current = root;
            Node parent = nil;
    
            while (current != nil) {
        
                parent = current;
                if (data < current.data) {
        
                    current = current.left;
                } else {
        
                    current = current.right;
                }
            }
    
            newNode.parent = parent;
            if (parent == nil) {
        
                root = newNode;
            } else if (data < parent.data) {
        
                parent.left = newNode;
            } else {
        
                parent.right = newNode;
            }
    
            newNode.left = nil;
            newNode.right = nil;
            newNode.color = Color.RED;
            fixInsert(newNode);
        }
    
        private void fixInsert(Node node) {
        
            while (node.parent.color == Color.RED) {
        
                if (node.parent == node.parent.parent.left) {
        
                    Node uncle = node.parent.parent.right;
                    if (uncle.color == Color.RED) {
        
                        node.parent.color = Color.BLACK;
                        uncle.color = Color.BLACK;
                        node.parent.parent.color = Color.RED;
                        node = node.parent.parent;
                    } else {
        
                        if (node == node.parent.right) {
        
                            node = node.parent;
                            rotateLeft(node);
                        }
                        node.parent.color = Color.BLACK;
                        node.parent.parent.color = Color.RED;
                        rotateRight(node.parent.parent);
                    }
                } else {
        
                    Node uncle = node.parent.parent.left;
                    if (uncle.color == Color.RED) {
        
                        node.parent.color = Color.BLACK;
                        uncle.color = Color.BLACK;
                        node.parent.parent.color = Color.RED;
                        node = node.parent.parent;
                    } else {
        
                        if (node == node.parent.left) {
        
                            node = node.parent;
                            rotateRight(node);
                        }
                        node.parent.color = Color.BLACK;
                        node.parent.parent.color = Color.RED;
                        rotateLeft(node.parent.parent);
                    }
                }
            }
            root.color = Color.BLACK;
        }
    
        private void rotateLeft(Node node) {
        
            Node rightChild = node.right;
            node.right = rightChild.left;
            if (rightChild.left != nil) {
        
                rightChild.left.parent = node;
            }
            rightChild.parent = node.parent;
            if (node.parent == nil) {
        
                root = rightChild;
            } else if (node == node.parent.left) {
        
                node.parent.left = rightChild;
            } else {
        
                node.parent.right = rightChild;
            }
            rightChild.left = node;
            node.parent = rightChild;
        }
    
        private void rotateRight(Node node) {
        
            Node leftChild = node.left;
            node.left = leftChild.right;
            if (leftChild.right != nil) {
        
                leftChild.right.parent = node;
            }
            leftChild.parent = node.parent;
            if (node.parent == nil) {
        
                root = leftChild;
            } else if (node == node.parent.left) {
        
                node.parent.left = leftChild;
            } else {
        
                node.parent.right = leftChild;
            }
            leftChild.right = node;
            node.parent = leftChild;
        }
    
        public void printTree() {
        
            printTree(root);
        }
    
        private void printTree(Node node) {
        
            if (node != nil) {
        
                printTree(node.left);
                System.out.println(node.data + " " + node.color);
                printTree(node.right);
            }
        }
    
        public static void main(String[] args) {
        
            RedBlackTree tree = new RedBlackTree();
            tree.insert(7);
            tree.insert(3);
            tree.insert(18);
            tree.insert(10);
            tree.insert(22);
            tree.insert(8);
            tree.insert(11);
            tree.insert(26);
            tree.insert(2);
            tree.insert(6);
            tree.insert(13);
            tree.printTree();
        }
    }

这个示例实现了红黑树的基本功能，包括插入和打印树。`Node` 类表示红黑树的节点，具有数据、父节点、左子节点、右子节点和颜色属性。`RedBlackTree` 类实现了红黑树的插入操作和辅助方法。

在 `insert` 方法中，首先将新节点插入到红黑树中，并将其颜色设为红色。然后，根据红黑树的性质进行修复操作，包括左旋、右旋和颜色调整。

`rotateLeft` 和 `rotateRight` 方法分别实现了左旋和右旋操作。这些操作用于保持红黑树的平衡。

`fixInsert` 方法用于修复插入操作可能破坏的红黑树性质。它根据不同的情况进行颜色调整和旋转操作，直到满足红黑树的性质。

`printTree` 方法用于打印红黑树的节点及其颜色。它使用中序遍历算法打印节点的数据和颜色。

在 `main` 方法中，我们创建了一个红黑树实例并插入一些节点，然后打印整棵树。

请注意，这只是一个简单的红黑树实现示例，仅包含基本的插入操作和打印功能。实际上，红黑树还可以支持删除、查找等操作，并且有更复杂的性质和规则需要遵循。完整的红黑树实现通常会更加复杂。