Red-Black Trees
Red-black trees are a representation of 2-3-4 trees using BST nodes.
- each node needs one extra value to encode link type
- but we no longer have to deal with different kinds of nodes
Link types:
- red links … combine nodes to represent 3- and 4-nodes
- black links … analogous to "ordinary" BST links (child links)
Advantages:
- standard BST search procedure works unmodified
- get benefits of 2-3-4 tree self-balancing (although deeper)
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}