利用Java实现红黑树

目录
  • 1、红黑树的属性
  • 2、旋转
  • 3、插入
  • 4、删除
  • 5、所有代码
  • 6、演示

1、红黑树的属性

红黑树是一种二分查找树,与普通的二分查找树不同的一点是,红黑树的每个节点都有一个颜色(color)属性。该属性的值要么是红色,要么是黑色。

通过限制从根到叶子的任何简单路径上的节点颜色,红黑树确保没有比任何其他路径长两倍的路径,从而使树近似平衡。

假设红黑树节点的属性有键(key)、颜色(color)、左子节点(left)、右子节点(right),父节点(parent)。

一棵红黑树必须满足下面有下面这些特性( 红黑树特性 ):

  • 树中的每个节点要么是红色,要么是黑色;
  • 根节点是黑色;
  • 每个叶子节点(null)是黑色;
  • 如果某节点是红色的,它的两个子节点都是黑色;
  • 对于每个节点到后面任一叶子节点(null)的所有路径,都有相同数量的黑色节点。

为了在红黑树代码中处理边界条件方便,我们用一个哨兵变量代替null。对于一个红黑树tree,哨兵变量RedBlackTree.NULL(下文代码中)是一个和其它节点有同样属性的节点,它的颜色(color)属性是黑色,其它属性可以任意取值。

我们使用哨兵变量是因为我们可以把一个节点node的子节点null当成一个普通节点。

在这里,我们使用哨兵变量RedBlackTree.NULL代替树中所有的null(所有的叶子节点及根节点的父节点)。

我们把从一个节点n(不包括)到任一叶子节点路径上的黑色节点的个数称为 黑色高度 ,用bh(n)表示。一棵红黑树的黑色高度是其根节点的黑色高度。

关于红黑树的搜索,求最小值,求最大值,求前驱,求后继这些操作的代码与二分查找树的这些操作的代码基本一致。可以在用java实现二分查找树查看。

结合上文给出下面的代码。

用一个枚举类Color表示颜色:

public enum Color {
    Black("黑色"), Red("红色");

    private String color;

    private Color(String color) {
        this.color = color;
    }

    @Override
    public String toString() {
        return color;
    }
}

类Node表示节点:

public class Node {
    public int key;
    public Color color;
    public Node left;
    public Node right;
    public Node parent;

    public Node() {
    }

    public Node(Color color) {
        this.color = color;
    }

    public Node(int key) {
        this.key = key;
        this.color = Color.Red;
    }

    public int height() {
        return Math.max(left != RedBlackTree.NULL ? left.height() : 0, right != RedBlackTree.NULL ? right.height() : 0) + 1;
    }

    public Node minimum() {
        Node pointer = this;
        while (pointer.left != RedBlackTree.NULL)
            pointer = pointer.left;
        return pointer;
    }

    @Override
    public String toString() {
        String position = "null";
        if (this.parent != RedBlackTree.NULL)
            position = this.parent.left == this ? "left" : "right";
        return "[key: " + key + ", color: " + color + ", parent: " + parent.key + ", position: " + position + "]";
    }
}

类RedTreeNode表示红黑树:

public class RedBlackTree {

    // 表示哨兵变量
    public final static Node NULL = new Node(Color.Black);

    public Node root;

    public RedBlackTree() {
        this.root = NULL;
    }

}

2、旋转

红黑树的插入和删除操作,能改变红黑树的结构,可能会使它不再有前面所说的某些特性性。为了维持这些特性,我们需要改变树中某些节点的颜色和位置。

我们可以通过旋转改变节点的结构。主要有 左旋转 右旋转 两种方式。具体如下图所示。

左旋转:把一个节点n的右子节点right变为它的父节点,n变为right的左子节点,所以right不能为null。这时n的右指针空了出来,right的左子树被n挤掉,所以right原来的左子树称为n的右子树。

