红黑树结构详解

思考
你所知道的查找算法有哪些?

暴力: 遍历

二分: 能使用二分查找的前提条件:有序

哈希: 最高效,O(1),hash冲突,JDK1.8 里面 HashMap:链表+红黑树

插值:

索引: 搜索引擎,Lucene

平衡树:

:star2::star2::star2::star2:B+树:

B-Tree:

:star2::star2::star2::star2:红黑树: 高效的查找算法数据结构

:star2::star2::star2::star2:二叉搜索树:

如果说二分查找我让你转换成数据结构,你想到的是什么?

二叉树

二叉查找树:时间复杂度就是树的深度

二叉查找树

二叉搜索树又叫作:二叉查找树,二叉排序树。它具有一下特点:

  • 如果它的左子树不为空,则左子树节点的值都小于根结点。
  • 如果它的右子树不为空,则右子树结点的值都大于根结点。
  • 子树同样也要遵循以上两点。

为什么又叫作二叉排序树呢?二叉树的遍历方式:前、中、后、层次遍历。

只要一棵树是二叉搜索树,那么它的中序遍历一定是有序的。

二叉搜索树有哪些应用呢?

既然是搜索树,那么肯定就是用在了查找上。查找操作的时间复杂度是树的高度。

AVL 树:平衡二叉树(追求极致的平衡,理想状态),折中的办法:红黑树。

红黑树的底层结构是什么?(底层数据结构是一个特殊的二叉树,二叉查找树)

链表 ——> 二叉树 ——> 二叉查找树 ——> 特殊的二叉查找树(自平衡的二叉查找树)

红黑树

通过上面两幅图我们发现,二叉树的结构就决定了其搜索的性能,那么我们应该怎么优化呢?

因此就有了 AVL 树和红黑树

AVL 树: 平衡二叉树,它的左右子树高度之差不超过 1;这样确实可以避免一条直线型的结构,但还不是我们最理想的。

红黑树:红黑树是一颗特殊的二叉查找树,它同样满足二叉查找树的特点,左子树节点值均小于根结点值,右子树节点值均大于根结点值。但是它和普通的二叉查找树又有不同的地方,红黑树需要在二叉查找树的基础之上增加一些特殊的性质约束:

红黑树的性质(重点)

  • 每个结点不是红色就是黑色。
  • 不可能有连在一起的红色结点。
  • 根结点都是黑色。(入度为 0,或没有父节点的结点就是根结点)
  • 每个红色结点的两个子节点都是黑色,叶子节点都是黑色(出度为 0)。

红黑树的变换规则

为了满足红黑树的性质,因此出现了旋转:那么红黑树有几种变换呢?3 种变换规则,为了完成一颗红黑树:

  • 改变颜色:最简单(红变黑、黑变红)
  • 左旋:针对于点旋,但是点上面的子树也要跟着转。指针,科班生
  • 右旋:

红黑树的变换规则

旋转和颜色变换规则:所有插入的点默认为红色。否则,如果插入的点为黑色,那么此时整棵中全是黑色节点,没有红色节点,这就会导致任何时候”红黑树的性质“全部满足,也就无法触发红黑树的调整操作。

旋转和颜色变换规则

所有新插入的点默认为红色

  1. 变颜色的情况

当前节点的父亲和叔叔节点是红色的:

    • 把父节点变为黑色;
    • 把叔叔节点变为黑色;
    • 把爷爷节点变为红色;
    • 把指针定义到爷爷节点,设为当前要操作的节点。
    1. 左旋

    当前父节点是红色,叔叔节点是黑色,且当前节点是右子树时,左旋。

    1. 右旋

    当前父节点是红色,叔叔节点是黑色,且当前节点是左子树时,右旋。

    • 把父节点变为黑色;
    • 把爷爷节点变为红色;
    • 以爷爷节点为中心右旋。
    Last modification:July 26th, 2020 at 11:07 am
    如果觉得我的文章对你有用,请随意赞赏