TreeMap红黑树解析_treemap 红黑树

TreeMap红黑树

一、前言

​ TreeMap完全是红黑树实现的， 是由Josh Bloch 和 Doug Lea两位并发领域的大师共同完成，https://www.cs.usfca.edu/~galles/visualization/RedBlack.html 这个外网可以演示标准红黑树的执行过程。但是TreeMap的红黑树的代码实现同红黑树发明者用到的算法还是有一定差别的：

• ​ 标准红黑树：删除操作找前驱节点替代原删除节点
• ​ TreeMap: 删除操作找后继节点替代原删除节点

这两种方案实际操作效果是一样的，只不过树的结构不一样，但是对应的红黑 树都是平衡的，在此，先说一下红黑树的性质，以便后续使用

红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点(NIL或NULL）是黑色。
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
（6）红黑树时间复杂度是O(lgn)

二、二叉查找树（BST - Binary Search Tree ）

二叉树：每个子节点只有两个节点的树

二叉查找树（二叉搜索树）：就是一颗二叉树，他的左节点比父节点要小，右节点比父节点要大。他的 高度决定的查找效率。

图1是平衡二叉树，图2是倾斜二叉树，当我们自上而下将二叉树压到同一X平面时，我们会发现：7个数据会按顺序变为1234567

常见操作

查找（红黑树通用）：查找每个节点我们从根节点开始查找 查找值比当前值大，则搜索右子树查找值等于当前值，停止查找，返回当前节点 查找值比当前值小，则搜索左子树

**插入：**要插入节点，必须先找到插入节点位置。依然是从根节点开始比较，小于根节点的话就和左子树 比较，反之与右子树比较，直到左子树为空或者右子树为空，则插入到相应为空的位置。

**遍历（红黑树通用）：**根据一定顺序来访问整个树，常见的有前序遍历，中序遍历（用的较多），后序遍历

• 前序遍历：根节点-》左子树-》右子树 426 -》42136 -》 4 213 657
• 中序遍历：左子树-》根节点-》右子树 246 -》12346 -》123 4 567
• 后续遍历：左子树-》右子树-》根节点 264 -》13264 -》132 576 4

**查找最小值（红黑树通用）：**沿着根节点的左子树一路查找，直到最后一个不为空的节点，该节点就是当前这个树的最小节点

**查找最大值（红黑树通用）：**沿着根节点的右子树一路查找，直到最后一个不为空的节点，该节点就是当前这个树的最大节点

**查找前驱节点（红黑树通用）：**小于当前节点的最大值

**查找后继节点（红黑树通用）：**大于当前节点的最小值

**删除：**本质上是找前驱或者后继节点来替代 叶子节点直接删除（没有前驱或后继节点） 只有一个子节点的用子节点替代（本质上就是找的前驱节点或者是后继节点，左节点就是前驱节点，右节点就是后继节点） 有两个子节点的，需要找到替代节点（替代节点就是前驱节点或者后继节点） 红黑树删除操作和二叉树基本一致，只不过红黑树多了着色和旋转过程

三、BST存在的问题

BST存在的问题是，树在插入的时候会导致倾斜，不同的插入顺序会导致数的高度不一样，而树的高度 直接影响了树的查找效率。最坏的情况所有的节点都在一条斜线上，这样树的高度为N。

基于BST存在的问题，平衡查找二叉树（Balanced Binary Tree）产生了。平衡树的插入和删除的时候，会通过旋转操作将高度保持在logn。如果你没有听说过logn不要害怕， 我对logn的理解也是一知半解，记得我第一次听说logn可能是在学二分搜索算法的时候。二分搜索一定有某种行为使其时间复杂度为 logn。我们来看看是二分搜索是如何实现的。因为在最好情况下二分搜索的时间复杂度是 O(1)，最坏情况(平均情况)下 O(log n)，我们直接来看最坏情况下的例子。已知有 16 个元素的有序数组。

举个最坏情况的例子，比如我们要找的是数字 13。

1. 此时，我们需要使用二分搜索法进行数据查找，13 小于中心点，所以不用考虑数组的一半

2. 1.选中间的元素作为中心点(长度的一半)

$$16\ast 1/2=8拿到数组下标0-7的数据$$

​ 2.13大于中心点，所以拿到1的后半段
$$8\ast 1/2=4拿到数组下标4-7的数据$$
​

​ 3.13小于中心点，所以拿到2的前半段
$$4\ast 1/2=2拿到数组下标4-5的数据$$

​ 4.13大于中心点，所以拿到3的后半段
$$2\ast 1/2=1拿到数组下标5的数据$$

至此，获取数据结束，此时，我们通过2分法查询了一共4次数据，得到最终的值13，总结一下
$$16\ast (1/2{)}^4=1$$
如果此时存在n个元素，我们需要执行k次2分查找，根据以上公式，得到
$$n\ast (1/2{)}^k=1$$
进而得到
$$lo{g}_{2}n=k$$
因此，我们可以使用logn来表示这种行为，这也就是所谓的时间复杂度O(logn)，就是查询次数k。

平衡查找二叉树中两款具有代表性的平衡术分别为AVL树（高度平衡树，具备二叉搜索 树的全部特性，而且左右子树高度差不超过1）和红黑树。

一个失衡二叉树，含有10个元素

AVL树，从失衡二叉树得来需要进行6次旋转操作，参照规则为左右子树高度差不超过1，当某一节点的左右子树的高度差超过1时，则需要进行旋转，我们可以把旋转操作看成通过围绕当前结点的滑轮拉动运动，通过拉动滑轮，更改左右结点结构，用以达到目的

AVL树通过左旋或者右旋（左旋右旋后一定不会破坏二叉搜索树的查找规则）实现平衡

以指向根节点a为基准，

左旋是结点a向左旋转，带动其余结点转动的同时，指向从1变为3，3的前驱结点连接到1上，作为1的后继结点

右旋是结点a向右旋转，带动其余结点转动的同时，指向从3变为1，1的后继结点连接到3上，作为3的前驱结点

使用AVL树时，相较于失衡二叉树，其具有更快的查询优势，比如上面的失衡二叉树，根节点是10，当我们需要遍历到1时，我们需要遍历10次，而AVL，我们只需要遍历4次。

但是通过失衡二叉树旋转得到的AVL树，我们旋转的次数有点多，此时，红黑树（红黑树来源于2-3-4树）就出现了，可以兼顾AVL的查询效率的同时，还有更少的旋转次数，就是为了解决AVL多次旋转，造成性能浪费的问题

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】