右旋转:把一个节点n的左子节点left变为它的父节点,n变为left的右子节点,所以left不能为null。这时n的左指针被空了出来,left的右子树被n挤掉,所以left原来的右子树被称为n的左子树。

可在RedTreeNode类中,加上如下实现代码:

public void leftRotate(Node node) {
        Node rightNode = node.right;

        node.right = rightNode.left;
        if (rightNode.left != RedBlackTree.NULL)
            rightNode.left.parent = node;

        rightNode.parent = node.parent;
        if (node.parent == RedBlackTree.NULL)
            this.root = rightNode;
        else if (node.parent.left == node)
            node.parent.left = rightNode;
        else
            node.parent.right = rightNode;

        rightNode.left = node;
        node.parent = rightNode;
    }

    public void rightRotate(Node node) {
        Node leftNode = node.left;

        node.left = leftNode.right;
        if (leftNode.right != RedBlackTree.NULL)
            leftNode.right.parent = node;

        leftNode.parent = node.parent;
        if (node.parent == RedBlackTree.NULL) {
            this.root = leftNode;
        } else if (node.parent.left == node) {
            node.parent.left = leftNode;
        } else {
            node.parent.right = leftNode;
        }

        leftNode.right = node;
        node.parent = leftNode;
    }

3、插入

红黑树的插入代码与二分查找树的插入代码非常相似。只不过红黑树的插入操作会改变红黑树的结构,使其不在有该有的特性。

在这里,新插入的节点默认是红色。

所以在插入节点之后,要有维护红黑树特性的代码。

public void insert(Node node) {
        Node parentPointer = RedBlackTree.NULL;
        Node pointer = this.root;

        while (this.root != RedBlackTree.NULL) {
            parentPointer = pointer;
            pointer = node.key < pointer.key ? pointer.left : pointer.right;
        }

        node.parent = parentPointer;
        if(parentPointer == RedBlackTree.NULL) {
            this.root = node;
        }else if(node.key < parentPointer.key) {
            parentPointer.left = node;
        }else {
            parentPointer.right = node;
        }

        node.left = RedBlackTree.NULL;
        node.right = RedBlackTree.NULL;
        node.color = Color.Red;
        // 维护红黑树属性的方法
        this.insertFixUp(node);
    }

用上述方法插入一个新节点的时候,有两类情况会违反红黑树的特性。

  • 当树中没有节点时,此时插入的节点称为根节点,而此节点的颜色为红色。
  • 当新插入的节点成为一个红色节点的子节点时,此时存在一个红色结点有红色子节点的情况。

对于第一类情况,可以直接把根结点设置为黑色;而针对第二类情况,需要根据具体条件,做出相应的解决方案。

具体代码如下:

public void insertFixUp(Node node) {
        // 当node不是根结点,且node的父节点颜色为红色
        while (node.parent.color == Color.Red) {
            // 先判断node的父节点是左子节点,还是右子节点,这不同的情况,解决方案也会不同
            if (node.parent == node.parent.parent.left) {
                Node uncleNode = node.parent.parent.right;
                if (uncleNode.color == Color.Red) {  // 如果叔叔节点是红色,则父父一定是黑色
                    // 通过把父父节点变成红色,父节点和兄弟节点变成黑色,然后在判断父父节点的颜色是否合适
                    uncleNode.color = Color.Black;
                    node.parent.color = Color.Black;
                    node.parent.parent.color = Color.Red;
                    node = node.parent.parent;
                } else if (node == node.parent.right) {
                    node = node.parent;
                    this.leftRotate(node);
                } else {
                    node.parent.color = Color.Black;
                    node.parent.parent.color = Color.Red;
                    this.rightRotate(node.parent.parent);
                }
            } else {
                Node uncleNode = node.parent.parent.left;
                if (uncleNode.color == Color.Red) {
                    uncleNode.color = Color.Black;
                    node.parent.color = Color.Black;
                    node.parent.parent.color = Color.Red;
                    node = node.parent.parent;
                } else if (node == node.parent.left) {
                    node = node.parent;
                    this.rightRotate(node);
                } else {
                    node.parent.color = Color.Black;
                    node.parent.parent.color = Color.Red;
                    this.leftRotate(node.parent.parent);
                }
            }
        }
        // 如果之前树中没有节点,那么新加入的点就成了新结点,而新插入的结点都是红色的,所以需要修改。
        this.root.color = Color.Black;
    }

