README

Red-Black Tree

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

  1. Every node is either red or black.
  2. The root is black.
  3. Every leaf (NIL) is black.
  4. If a node is red, then both its children are black.
  5. 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.

red-black-tree-01-insertion.png

Deleting the node 514 should not trigger any rebalancing:

red-black-tree-02-delete-514.png

Deleting the node 11 triggers multiple rotates for rebalancing:

red-black-tree-03-delete-11.png red-black-tree-04-delete-11.png red-black-tree-05-delete-11.png red-black-tree-06-delete-11.png red-black-tree-07-delete-11.png red-black-tree-08-delete-11.png red-black-tree-09-delete-11.png

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

Documentation

Overview

    Package adt implements useful abstract data types.

    Example
    Output:
    
    Overlapping range: &{Ivl:{Begin:7 End:20} Val:789}
    Overlapping range: &{Ivl:{Begin:9 End:13} Val:456}
    

    Index

    Examples

    Constants

    This section is empty.

    Variables

    This section is empty.

    Functions

    This section is empty.

    Types

    type BytesAffineComparable

    type BytesAffineComparable []byte

      BytesAffineComparable treats empty byte arrays as > all other byte arrays

      func (BytesAffineComparable) Compare

      func (b BytesAffineComparable) Compare(c Comparable) int

      type Comparable

      type Comparable interface {
      	// Compare gives the result of a 3-way comparison
      	// a.Compare(b) = 1 => a > b
      	// a.Compare(b) = 0 => a == b
      	// a.Compare(b) = -1 => a < b
      	Compare(c Comparable) int
      }

        Comparable is an interface for trichotomic comparisons.

        type Int64Comparable

        type Int64Comparable int64

        func (Int64Comparable) Compare

        func (v Int64Comparable) Compare(c Comparable) int

        type Interval

        type Interval struct {
        	Begin Comparable
        	End   Comparable
        }

          Interval implements a Comparable interval [begin, end) TODO: support different sorts of intervals: (a,b), [a,b], (a, b]

          func NewBytesAffineInterval

          func NewBytesAffineInterval(begin, end []byte) Interval

          func NewBytesAffinePoint

          func NewBytesAffinePoint(b []byte) Interval

          func NewInt64Interval

          func NewInt64Interval(a int64, b int64) Interval

          func NewInt64Point

          func NewInt64Point(a int64) Interval

          func NewStringAffineInterval

          func NewStringAffineInterval(begin, end string) Interval

          func NewStringAffinePoint

          func NewStringAffinePoint(s string) Interval

          func NewStringInterval

          func NewStringInterval(begin, end string) Interval

          func NewStringPoint

          func NewStringPoint(s string) Interval

          func (*Interval) Compare

          func (ivl *Interval) Compare(c Comparable) int

            Compare on an interval gives == if the interval overlaps.

            type IntervalTree

            type IntervalTree interface {
            	// Insert adds a node with the given interval into the tree.
            	Insert(ivl Interval, val interface{})
            	// Delete removes the node with the given interval from the tree, returning
            	// true if a node is in fact removed.
            	Delete(ivl Interval) bool
            	// Len gives the number of elements in the tree.
            	Len() int
            	// Height is the number of levels in the tree; one node has height 1.
            	Height() int
            	// MaxHeight is the expected maximum tree height given the number of nodes.
            	MaxHeight() int
            	// Visit calls a visitor function on every tree node intersecting the given interval.
            	// It will visit each interval [x, y) in ascending order sorted on x.
            	Visit(ivl Interval, ivv IntervalVisitor)
            	// Find gets the IntervalValue for the node matching the given interval
            	Find(ivl Interval) *IntervalValue
            	// Intersects returns true if there is some tree node intersecting the given interval.
            	Intersects(iv Interval) bool
            	// Contains returns true if the interval tree's keys cover the entire given interval.
            	Contains(ivl Interval) bool
            	// Stab returns a slice with all elements in the tree intersecting the interval.
            	Stab(iv Interval) []*IntervalValue
            	// Union merges a given interval tree into the receiver.
            	Union(inIvt IntervalTree, ivl Interval)
            }

              IntervalTree represents a (mostly) textbook implementation of the "Introduction to Algorithms" (Cormen et al, 3rd ed.) chapter 13 red-black tree and chapter 14.3 interval tree with search supporting "stabbing queries".

              func NewIntervalTree

              func NewIntervalTree() IntervalTree

                NewIntervalTree returns a new interval tree.

                type IntervalValue

                type IntervalValue struct {
                	Ivl Interval
                	Val interface{}
                }

                  IntervalValue represents a range tree node that contains a range and a value.

                  type IntervalVisitor

                  type IntervalVisitor func(n *IntervalValue) bool

                    IntervalVisitor is used on tree searches; return false to stop searching.

                    type StringAffineComparable

                    type StringAffineComparable string

                      StringAffineComparable treats "" as > all other strings

                      func (StringAffineComparable) Compare

                      func (s StringAffineComparable) Compare(c Comparable) int

                      type StringComparable

                      type StringComparable string

                      func (StringComparable) Compare

                      func (s StringComparable) Compare(c Comparable) int