README
¶
LLRB-Tree implementation for Go
This repository contains an implementation of a Left-Leaning Red-Black (LLRB) tree in Go. The LLRB tree is a self-balancing binary search tree that provides efficient operations for insertion, deletion, and search.
For more information and usage examples, please refer to the GoDoc documentation.
Documentation
¶
Overview ¶
Package llrb implements LLRB 2-3 trees, based on this paper:
A left-leaning red–black (LLRB) tree is a type of self-balancing binary search tree. It is a variant of the red–black tree and guarantees the same asymptotic complexity for operations, but is designed to be easier to implement.
Index ¶
- type CompareFunc
- type IterFunc
- type LLRBMap
- func (m *LLRBMap[K, V]) Clear()
- func (m *LLRBMap[K, V]) Delete(key K) (V, bool)
- func (m *LLRBMap[K, V]) Get(key K) (V, bool)
- func (m *LLRBMap[K, V]) Has(key K) bool
- func (m *LLRBMap[K, V]) Len() int
- func (m *LLRBMap[K, V]) Range(iter func(key K, value V) bool)
- func (m *LLRBMap[K, V]) Set(key K, value V) (V, bool)
- type LLRBSet
- type LLRBTree
- func (t *LLRBTree[T]) Ascend(iter IterFunc[T])
- func (t *LLRBTree[T]) AscendGreaterOrEqual(pivot T, iter IterFunc[T])
- func (t *LLRBTree[T]) AscendLessThan(pivot T, iter IterFunc[T])
- func (t *LLRBTree[T]) AscendRange(greaterOrEqual, lessThan T, iter IterFunc[T])
- func (t *LLRBTree[T]) Clear()
- func (t *LLRBTree[T]) Delete(item T) (deleted T, ok bool)
- func (t *LLRBTree[T]) DeleteMax() (deleted T, ok bool)
- func (t *LLRBTree[T]) DeleteMin() (deleted T, ok bool)
- func (t *LLRBTree[T]) Descend(iter IterFunc[T])
- func (t *LLRBTree[T]) DescendGreaterThan(pivot T, iter IterFunc[T])
- func (t *LLRBTree[T]) DescendLessOrEqual(pivot T, iter IterFunc[T])
- func (t *LLRBTree[T]) DescendRange(lessOrEqual, greaterThan T, iter IterFunc[T])
- func (t *LLRBTree[T]) Get(item T) (T, bool)
- func (t *LLRBTree[T]) Has(item T) bool
- func (t *LLRBTree[T]) Len() int
- func (t *LLRBTree[T]) ReplaceOrInsert(item T) (prev T, exist bool)
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type CompareFunc ¶
CompareFunc is a function type that compares two values of type T and returns an integer. It should return a negative value if a < b, 0 if a == b, and a positive value if a > b.
type IterFunc ¶
IterFunc is a function type that takes a value of type T and returns a boolean. It should return true to continue iteration, or false to stop iteration.
type LLRBMap ¶
LLRBMap represents a left-leaning red-black tree map.
Example ¶
package main
import (
"fmt"
"github.com/maolonglong/llrb"
)
func main() {
m := llrb.NewMap[int, string]()
m.Set(1, "apple")
m.Set(2, "banana")
m.Set(3, "cherry")
v, ok := m.Get(2)
if ok {
fmt.Println(v)
}
m.Delete(3)
m.Range(func(key int, value string) bool {
fmt.Println(key, value)
return true
})
}
Output: banana 1 apple 2 banana
func (*LLRBMap[K, V]) Clear ¶
func (m *LLRBMap[K, V]) Clear()
Clear removes all key-value pairs from the map, resulting in an empty map.
func (*LLRBMap[K, V]) Delete ¶
Delete removes the key-value pair with the specified key from the map. It returns the value associated with the key and a boolean indicating if the key existed.
func (*LLRBMap[K, V]) Get ¶
Get retrieves the value associated with the specified key from the map. It returns the value and a boolean indicating if the key exists in the map.
func (*LLRBMap[K, V]) Has ¶
Has checks if the map contains the specified key. It returns true if the key exists in the map, false otherwise.
type LLRBSet ¶
LLRBSet represents a set data structure implemented using a Left-Leaning Red-Black Tree.
Example ¶
package main
import (
"fmt"
"github.com/maolonglong/llrb"
)
func main() {
s := llrb.NewSet[int]()
s.Insert(1)
s.Insert(2)
s.Insert(2)
s.Insert(3)
fmt.Println(s.Len())
fmt.Println(s.Has(2))
s.Delete(2)
fmt.Println(s.Len())
s.Range(func(x int) bool {
fmt.Println(x)
return true
})
}
Output: 3 true 2 1 3
func (*LLRBSet[T]) Clear ¶
func (s *LLRBSet[T]) Clear()
Clear removes all values from the set, resulting in an empty set.
func (*LLRBSet[T]) Delete ¶
Delete removes a value from the set. It returns true if the value existed in the set, false otherwise.
func (*LLRBSet[T]) Has ¶
Has checks if the set contains the specified value. It returns true if the value exists in the set, false otherwise.
func (*LLRBSet[T]) Insert ¶
Insert inserts a value into the set. It returns true if the value already exists in the set, false otherwise.
type LLRBTree ¶
type LLRBTree[T any] struct { // contains filtered or unexported fields }
LLRBTree is a Left-Leaning Red-Black (LLRB) implementation of 2-3 trees.
Example ¶
package main
import (
"fmt"
"github.com/maolonglong/llrb"
)
func main() {
// Create a new LLRBTree
tree := llrb.NewOrdered[int]()
// Insert some items into the tree
tree.ReplaceOrInsert(5)
tree.ReplaceOrInsert(2)
tree.ReplaceOrInsert(7)
tree.ReplaceOrInsert(1)
tree.ReplaceOrInsert(4)
// Iterate over the tree in ascending order
tree.Ascend(func(item int) bool {
fmt.Println(item)
return true
})
}
Output: 1 2 4 5 7
func New ¶
func New[T any](compare CompareFunc[T]) *LLRBTree[T]
New creates a new LLRB-Tree with the given compare function.
func NewOrdered ¶
NewOrdered creates a new LLRB-Tree for ordered types.
func (*LLRBTree[T]) Ascend ¶
Ascend calls the iterator for every value in the tree within the range [first, last], until the iterator returns false.
func (*LLRBTree[T]) AscendGreaterOrEqual ¶
AscendGreaterOrEqual calls the iterator for every value in the tree within the range [pivot, last], until the iterator returns false.
func (*LLRBTree[T]) AscendLessThan ¶
AscendLessThan calls the iterator for every value in the tree within the range [first, pivot), until the iterator returns false.
func (*LLRBTree[T]) AscendRange ¶
AscendRange calls the iterator for every value in the tree within the range [greaterOrEqual, lessThan), until the iterator returns false.
func (*LLRBTree[T]) Clear ¶
func (t *LLRBTree[T]) Clear()
Clear removes all items from the LLRB-Tree.
func (*LLRBTree[T]) Delete ¶
Delete removes an item equal to the passed-in item from the tree, returning it. If no such item exists, it returns (nil, false).
func (*LLRBTree[T]) DeleteMax ¶
DeleteMax removes the largest item in the tree and returns it. If no such item exists, it returns (nil, false).
func (*LLRBTree[T]) DeleteMin ¶
DeleteMin removes the smallest item in the tree and returns it. If no such item exists, it returns (nil, false).
func (*LLRBTree[T]) Descend ¶
Descend calls the iterator for every value in the tree within the range [last, first], until the iterator returns false.
func (*LLRBTree[T]) DescendGreaterThan ¶
DescendGreaterThan calls the iterator for every value in the tree within the range [last, pivot), until the iterator returns false.
func (*LLRBTree[T]) DescendLessOrEqual ¶
DescendLessOrEqual calls the iterator for every value in the tree within the range [pivot, first], until the iterator returns false.
func (*LLRBTree[T]) DescendRange ¶
DescendRange calls the iterator for every value in the tree within the range [lessOrEqual, greaterThan), until the iterator returns false.
func (*LLRBTree[T]) Get ¶
Get looks for the key item in the tree, returning it. It returns (zeroValue, false) if unable to find that item.
func (*LLRBTree[T]) ReplaceOrInsert ¶
ReplaceOrInsert adds the given item to the tree. If an item in the tree already equals the given one, it is removed from the tree and returned, and the second return value is true. Otherwise, (zeroValue, false) is returned.
Note: nil cannot be added to the tree (undefined behavior).
Source Files