下面的图分别对应第二类情况中的六种及相应处理结果。

情况1:

情况2:

情况3:

情况4:

情况5:

情况6:

4、删除

红黑树中节点的删除会使一个结点代替另外一个节点。所以先要实现这样的代码:

public void transplant(Node n1, Node n2) {
        if(n1.parent == RedBlackTree.NULL){
            this.root = n2;
        }else if(n1.parent.left == n1) {
            n1.parent.left = n2;
        }else {
            n1.parent.right = n2;
        }
        n2.parent = n1.parent;
    }

红黑树的删除节点代码是基于二分查找树的删除节点代码而写的。

删除结点代码:

public void delete(Node node) {
        Node pointer1 = node;
        // 用于记录被删除的颜色,如果是红色,可以不用管,但如果是黑色,可能会破坏红黑树的属性
        Color pointerOriginColor = pointer1.color;
        // 用于记录问题的出现点
        Node pointer2;
        if (node.left == RedBlackTree.NULL) {
            pointer2 = node.right;
            this.transplant(node, node.right);
        } else if (node.right == RedBlackTree.NULL) {
            pointer2 = node.left;
            this.transplant(node, node.left);
        } else {
            // 如要删除的字节有两个子节点,则找到其直接后继(右子树最小值),直接后继节点没有非空左子节点。
            pointer1 = node.right.minimum();
            // 记录直接后继的颜色和其右子节点
            pointerOriginColor = pointer1.color;
            pointer2 = pointer1.right;
            // 如果其直接后继是node的右子节点,不用进行处理
            if (pointer1.parent == node) {
                pointer2.parent = pointer1;
            } else {
                // 否则,先把直接后继从树中提取出来,用来替换node
                this.transplant(pointer1, pointer1.right);
                pointer1.right = node.right;
                pointer1.right.parent = pointer1;
            }
            // 用node的直接后继替换node,继承node的颜色
            this.transplant(node, pointer1);
            pointer1.left = node.left;
            pointer1.left.parent = pointer1;
            pointer1.color = node.color;
        }
        if (pointerOriginColor == Color.Black) {
            this.deleteFixUp(pointer2);
        }
    }

当被删除节点的颜色是黑色时需要调用方法维护红黑树的特性。

主要有两类情况:

  • 当node是红色时,直接变成黑色即可。
  • 当node是黑色时,需要调整红黑树结构。,
private void deleteFixUp(Node node) {
        // 如果node不是根节点,且是黑色
        while (node != this.root && node.color == Color.Black) {
            // 如果node是其父节点的左子节点
            if (node == node.parent.left) {
                // 记录node的兄弟节点
                Node pointer1 = node.parent.right;
                // 如果他兄弟节点是红色
                if (pointer1.color == Color.Red) {
                    pointer1.color = Color.Black;
                    node.parent.color = Color.Red;
                    leftRotate(node.parent);
                    pointer1 = node.parent.right;
                }
                if (pointer1.left.color == Color.Black && pointer1.right.color == Color.Black) {
                    pointer1.color = Color.Red;
                    node = node.parent;
                } else if (pointer1.right.color == Color.Black) {
                    pointer1.left.color = Color.Black;
                    pointer1.color = Color.Red;
                    rightRotate(pointer1);
                    pointer1 = node.parent.right;
                } else {
                    pointer1.color = node.parent.color;
                    node.parent.color = Color.Black;
                    pointer1.right.color = Color.Black;
                    leftRotate(node.parent);
                    node = this.root;
                }
            } else {
                // 记录node的兄弟节点
                Node pointer1 = node.parent.left;
                // 如果他兄弟节点是红色
                if (pointer1.color == Color.Red) {
                    pointer1.color = Color.Black;
                    node.parent.color = Color.Red;
                    rightRotate(node.parent);
                    pointer1 = node.parent.left;
                }
                if (pointer1.right.color == Color.Black && pointer1.left.color == Color.Black) {
                    pointer1.color = Color.Red;
                    node = node.parent;
                } else if (pointer1.left.color == Color.Black) {
                    pointer1.right.color = Color.Black;
                    pointer1.color = Color.Red;
                    leftRotate(pointer1);
                    pointer1 = node.parent.left;
                } else {
                    pointer1.color = node.parent.color;
                    node.parent.color = Color.Black;
                    pointer1.left.color = Color.Black;
                    rightRotate(node.parent);
                    node = this.root;
                }
            }

        }
        node.color = Color.Black;
    }

