红黑树的基本知识

给梦想一点时间,让它一步步成长 有事做、有人爱、有所期待 本文由博客端 https://www.wslhome.top 主动推送

铺垫

在写之前我们先来点铺垫吧,就当是凑字数,练习打字了,搞起来。回忆一下你学的查找算法有哪些呢?总之我在之前虽然都知道,刷题时只是知道暴力破解...(小声逼逼:丢大家的脸了)。好了,那查找算法除了暴力破解(for 循环)外还有哪些呢?回忆一下大概有:二分查找、哈希、索引、B-Tree、B+Tree、BM 算法、KMP 之类的以及 bfs&dfs(图论中的遍历)等等....

在里面我们简单的二分、效率高的哈希。

敲重点:哈希的时间复杂度 O(1) 在 jdk1.7 中 Hashmap 采用链表 + 数组实现,其中链表引入为了解决 hash 冲突。在 1.8 中引入了红黑树,在 1.8 之前采用头插法会造成死循环,在 1.8 之后采用尾插法不会造成死循环。同时 HashMap 不是线程安全的可以使用 Collections.synchronizedMap(new HashMap(...));实现同步,同 HashTable 与 ConcurrentHashMap 属于线程安全、但是 hashtable 效率较差、基本不用。ConcurrentHashMap 效率较高。除此之外 1.8 的 HashMap 的性能高于 1.7 的性能(网友测试约 15%,在某些 size 区域更加高)。在 1.7 中,Hashmap 有两个重要的参数和三个构造函数,初始容量 16,默认负载因子 0.75,在 put 方法中元素大于等于 table 数组长度 x 负载因子的时候进行 2 的 n 次幂扩容。在 1.8 中当一个链表长度大于 8 的时候,HashMap 会动态的将它替换成一个红黑树(JDK1.8 引入红黑树大程度优化了 HashMap 的性能),这会将时间复杂度从 O(n)降为 O(logn)。

废话好像有点多了,接着说回来。

引入

在说红黑树之前,我们先来复习一个知识点。

二叉搜索树也就二叉查找树或者二叉排序树:

特点

image.png

但是有没有想过这样的一个问题,要是插入的值依次变大或者变小,然后出现树退化的情况

(贪心算法可以构建哈夫曼树也就是最优二叉树构建不了二叉查找树和红黑树,但是哈夫曼树在某些特殊情况下也会出现单分支情况从而退化成链表。)

image.png

在没有退化之前我们查找的复杂度为 lgn,但是上图的情况时间复杂度就变为 n。出现这样算法要怎么办呢?

如何才能让其不退化为链表呢?

这时候出现 AVL 树(平衡二叉树的折中(追求极致平衡、立项状态)< 实际应用中很少有人写 >)以及红黑树**(底层是特殊的二叉查找树)**

红黑树特点:

上面说到红黑树底层是特殊的二叉查找树,所以二叉具有的特点他也得有,其次还有的特点为:

先来看一个红黑树吧:

image.png

你看着上面这个难受,其实你平时看见的是这样的:

image.png

好了,图也看了,现在应该知道一下它的颜色是个什么回事。其实就是在二叉的基础上再每个点位增加了存储位表示红色或者黑色(0/1)。至于为什么要叫红黑树,好像是因为发明的那几个人,用马克笔画图,然而马克笔就是红色和黑色,所以就叫红黑树了。

接下来,我们要来学最重要的了:

红黑树的变换

改变颜色:红变黑、黑变红

左(右)旋:针对于点旋,但是点上面的子树也要跟着转

变颜色就不说了,先来简洁明了看看好多人都懵逼的旋转。

左旋:

左旋.gif

再来看一个右旋:

右旋.gif

旋转和颜色变换规则:所有插入的点默认为红色。

改变颜色:
当前节点的父亲是红色,且他的祖父(父亲的父亲)节点的另一个子节点(叔叔)为红色:

左旋:
当前节点的父节点是红色,祖父节点的另一个子节点(叔叔节点)是黑色的时候,且当前节点是右子树,以父节点左旋。

右旋:

当前节点的父节点是红色,祖父节点的另一个子节点(叔叔节点)是黑色的时候,且当前节点是左子树,以父节点右旋。

图解:

可能看着文字不理解,直接看图:

颜色变换:

颜色变换 1.gif

左旋:

左旋.gif

右旋:

右旋 1.gif

再一起来看一下整个过程:

全部.gif

红黑树其他知识:

赞助商 我要投放

回帖
请输入回帖内容 ...