对红黑树的不种见解

红黑树很出名，也有很多人知道怎么用，但红黑树是怎么发明的，发明动机是什么，设计思想是什么一直困扰着我，我以到网上搜索了很久都没有答案，就找到了红黑树之前就对称平衡二叉树，这种树有种不同类型的结点，是因为有彩色打印机，才把这两种不同类型的结点表示成不同的颜色，其它的我今天就来大胆猜测一下。

其实红黑树之所以那么流行，是因为他很好的平衡了一对矛盾，就是平衡度与维持这个平衡度所需要的性能代价，何谓平衡度，这个术语是我自己发明的，平衡度即一棵二叉树在固定高度的情况下能容纳的结点数量，容纳得最多则平衡度越大，所以完全平衡二叉树的平衡度都大，平衡度大有什么好处呢，很显然，平衡度最大，则固定结点数量的二叉树越矮，查找越快，这就是完全平衡二叉树的目的了。如果一棵二叉树是只读的，后续不用修改，那么用完全平衡二叉树最好用了，但是一般情况下我们都要修改这棵树，比如新增一个结点或删除一个结点，这个时候，你会发现一棵完全平衡二叉树很痛苦，因为插入了新的结点就打破了原有的平衡，要经过长时间的调整才能使树恢复平衡，删除结点也一样，这就好比打破一个生态环境的平衡一样痛苦。完全平衡二叉树走了查找效率这个极端，还有另一种极端的做法是就是插入和删点完全不调整，到最后那肯定是一棵很烂的棵树了，查找效率就等同于线性表了。

红黑树就做好了这两个极端之间的平衡，无论你是插入还是删除结点，他都能保证一趟搞定，一趟就是最多循环h次，h是树的高度，当然查找效率也不赖。他是怎么做到的呢，以下就是猜测了，他的创始人肯定也是因为遇到完全平衡二叉树的痛苦，所以他就要想办法偷个懒呗，他就想啊，可不可以修改树之后不需要调整树的结构呢，但是不调整，久而久之平衡度就会很差，所以还是要调整，那能不能少调整几次呢，比如有时候修改需要调整，有时候不需要调，所以我们可以引入的一种非正常的结点，这种结点很懒惰，插入之后可以不调整树，但懒惰结点的数量也不能太多，太多了就又变成烂树了，我们可以规定，懒惰结点不准连续，这样可以限制其数量不会太多，另一方面，我们也要求不同路径上正常结点的数量要相同，这样以来两个极端就都折衷了，再把正常结点标成黑，懒惰结点标成红，就成了红黑树了，当然这都是我的猜测，但这样可以更能看出红黑树的特点，所以我觉得将其改名为“懒惰结点平衡二叉树”更为贴切。

未完，持续更新中...