对第二类情况,有下面8种:

情况1:

情况2:

情况3:

情况4:

情况5:

情况6:

情况7:

情况8:

5、所有代码

public enum Color {
    Black("黑色"), Red("红色");

    private String color;

    private Color(String color) {
        this.color = color;
    }

    @Override
    public String toString() {
        return color;
    }
}
public class Node {
    public int key;
    public Color color;
    public Node left;
    public Node right;
    public Node parent;

    public Node() {
    }

    public Node(Color color) {
        this.color = color;
    }

    public Node(int key) {
        this.key = key;
        this.color = Color.Red;
    }

    /**
     * 求在树中节点的高度
     *
     * @return
     */
    public int height() {
        return Math.max(left != RedBlackTree.NULL ? left.height() : 0, right != RedBlackTree.NULL ? right.height() : 0) + 1;
    }

    /**
     * 在以该节点为根节点的树中,求最小节点
     *
     * @return
     */
    public Node minimum() {
        Node pointer = this;
        while (pointer.left != RedBlackTree.NULL)
            pointer = pointer.left;
        return pointer;
    }

    @Override
    public String toString() {
        String position = "null";
        if (this.parent != RedBlackTree.NULL)
            position = this.parent.left == this ? "left" : "right";
        return "[key: " + key + ", color: " + color + ", parent: " + parent.key + ", position: " + position + "]";
    }
}
import java.util.LinkedList;
import java.util.Queue;

public class RedBlackTree {

    public final static Node NULL = new Node(Color.Black);

    public Node root;

    public RedBlackTree() {
        this.root = NULL;
    }

    /**
     * 左旋转
     *
     * @param node
     */
    public void leftRotate(Node node) {
        Node rightNode = node.right;

        node.right = rightNode.left;
        if (rightNode.left != RedBlackTree.NULL)
            rightNode.left.parent = node;

        rightNode.parent = node.parent;
        if (node.parent == RedBlackTree.NULL)
            this.root = rightNode;
        else if (node.parent.left == node)
            node.parent.left = rightNode;
        else
            node.parent.right = rightNode;

        rightNode.left = node;
        node.parent = rightNode;
    }

    /**
     * 右旋转
     *
     * @param node
     */
    public void rightRotate(Node node) {
        Node leftNode = node.left;

        node.left = leftNode.right;
        if (leftNode.right != RedBlackTree.NULL)
            leftNode.right.parent = node;

        leftNode.parent = node.parent;
        if (node.parent == RedBlackTree.NULL) {
            this.root = leftNode;
        } else if (node.parent.left == node) {
            node.parent.left = leftNode;
        } else {
            node.parent.right = leftNode;
        }

        leftNode.right = node;
        node.parent = leftNode;
    }

    public void insert(Node node) {
        Node parentPointer = RedBlackTree.NULL;
        Node pointer = this.root;

        while (pointer != RedBlackTree.NULL) {
            parentPointer = pointer;
            pointer = node.key < pointer.key ? pointer.left : pointer.right;
        }

        node.parent = parentPointer;
        if (parentPointer == RedBlackTree.NULL) {
            this.root = node;
        } else if (node.key < parentPointer.key) {
            parentPointer.left = node;
        } else {
            parentPointer.right = node;
        }

        node.left = RedBlackTree.NULL;
        node.right = RedBlackTree.NULL;
        node.color = Color.Red;
        this.insertFixUp(node);
    }

