数据结构与算法 ||设计模式
20200730 红黑树
一、 二叉查找树（BST）具备什么特性呢？
1.左子树上所有结点的值均小于或等于它的根结点的值。
2.右子树上所有结点的值均大于或等于它的根结点的值。
3.左、右子树也分别为二叉排序树。
二分法查找思想，查找最大次数等同于二叉树的最大高度
二 、红黑树特点（就是平衡二叉树）
1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
自己积累：红黑树从根到叶子节点最长路径不会超过最短路径2蓓
插入或删除节点会破坏红黑树的平衡，解决办法：旋转（分为左旋转和右旋转）、变色
冒泡排序