publics/etcd-io__etcd @ 660dc83e1993359fe694dd89d70075d76f56ce6d

Gyuho Lee ffe90b9ff3 pkg/adt: remove TODO		5 vuotta sitten
..
img	d938435e44 pkg/adt: README "IntervalTree.Delete" test case images	5 vuotta sitten
README.md	d938435e44 pkg/adt: README "IntervalTree.Delete" test case images	5 vuotta sitten
doc.go	fc7da09d67 *: add missing godoc package descriptions	8 vuotta sitten
example_test.go	266214d19e pkg/adt: add "visitLevel", make "IntervalTree" interface, more tests	5 vuotta sitten
interval_tree.go	036bd1ab09 pkg/adt: fix interval tree black-height property based on rbtree	5 vuotta sitten
interval_tree_test.go	ffe90b9ff3 pkg/adt: remove TODO	5 vuotta sitten

Red-Black Tree

"Introduction to Algorithms" (Cormen et al, 3rd ed.), Chapter 13

Every node is either red or black.
The root is black.
Every leaf (NIL) is black.
If a node is red, then both its children are black.
For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

For example,

import (
    "fmt"

    "go.etcd.io/etcd/pkg/adt"
)

func main() {
    ivt := adt.NewIntervalTree()
    ivt.Insert(NewInt64Interval(510, 511), 0)
    ivt.Insert(NewInt64Interval(82, 83), 0)
    ivt.Insert(NewInt64Interval(830, 831), 0)
    ...

After inserting the values 510, 82, 830, 11, 383, 647, 899, 261, 410, 514, 815, 888, 972, 238, 292, 953.

Deleting the node 514 should not trigger any rebalancing:

Deleting the node 11 triggers multiple rotates for rebalancing:

Try yourself at https://www.cs.usfca.edu/~galles/visualization/RedBlack.html.

README.md

Red-Black Tree