TreeMap的底层实现(红黑树)

知了堂姐

2024-07-09 11:12:24

0次

1、红黑树的基本概念。

红黑树，对很多童鞋来说，是既熟悉又陌生。学校中学过，只了解大概；工作中不怎么使用，但面试又是重点。每次需要查看红黑树内容时都很难以更生动形象的方式来理解其内容。没错，本文内容就是要解决这个问题，用简单的语言，搭配静图和动图(利用大脑图形记忆方式)，让你对红黑树有更深入的了解和更清晰的记忆，希望小伙伴们再次遇到红黑树的问题不至于头大。
每个节点都只能是红色或者黑色根节点是黑色每个叶节点（NIL节点，空节点）是黑色的。如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

2、Java 中TreeMap是如何通过put、deleteEntry两个来实现红黑树增加、删除节点的。

3、TreeMap数据结构

TreeMap的定义如下：
public class TreeMap extends AbstractMap implements NavigableMap, Cloneable, java.io.Serializable
TreeMap继承AbstractMap，实现NavigableMap、Cloneable、Serializable三个接口。其中AbstractMap表明TreeMap为一个Map即支持key-value的集合

TreeMap put()方法实现分析

在TreeMap的put()的实现方法中主要分为两个步骤，第一：构建排序二叉树，第二：平衡二叉树。

对于排序二叉树的创建，其添加节点的过程如下：

以根节点为初始节点进行检索。与当前节点进行比对，若新增节点值较大，则以当前节点的右子节点作为新的当前节点。否则以当前节点的左子节点作为新的当前节点。循环递归2步骤知道检索出合适的叶子节点为止。将新增节点与3步骤中找到的节点进行比对，如果新增节点较大，则添加为右子节点；否则添加为左子节点。按照这个步骤我们就可以将一个新增节点添加到排序二叉树中合适的位置

4.红黑树的定义（特性）

1. 根节点是【黑色】2. 每个节点要么是【黑色】要么是【红色】3. 每个【红色】节点的两个子节点一定都是【黑色】4. 每个叶子节点（NIL）都是【黑色】5. 任意一个节点的路径到叶子节点所包含的【黑色】节点的数量是相同的---这个也称之为【黑色完美平衡】6. 新插入的节点必须是【红色】->为什么？如果新插入的节点是【黑色】，那不管是在插入到那里，一定会破坏黑色完美平衡的，因为任意一个节点的路径到叶子节点的黑色节点的数量肯定不一样了（第 6 点我自己加的，实际特性的定义是前 5 个）

5.红黑树与AVL树的比较

1. AVL树的时间复杂度优于红黑树，但是对于现在的计算机，这种差别可以忽略2. 红黑树的插入删除比AVL树更便于控制操作。3. 红黑树整体性能略优于AVL树。（红黑树旋转情况少于AVL树）。这点是非常重要的4. 如果是在查询很多增删少的情况下 AVL 树还是优于红黑树的，如果增删比较频繁，那红黑树绝对是完美的一种选择

红黑树在添加和删除节点的时候是靠什么来维持平衡的呢？那就是左旋、右旋加变色

左旋、右旋加变色的定义（旋那边另一半的的反方向子节点给对方）

左旋:以某个节点作为固定支撑点（围绕该节点旋转）,其右子节点变为旋转节点的父节点，右子节点的左子节点变为旋转节点的右子节点，左子节点保持不变右旋: 以某个节点作为固定支撑点（围绕该节点旋转），其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变变色:节点的颜色由红色变成黑色，或者是由黑色变成红色