    private void insertFixUp(Node node) {
        // 当node不是根结点,且node的父节点颜色为红色
        while (node.parent.color == Color.Red) {
            // 先判断node的父节点是左子节点,还是右子节点,这不同的情况,解决方案也会不同
            if (node.parent == node.parent.parent.left) {
                Node uncleNode = node.parent.parent.right;
                if (uncleNode.color == Color.Red) { // 如果叔叔节点是红色,则父父一定是黑色
                    // 通过把父父节点变成红色,父节点和兄弟节点变成黑色,然后在判断父父节点的颜色是否合适
                    uncleNode.color = Color.Black;
                    node.parent.color = Color.Black;
                    node.parent.parent.color = Color.Red;
                    node = node.parent.parent;
                } else if (node == node.parent.right) { // node是其父节点的右子节点,且叔叔节点是黑色
                    // 对node的父节点进行左旋转
                    node = node.parent;
                    this.leftRotate(node);
                } else { // node如果叔叔节点是黑色,node是其父节点的左子节点,父父节点是黑色
                    // 把父节点变成黑色,父父节点变成红色,对父父节点进行右旋转
                    node.parent.color = Color.Black;
                    node.parent.parent.color = Color.Red;
                    this.rightRotate(node.parent.parent);
                }
            } else {
                Node uncleNode = node.parent.parent.left;
                if (uncleNode.color == Color.Red) {
                    uncleNode.color = Color.Black;
                    node.parent.color = Color.Black;
                    node.parent.parent.color = Color.Red;
                    node = node.parent.parent;
                } else if (node == node.parent.left) {
                    node = node.parent;
                    this.rightRotate(node);
                } else {
                    node.parent.color = Color.Black;
                    node.parent.parent.color = Color.Red;
                    this.leftRotate(node.parent.parent);
                }
            }
        }
        // 如果之前树中没有节点,那么新加入的点就成了新结点,而新插入的结点都是红色的,所以需要修改。
        this.root.color = Color.Black;
    }

    /**
     * n2替代n1
     *
     * @param n1
     * @param n2
     */
    private void transplant(Node n1, Node n2) {

        if (n1.parent == RedBlackTree.NULL) { // 如果n1是根节点
            this.root = n2;
        } else if (n1.parent.left == n1) { // 如果n1是其父节点的左子节点
            n1.parent.left = n2;
        } else { // 如果n1是其父节点的右子节点
            n1.parent.right = n2;
        }
        n2.parent = n1.parent;
    }

    /**
     * 删除节点node
     *
     * @param node
     */
    public void delete(Node node) {
        Node pointer1 = node;
        // 用于记录被删除的颜色,如果是红色,可以不用管,但如果是黑色,可能会破坏红黑树的属性
        Color pointerOriginColor = pointer1.color;
        // 用于记录问题的出现点
        Node pointer2;
        if (node.left == RedBlackTree.NULL) {
            pointer2 = node.right;
            this.transplant(node, node.right);
        } else if (node.right == RedBlackTree.NULL) {
            pointer2 = node.left;
            this.transplant(node, node.left);
        } else {
            // 如要删除的字节有两个子节点,则找到其直接后继(右子树最小值),直接后继节点没有非空左子节点。
            pointer1 = node.right.minimum();
            // 记录直接后继的颜色和其右子节点
            pointerOriginColor = pointer1.color;
            pointer2 = pointer1.right;
            // 如果其直接后继是node的右子节点,不用进行处理
            if (pointer1.parent == node) {
                pointer2.parent = pointer1;
            } else {
                // 否则,先把直接后继从树中提取出来,用来替换node
                this.transplant(pointer1, pointer1.right);
                pointer1.right = node.right;
                pointer1.right.parent = pointer1;
            }
            // 用node的直接后继替换node,继承node的颜色
            this.transplant(node, pointer1);
            pointer1.left = node.left;
            pointer1.left.parent = pointer1;
            pointer1.color = node.color;
        }
        if (pointerOriginColor == Color.Black) {
            this.deleteFixUp(pointer2);
        }
    }

