二叉树相关

树 ...


红黑BST的基本操作过程

红黑BST是2-3查找树的一种具体实现方式,它将2-3查找树中的3-节点视为两个相连的2-节点,并对链接设定了颜色(红,黑)属性以描述这些特殊的2-节点。这样就不用再为3-节点定义专门的数据结构,基础操作直接复用BST的逻辑即可,基于基础操作可方便地实现更多更高级的操作。

红黑BST的基本设定:

  • 红色链接一律为左链接
  • 不可出现同时与两条红链接相连的节点

《2-3查找树的基本操作过程》中讨论删除操作的时候,把3-节点视为两个2-节点相连,且规定后来的那个节点为子节点,于是得到了下图。此时的链接就不都是左链接。

一个节点与两条红色链接相连的情况 ...


2-3查找树的基本操作过程

假设一组key:{ 9, 3, 8, 1, 2, 10, 4, 5, 7, 6 }

执行操作:put(key)、del(key)、get(key),只考虑key,不考虑value ...


二叉树的几个术语

根(root)节点、内部(inner)节点、叶子(leaf)节点。

边 ...


普通BST的基本操作过程

假设一组key:{ 9, 3, 8, 1, 2, 10, 4, 5, 7, 6 }

执行操作:put(key)、del(key)、get(key),只考虑key,不考虑value

put(key):插入一个键值为key的节点

依次插入上面的那10个key:

  • put(9)

  • put(3)

  • put ...