最近学习数据结构和c++的STL，了解到了map、set的实现都是依靠红黑树，依靠红黑树的这两个容器都有查找速度快，插入删除元素快的特点，下面记录一下红黑树的原理及实现。
红黑树本质上也是一个平衡二叉树，但是它并不是严格意义上的完全平衡二叉树（AVL），而是黑色节点平衡二叉树。
红黑树的几个性质：
- 树中只有红色或黑色的节点（每个节点不是红色就是黑色）
- 根节点是黑色节点
- 每个叶子节点（NIL）是黑色节点（NIL可以看作是空的叶子节点）
- 每个红色节点的两个子节点都是黑色
- 任意节点到每个叶子节点的路径都包含相同数量的黑节点
红黑树的查找和普通的二叉树一样，但又因为红黑树总能保证黑色平衡，时间复杂度就为O(2logn)，所以查找的速度很快。
红黑树的插入、删除速度也很快。在c++中，由红黑树构成的数据结构（map、set、multimap、multiset）在插入或者删除操作时不需要操作内存，当插入或删除操作后，它对应的迭代器（itrator）也不需要重新声明，究其原因是因为当进行插入/删除操作时，本质上只是指针的指向进行了改变，而容器内储存的仅仅是节点的关系，而不是真正的数据。新节点也只是加了一个额外的指针进行指向，所以迭代器也可以正常继续使用。