    /**
     * The procedure RB-DELETE-FIXUP restores properties 1, 2, and 4
     *
     * @param node
     */
    private void deleteFixUp(Node node) {
        // 如果node不是根节点,且是黑色
        while (node != this.root && node.color == Color.Black) {
            // 如果node是其父节点的左子节点
            if (node == node.parent.left) {
                // 记录node的兄弟节点
                Node pointer1 = node.parent.right;
                // 如果node兄弟节点是红色
                if (pointer1.color == Color.Red) {
                    pointer1.color = Color.Black;
                    node.parent.color = Color.Red;
                    leftRotate(node.parent);
                    pointer1 = node.parent.right;
                }
                if (pointer1.left.color == Color.Black && pointer1.right.color == Color.Black) {
                    pointer1.color = Color.Red;
                    node = node.parent;
                } else if (pointer1.right.color == Color.Black) {
                    pointer1.left.color = Color.Black;
                    pointer1.color = Color.Red;
                    rightRotate(pointer1);
                    pointer1 = node.parent.right;
                } else {
                    pointer1.color = node.parent.color;
                    node.parent.color = Color.Black;
                    pointer1.right.color = Color.Black;
                    leftRotate(node.parent);
                    node = this.root;
                }
            } else {
                // 记录node的兄弟节点
                Node pointer1 = node.parent.left;
                // 如果他兄弟节点是红色
                if (pointer1.color == Color.Red) {
                    pointer1.color = Color.Black;
                    node.parent.color = Color.Red;
                    rightRotate(node.parent);
                    pointer1 = node.parent.left;
                }
                if (pointer1.right.color == Color.Black && pointer1.left.color == Color.Black) {
                    pointer1.color = Color.Red;
                    node = node.parent;
                } else if (pointer1.left.color == Color.Black) {
                    pointer1.right.color = Color.Black;
                    pointer1.color = Color.Red;
                    leftRotate(pointer1);
                    pointer1 = node.parent.left;
                } else {
                    pointer1.color = node.parent.color;
                    node.parent.color = Color.Black;
                    pointer1.left.color = Color.Black;
                    rightRotate(node.parent);
                    node = this.root;
                }
            }

        }
        node.color = Color.Black;
    }

    private void innerWalk(Node node) {
        if (node != NULL) {
            innerWalk(node.left);
            System.out.println(node);
            innerWalk(node.right);
        }
    }

    /**
     * 中序遍历
     */
    public void innerWalk() {
        this.innerWalk(this.root);
    }

    /**
     * 层次遍历
     */
    public void print() {
        Queue<Node> queue = new LinkedList<>();
        queue.add(this.root);
        while (!queue.isEmpty()) {
            Node temp = queue.poll();
            System.out.println(temp);
            if (temp.left != NULL)
                queue.add(temp.left);
            if (temp.right != NULL)
                queue.add(temp.right);
        }
    }

    // 查找
    public Node search(int key) {
        Node pointer = this.root;
        while (pointer != NULL && pointer.key != key) {
            pointer = pointer.key < key ? pointer.right : pointer.left;
        }
        return pointer;
    }

}

6、演示

演示代码:

