红黑树是一种性能非常优秀的数据结构，关键在于它能保证最坏的性能也是对数的，主要是因为它是一种平衡的树，所以也叫平衡查找树。要理解红黑树，最好先看看我的上一篇博客《算法4》符号表以及二叉查找树，了解二叉查找树以及我们为什么需要平衡查找树。
二叉查找树中树高会受到输入数据的影响，极端情况下一棵树和一个链表没什么区别，所以我们需要一种树，它的所有叶节点到根节点的距离都是相等的
符号表就是键值对的集合，并且支持put和get操作。现实中符号表的应用非常广泛，所以这里介绍几种键值对的实现，主要是二叉查找树以及之后将要介绍的红黑树。 一个值得注意的点就是，符号表里面不允许重复的key，也就是put一个键值对时，会先查找符号表里面是否含有这个key，有的话就更改这个key对应的值，没有的话就新加一个键值对
我们维