README
¶
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.
Documentation
¶
Overview ¶
Package adt implements useful abstract data types.
Example ¶
package main
import (
"fmt"
"github.com/coreos/etcd/pkg/adt"
)
func main() {
ivt := adt.NewIntervalTree()
ivt.Insert(adt.NewInt64Interval(1, 3), 123)
ivt.Insert(adt.NewInt64Interval(9, 13), 456)
ivt.Insert(adt.NewInt64Interval(7, 20), 789)
rs := ivt.Stab(adt.NewInt64Point(10))
for _, v := range rs {
fmt.Printf("Overlapping range: %+v\n", v)
}
}
Output: Overlapping range: &{Ivl:{Begin:7 End:20} Val:789} Overlapping range: &{Ivl:{Begin:9 End:13} Val:456}
Index ¶
- type BytesAffineComparable
- type Comparable
- type Int64Comparable
- type Interval
- func NewBytesAffineInterval(begin, end []byte) Interval
- func NewBytesAffinePoint(b []byte) Interval
- func NewInt64Interval(a int64, b int64) Interval
- func NewInt64Point(a int64) Interval
- func NewStringAffineInterval(begin, end string) Interval
- func NewStringAffinePoint(s string) Interval
- func NewStringInterval(begin, end string) Interval
- func NewStringPoint(s string) Interval
- type IntervalTree
- type IntervalValue
- type IntervalVisitor
- type StringAffineComparable
- type StringComparable
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 NewBytesAffinePoint ¶
func NewInt64Interval ¶
func NewInt64Point ¶
func NewStringAffineInterval ¶
func NewStringAffinePoint ¶
func NewStringInterval ¶
func NewStringPoint ¶
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
Source Files