数据结构-红黑树

首先了解下二叉树特性:

    1.左子树上所有的节点的值均小于或等于它的根节点的值

    2.右子树上所有节点的值均大于或等于它的根节点的值

    3.左右子树也分别为二叉树排序

二叉树优缺点:查找所需要的最大次数等同于二叉查找树丶高度.在插入结点的时候也是利用类似的方法,通过一层一层比较大小,找到新节点适合插入位置.缺点就是后来插入的很容易变成线性结构,查找性能大打折扣.

红黑树特性:

    1.红黑树是一种自平衡的二叉查找树.

    2.节点是红色或者黑色

    3.根节点是黑色

    4.每个叶子节点都是黑色的空节点(NIL节点)

    5.每个红色节点的两字子节点都是黑色(从每个叶子到根的所有路径上不能有两个连续的红色节点)

    6.从任一节点到其每个叶子所有路径都包含相同数目的黑色节点

红黑树从根到叶子的最长路径不会超过最短路径的2倍,当插入或删除节点的时候,红黑树的规则很有可能被破坏,我们需要调整,来维持规则.

调整的两种方法:

    变色:为了重新符合红黑树的规则,尝试把红色节点变为黑色,或者把黑色节点变为红色

    旋转有两种情况:

    左旋转:逆时针旋转红黑树的两个节点,使得父节点被自己的右孩子取代,而自己的成为自己的做孩子.如下图

    右旋转:顺时针旋转红黑树的两个节点,使得父节点被自己的左孩子取代,而自己成为自己的右孩子.

红黑树实际应用:JDK的集合类TreeMap和TreeSet底层就是红黑树实现的,在java8中,HashMap也用到红黑树.