红黑树是一种自平衡的二叉查找树。

具有以下特点：

1. 节点是红色或者黑色
2. 根节点是黑色
3. 每个叶子节点都是黑色的空节点（NIL节点）
4. 每个红色节点的两个子节点都是黑色的。（从每个叶子到根的所有路径上不能有两个连续的红色节点）
5. 从任一节点到其每个叶子节点的所有路径都包含相同的数目的黑色节点。

二叉查找树（BST：Binary Search Tree）是一种特殊的二叉树，改善二叉树节点的查找效率。

特性：

其左子树下的每个后代节点的值都小于节点n的价值；

其右子树下的每个后代节点的值都大于节点n的值；

tree