【51CTO.com原创稿件】 学过数据结构都知道二叉树的概念，而又有多种比较常见的二叉树类型，比如完全二叉树、满二叉树、二叉搜索树、均衡二叉树、完美二叉树等。

图片来自 Pexels

今天我们要说的红黑树就是就是一棵非严格均衡的二叉树，均衡二叉树又是在二叉搜索树的基础上增加了自动维持平衡的性质，插入、搜索、删除的效率都比较高。红黑树也是实现 TreeMap 存储结构的基石。

二叉搜索树

二叉搜索树又叫二叉查找树、二叉排序树，我们先看一下典型的二叉搜索树，这样的二叉树有何规则特点呢?

二叉搜索树有如下几个特点：

• 节点的左子树小于节点本身
• 节点的右子树大于节点本身
• 左右子树同样为二叉搜索树

下图就是一棵典型的二叉搜索树：

二叉搜索树是均衡二叉树的基础，我们看一下它的搜索步骤如何。我们要从二叉树中找到值为 58 的节点。

第一步：首先查找到根节点，值为 60 的节点。

第二步：比较我们要找的值 58 与该节点的大小。

如果等于，那么恭喜，已经找到;如果小于，继续找左子树;如果大于，那么找右子树。

很明显 58<60，因此我们找到左子树的节点 56，此时我们已经定位到了节点 56。