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 ¶
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