BST树、红黑树（1-基本概念）
BST树、红黑树
BST树（二叉排序树，二叉搜索树）
定义：
(1) 若左子树非空，那么左子树上所有节点关键字均小于根节点的关键字值
(2) 若右子树非空，则右子树上的所有节点关键字均大于根节点的关键字值
(3) 左、右子树本身也是一颗二叉排序树
红黑树：
红黑树是一棵二叉搜索树，它在每个节点上增加了一个存储为来表示结点的颜色，可以是红色或者黑色。通过对任何一条从根到叶子结点的简单路径上各个结点的颜色来进行约束，红黑树确保没有任何一条路径会比其他路径长出两倍，因而近乎是平衡的。树的每个结点包含5个属性：color、key、left、right和p。
红黑树是满足以下条件的二叉搜索树：
（1） 每个结点或是红色的，或是黑色的。
（2） 根结点是黑色的。
（3） 每个叶子结点（NIL）是黑色的。
（4） 如果一个结点是红色的，则它的两个子结点都是黑色的。
（5） 对每个结点，从该节点到其所有后代叶子结点的简单路径上，均包含相同数目的黑色结点。
下图为一棵红黑树（省略了叶子结点NIL和根结点的父节点NIL）