RBTree - juedaiyuer/researchNote GitHub Wiki

#红黑树#

##红黑树的特性##

  1. 每个节点或者是黑色，或者是红色
  2. 根节点是黑色
  3. 只为空（NIL或null）的节点
  4. 如果一个节点是红色的，则它的子节点必须是黑色的
  5. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点；确保没有一条路径会比其它路径长出两倍，因而红黑树是相对接近平衡的二叉树

##红黑树的应用##

  • 用来存储有序的数据，时间复杂度为O（lgn）,效率非常之高
  • java集合TreeSet和TreeMap
  • C++ STL的set,map
  • Linux虚拟内存的管理

！RBTree

##基本定义##

##source##