public class Test01 {
  public static void main(String[] args) {
    int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8 };
    RedBlackTree redBlackTree = new RedBlackTree();
    for (int i = 0; i < arr.length; i++) {
      redBlackTree.insert(new Node(arr[i]));
    }
    System.out.println("树的高度: " + redBlackTree.root.height());
    System.out.println("左子树的高度: " + redBlackTree.root.left.height());
    System.out.println("右子树的高度: " + redBlackTree.root.right.height());
    System.out.println("层次遍历");
    redBlackTree.print();
    // 要删除节点
    Node node = redBlackTree.search(4);
    redBlackTree.delete(node);
    System.out.println("树的高度: " + redBlackTree.root.height());
    System.out.println("左子树的高度: " + redBlackTree.root.left.height());
    System.out.println("右子树的高度: " + redBlackTree.root.right.height());
    System.out.println("层次遍历");
    redBlackTree.print();
  }
}

到此这篇关于利用Java实现红黑树的文章就介绍到这了,更多相关Java实现红黑树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2021-09-14

Java数据结构之红黑树的真正理解

真正的帮助大家理解红黑树: 一.红黑树所处数据结构的位置: 在JDK源码中, 有treeMap和JDK8的HashMap都用到了红黑树去存储 红黑树可以看成B树的一种: 从二叉树看,红黑树是一颗相对平衡的二叉树 二叉树-->搜索二叉树-->平衡搜索二叉树--> 红黑树 从N阶树看,红黑树就是一颗 2-3-4树 N阶树-->B(B-)树 故我提取出了红黑树部分的源码,去说明红黑树的理解 看之前,理解红黑树的几个特性,后面的操作都是为了让树符合红黑树的这几个特性,从而满足对查找效率的O

图解红黑树及Java进行红黑二叉树遍历的方法

红黑树 红黑树是一种数据结构与算法课堂上常常提到但又不会细讲的树,也是技术面试中经常被问到的树,然而无论是书上还是网上的资料,通常都比较刻板难以理解,能不能一种比较直观的方式来理解红黑树呢?本文将以图形的方式来解释红黑树的插入与删除操作. 对树结构的学习是一个递进的过程,我们通常所接触的树都是二叉树,二叉树简单来说就是每个非叶子节点都有且只有两个孩子,分别叫做左孩子和右孩子.二叉树中有一类特殊的树叫二叉查找树,二叉查找树是一种有序的树,对于每个非叶子节点,其左子树的值都小于它,其右子树的值都大于

java算法实现红黑树完整代码示例

红黑树 定义 红黑树(英语:Red–black tree)是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组. 红黑树的另一种定义是含有红黑链接并满足下列条件的二叉查找树: 红链接均为左链接:没有任何一个结点同时和两条红链接相连:该树是完美黑色平衡的,即任意空链接到根结点的路径上的黑链接数量相同. 满足这样定义的红黑树和相应的2-3树是一一对应的. 旋转 旋转又分为左旋和右旋.通常左旋操作用于将一个向右倾斜的红色链接旋转为向左链接.对比操作前后,可以看出,该操作

通过java.util.TreeMap源码加强红黑树的理解

