README.md

Documentation: go.etcd.io/etcd/pkg/v3/adt

     1
     2## Red-Black Tree
     3
     4*"Introduction to Algorithms" (Cormen et al, 3rd ed.), Chapter 13*
     5
     61. Every node is either red or black.
     72. The root is black.
     83. Every leaf (NIL) is black.
     94. If a node is red, then both its children are black.
    105. For each node, all simple paths from the node to descendant leaves contain the
    11same number of black nodes.
    12
    13For example,
    14
    15```go
    16import (
    17    "fmt"
    18
    19    "go.etcd.io/etcd/pkg/v3/adt"
    20)
    21
    22func main() {
    23    ivt := adt.NewIntervalTree()
    24    ivt.Insert(NewInt64Interval(510, 511), 0)
    25    ivt.Insert(NewInt64Interval(82, 83), 0)
    26    ivt.Insert(NewInt64Interval(830, 831), 0)
    27    ...
    28```
    29
    30After inserting the values `510`, `82`, `830`, `11`, `383`, `647`, `899`, `261`, `410`, `514`, `815`, `888`, `972`, `238`, `292`, `953`.
    31
    32![red-black-tree-01-insertion.png](img/red-black-tree-01-insertion.png)
    33
    34Deleting the node `514` should not trigger any rebalancing:
    35
    36![red-black-tree-02-delete-514.png](img/red-black-tree-02-delete-514.png)
    37
    38Deleting the node `11` triggers multiple rotates for rebalancing:
    39
    40![red-black-tree-03-delete-11.png](img/red-black-tree-03-delete-11.png)
    41![red-black-tree-04-delete-11.png](img/red-black-tree-04-delete-11.png)
    42![red-black-tree-05-delete-11.png](img/red-black-tree-05-delete-11.png)
    43![red-black-tree-06-delete-11.png](img/red-black-tree-06-delete-11.png)
    44![red-black-tree-07-delete-11.png](img/red-black-tree-07-delete-11.png)
    45![red-black-tree-08-delete-11.png](img/red-black-tree-08-delete-11.png)
    46![red-black-tree-09-delete-11.png](img/red-black-tree-09-delete-11.png)
    47
    48Try yourself at https://www.cs.usfca.edu/~galles/visualization/RedBlack.html.
View as plain text