数据结构与算法（十三）中红黑树的具体实现是怎样的？

本文共计2729个文字，预计阅读时间需要11分钟。

一、概要介绍红黑树是一种自平衡的排序二叉树，常用于关联数组和字典。在各种语言的底层实现中被广泛应用，如Java的TreeMap和TreeSet，以及JDK 8中的HashMap。

一、概述 1、介绍

　　红黑树是一种自平衡的排序二叉树，常用于关联数组、字典，在各种语言的底层实现中被广泛应用，Java 的 TreeMap 和 TreeSet 就是基于红黑树实现的，在 JDK 8 的HashMap中也有应用。
　　红黑树是在排序二叉树的基础上定义的，且还要满足以下性质（重要）：（请务必先学习排序二叉树，排序二叉树先看这篇 二叉树）
　　（1）每个结点要么是黑色，要么是红色。
　　（2）根结点是黑色。
　　（3）所有叶子结点都是黑色（这里说的叶子结点指 NIL 结点，空结点，即：空结点为黑色）。
　　（4）从任意一个结点到其所有叶子结点，所经过的黑色结点数目必须相等。
　　（5）所有红色结点的两个孩子结点必须是黑色（即，红色结点不能连续）。