红黑树

来自牛奶河Wiki
跳到导航 跳到搜索

红黑树(Red-Black Tree)，是一种特殊的二叉查找树，是相对是接近平衡的二叉树。红黑树的每个节点可以是红(Red)或黑(Black)。

红黑树的特性:

  1. 每个节点是黑色，或者是红色
  2. 根节点是黑色
  3. 每个 NIL 叶子节点是黑色
  4. 如果一个节点是红色的，则它的子节点必须是黑色的
  5. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点
取自“https://mwbbs.eu.org/wiki/index.php?title=红黑树&oldid=2423”