这效率也太低下了吧，一颗二叉查找树的优势完全丧失了。怎么办呢？既然上面的二叉查找树在插入的时候变成了“一条腿”，也就是丧失了平衡，那我们干脆做出一点改进，使用平衡二叉树吧。

二、平衡二叉树

下面就是一颗平衡二叉树。

上面这颗二叉树就是平衡二叉树，也叫作AVL树。仔细分析你会发现如下特点：

（1）从任何一个节点出发，左右子树深度之差的绝对值不超过1。

（2）左右子树仍然为平衡二叉树。

现在我们再往里插入一个元素4，这时候会发生什么呢？

从图中我们可以看到，插入了4之后破坏了平衡，怎么办呢？既然破坏了平衡，那就想办法纠正过来。

我们发现经过调整之后，我们二叉树就重新回到了平衡。对于其他插入的情况，大家可以自己私下试一遍，最终你会发现一个结论，那就是平衡二叉树在插入时最多只需要两次旋转就会重新恢复平衡。

从上面这个过程我们会发现，平衡二叉树真的很不错，在查找时既有着二叉查找树的优越性，在插入时还能通过调整继续保持着。那么为什么还要使用到红黑树呢？我觉得可以从以下两个方面来考虑：

（1）删除：对于平衡二叉树来说，在最坏情况下，需要维护从被删节点到根节点这条路径上所有节点的平衡性，旋转的量级是O(logN)。但是红黑树就不一样了，最多只需3次旋转就会重新平衡，旋转的量级是O(1)。

（2）保持平衡：平衡二叉树高度平衡，这也就意味着在大量插入和删除节点的场景下，平衡二叉树为了保持平衡需要调整的频率会更高。

注意：在大量查找的情况下，平衡二叉树的效率更高，也是首要选择。在大量增删的情况下，红黑树是首选。

鉴于以上原因，因此我们才使用到了红黑树这种更好的结构。上面提了这么多次红黑树，相信你已经迫不及待的想要认识一下了。下面就正式拉开红黑树的序幕。

三、红黑树

红黑树听名字就知道，里面涉及到两种颜色：红色和黑色。我们直接来看一下：