红黑树
红黑树是一个能实现自平衡的二叉查找树
为何要引入红黑树:
首先来考虑一下二叉查找树 二叉查找树使用了二分查找的思想 查找所需的最大次数等同于二叉查找树的高度
但如果向二叉查找树一直插入一直比树结点更大或更小的值(例如结点由7 8 9 一直插入6 5 4 3 2 1) 二叉查找树就会失去平衡(1 2 3 4 5 6都是7的左孩子) 因此为了解决二叉查找树多次插入新结点导致的不平衡就需要引入红黑树
红黑树特点/规则
结点是红色或黑色
根结点一定是黑色的
每一个叶子结点(NIL)都是黑色
每个红色结点的两个子结点都是黑色
没有两个相邻的红色结点(红色结点不能有红色父结点和红色子结点 并没有说不能有两个连续的黑结点)
任意一个结点到其每个叶子结点(NIL)的路径都包含相同数目的黑色结点 简称为黑高
根据以上的几个规则作为限制 即可避免二叉查找树退化成单链表
对红黑树进行操作要面临的五种局面
当插入或删除结点的时候 红黑树原有构造的规则会被打破 因此需要对红黑树做一些调整 从而继续维持红黑树的规则
向红黑树插入14结点 由于父结点15 是黑色结点 这种情况没有破坏红黑树规则 无需做任何调整