在此之前,我们已经为大家整理了很多关于经典问题红黑树的思路和解决办法.本篇文章,是通过分析java.util.TreeMap源码,让大家通过实例来对红黑树这个问题有更加深入的理解. 本篇将结合JDK1.6的TreeMap源码,来一起探索红-黑树的奥秘.红黑树是解决二叉搜索树的非平衡问题. 当插入(或者删除)一个新节点时,为了使树保持平衡,必须遵循一定的规则,这个规则就是红-黑规则:  1) 每个节点不是红色的就是黑色的  2) 根总是黑色的  3) 如果节点是红色的,则它的子节点必须是黑色的(反

基于红黑树插入操作原理及java实现方法(分享)

红黑树是一种二叉平衡查找树,每个结点上有一个存储位来表示结点的颜色,可以是RED或BLACK. 红黑树具有以下性质: (1) 每个结点是红色或是黑色 (2) 根结点是黑色的 (3) 如果一个结点是红色的,则它的两个儿子都是黑色的 (4) 对于每个结点,从该结点到其子孙结点的所有路径上包含相同数目的黑结点 通过红黑树的性质,可以保证所有基于红黑树的实现都能保证操作的运行时间为对数级别(范围查找除外.它所需的额外时间和返回的键的数量成正比). Java的TreeMap就是通过红黑树实现的. 红黑树的

Java红黑树的数据结构与算法解析

目录 红黑树的介绍 红黑树的实现 1.节点 2.查找 3.平衡化 颜色反转 插入的实现 红黑树的复杂度– 总结 红黑树的介绍 红黑树(Red-Black Tree,简称R-B Tree),它一种特殊的二叉查找树. 红黑树是特殊的二叉查找树,意味着它满足二叉查找树的特征:任意一个节点所包含的键值,大于等于左孩子的键值,小于等于右孩子的键值. 除了具备该特性之外,红黑树还包括许多额外的信息. 红黑树的每个节点上都有存储位表示节点的颜色,颜色是红(Red)或黑(Black). 红黑树的特性: (1)

java中treemap和treeset实现红黑树

TreeMap 的实现就是红黑树数据结构,也就说是一棵自平衡的排序二叉树,这样就可以保证当需要快速检索指定节点. TreeSet 和 TreeMap 的关系 为了让大家了解 TreeMap 和 TreeSet 之间的关系,下面先看 TreeSet 类的部分源代码: public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializab

详解Java中HashSet和TreeSet的区别

详解Java中HashSet和TreeSet的区别 1. HashSet HashSet有以下特点: 不能保证元素的排列顺序,顺序有可能发生变化 不是同步的 集合元素可以是null,但只能放入一个null 当向HashSet集合中存入一个元素时,HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值,然后根据 hashCode值来决定该对象在HashSet中存储位置. 简单的说,HashSet集合判断两个元素相等的标准是两个对象通过equals方法比较相等,并且两个

java中TreeMap排序的示例代码

1. 定义TreeMap的排序方法 使用Comparator对象作为参数 需要注意的是:排序方法是针对键的,而不是值的.如果想针对值,需要更麻烦的一些方法(重写一些方法) TreeMap<Screen,Integer> res = new TreeMap<Screen, Integer>(new Comparator<Screen>() { @Override public int compare(Screen screen1, Screen t1) { // 定义Tr

Java中Set与List的关系与区别介绍

两个接口都是继承自Collection. List (inteface) 次序是List 的最重要特点,它确保维护元素特定的顺序. --ArrayList 允许对元素快速随机访问. --LinkedList 对顺序访问进行优化,向List 中间插入与移除的开销并不大,具有addFrist(),addLast(),getFirst,getLast,removeFirst和removeLast().这些方法使得LinkedList可当作堆栈/队列/双向队列. Set (inteface) 存入Set

java 中HashMap、HashSet、TreeMap、TreeSet判断元素相同的几种方法比较

java 中HashMap.HashSet.TreeMap.TreeSet判断元素相同的几种方法比较 1.1     HashMap 先来看一下HashMap里面是怎么存放元素的.Map里面存放的每一个元素都是key-value这样的键值对,而且都是通过put方法进行添加的,而且相同的key在Map中只会有一个与之关联的value存在.put方法在Map中的定义如下. V put(K key, V value); 它用来存放key-value这样的一个键值对,返回值是key在Map中存放的旧va

浅谈java中的TreeMap 排序与TreeSet 排序

TreeMap: package com; import java.util.Comparator; import java.util.TreeMap; public class Test5 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub TreeMap<String, String> tree = new TreeMap<String,

Java中HashMap和TreeMap的区别深入理解

首先介绍一下什么是Map.在数组中我们是通过数组下标来对其内容索引的,而在Map中我们通过对象来对对象进行索引,用来索引的对象叫做key,其对应的对象叫做value.这就是我们平时说的键值对. HashMap通过hashcode对其内容进行快速查找,而 TreeMap中所有的元素都保持着某种固定的顺序,如果你需要得到一个有序的结果你就应该使用TreeMap(HashMap中元素的排列顺序是不固定的). HashMap 非线程安全 TreeMap 非线程安全 线程安全 在Java里,线程安全一般体