Documentation
¶
Overview ¶
Package ost provides the interfaces for order statistic trees, which are binary trees with the ability to perform log(n) time searches for elements in the tree with a specified rank, as well as log(n) time retrieval for the rank of a specified element in the tree.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Node ¶
type Node interface {
Left() (Node, error)
Right() (Node, error)
Size() int
Value() float64
Select(int) order.Node
Rank(float64) int
TreeString() string
}
Node is the interface for any node struct within an Tree.
type Tree ¶
type Tree interface {
Size() int
Add(float64)
Remove(float64)
Select(int) order.Node
Rank(float64) int
String() string
Clear()
}
Tree is the interface for order statistic trees, which are variants of binary trees that provide two additional methods: Select(i), which finds the ith smallest element in the tree, and Rank(x), which finds the rank of element x in the tree.
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
Package avl provides the implementation for an AVL tree, which satisfies the ost package interfaces, as well as the order package interfaces.
|
Package avl provides the implementation for an AVL tree, which satisfies the ost package interfaces, as well as the order package interfaces. |
|
Package rb provides the implementation for a red black tree, which satisfies the ost package interfaces, as well as the order package interfaces.
|
Package rb provides the implementation for a red black tree, which satisfies the ost package interfaces, as well as the order package interfaces. |
Click to show internal directories.
Click to hide internal directories.