Documentation
¶
Index ¶
- type CSBTree
- func (u *CSBTree[T, S]) Corrupt() bool
- func (u *CSBTree[T, S]) Has(v T) bool
- func (u *CSBTree) InOrder() func() (T, bool)
- func (u *CSBTree[T, S]) Insert(v T) bool
- func (u *CSBTree) KLargest(k uint) (T, bool)
- func (u *CSBTree) Maximum() (T, bool)
- func (u *CSBTree) Minimum() (T, bool)
- func (u *CSBTree[T, S]) Predecessor(v T) (T, bool)
- func (u *CSBTree[T, S]) RankOf(v T) uint
- func (u *CSBTree[T, S]) Remove(v T) bool
- func (u *CSBTree) Size() uint
- func (u *CSBTree[T, S]) Successor(v T) (T, bool)
- type SBTree
- func (u *SBTree[T, S]) Corrupt() bool
- func (u *SBTree[T, S]) Has(v T) bool
- func (u *SBTree) InOrder() func() (T, bool)
- func (u *SBTree[T, S]) Insert(v T) bool
- func (u *SBTree) KLargest(k uint) (T, bool)
- func (u *SBTree) Maximum() (T, bool)
- func (u *SBTree) Minimum() (T, bool)
- func (u *SBTree[T, S]) Predecessor(v T) (T, bool)
- func (u *SBTree[T, S]) RankOf(v T) uint
- func (u *SBTree[T, S]) Remove(v T) bool
- func (u *SBTree) Size() uint
- func (u *SBTree[T, S]) Successor(v T) (T, bool)
- type Tree
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type CSBTree ¶
type CSBTree[T any, S constraints.Unsigned] struct { // contains filtered or unexported fields }
CSBTree is the version of SBTree for user-defined struct satisfying Ordered interface. All methods are implemented exactly as SBTree except for using Ordered.LessThan and Ordered.Equals for comparisons. Argument passed to Ordered.LessThan and Ordered.Equals will always be type T so no type checks are needed.
func Build1 ¶ added in v0.4.0
func Build1[T any, S constraints.Unsigned](sli []T, lessThan, equals func(T, T) bool) *CSBTree[T, S]
Build1 is the CSBTree equivalence of Build
func New1 ¶ added in v0.4.0
func New1[T any, S constraints.Unsigned](lessThan, equals func(T, T) bool) *CSBTree[T, S]
New1 is the CSBTree equivalence of New
func (*CSBTree) InOrder ¶
func (u *CSBTree) InOrder() func() (T, bool)
InOrder [Tree.InOrder] Time: f(): amortized O(1) at each call to the returned function. Space: O(1)
func (*CSBTree) KLargest ¶
KLargest [Tree.KLargest] Returns (x,true) if k<= Size(), otherwise (0,false). This function utilizes the fact that base balances according to the sizes of each subtree to provide O(D) performance with very small constant. Time: O(D); Space: O(1)
func (*CSBTree) Maximum ¶
func (u *CSBTree) Maximum() (T, bool)
Maximum [Tree.Maximum] Time: O(D); Space: O(1)
func (*CSBTree) Minimum ¶
func (u *CSBTree) Minimum() (T, bool)
Minimum [Tree.Minimum] Time: O(D); Space: O(1)
func (*CSBTree[T, S]) Predecessor ¶
type SBTree ¶
type SBTree[T constraints.Ordered, S constraints.Unsigned] struct { // contains filtered or unexported fields }
SBTree is a binary search tree with no repeated values. It maintains balance through rotations by checking the sizes of subtrees. T is the type of values it will hold, S is the type of the variables used for storing the sizes of different subtrees. This struct holds a root pointer and a corresponding nilPtr used as nil described in nodePtr. This tree needs to keep track of the sizes of each subtree, so the additional memory cost is size(S)*n. The worst case height of the tree is less than f(n)=1.44*log2(n+1.5)-1.33. So the height D of the tree is of O(log n). However, on average, D=log2(N). Note that due to the way uint works in Go, and that the Tree interface defines the return value of some functions to be uint. S shouldn't be any type that will cause overflow when converted to uint. For example, uint on 32 bit machine is uint32, if S=uint64, then calling Size() can potentially result in undefined values as uint64 would cause overflow if converted to uint32. Generally, you should let S be a wide upperbound for the size of the tree.
func Build ¶ added in v0.4.0
func Build[T constraints.Ordered, S constraints.Unsigned](sli []T) *SBTree[T, S]
Build builds a SBTree using the given sorted slice recursively. This is faster than repeatedly calling Insert. The word "set" is used to show that there shouldn't be any repeated element. The given slice must be sorted in ascending order and mustn't contain duplicate elements(satisfying SBTree conditions), otherwise there will be corrupt structures. Time: O(n).
func New ¶ added in v0.4.0
func New[T constraints.Ordered, S constraints.Unsigned]() *SBTree[T, S]
New returns a SBTree satisfying the above definitions for nilPtr, root, and types. SBTree shouldn't be created directly using struct literal.
func (*SBTree) InOrder ¶
func (u *SBTree) InOrder() func() (T, bool)
InOrder [Tree.InOrder] Time: f(): amortized O(1) at each call to the returned function. Space: O(1)
func (*SBTree[T, S]) Insert ¶
Insert [Tree.Insert]. Recursive. It is a wrapper for insert. Time: O(D)
func (*SBTree) KLargest ¶
KLargest [Tree.KLargest] Returns (x,true) if k<= Size(), otherwise (0,false). This function utilizes the fact that base balances according to the sizes of each subtree to provide O(D) performance with very small constant. Time: O(D); Space: O(1)
func (*SBTree) Maximum ¶
func (u *SBTree) Maximum() (T, bool)
Maximum [Tree.Maximum] Time: O(D); Space: O(1)
func (*SBTree) Minimum ¶
func (u *SBTree) Minimum() (T, bool)
Minimum [Tree.Minimum] Time: O(D); Space: O(1)
func (*SBTree[T, S]) Predecessor ¶
Predecessor [Tree.Predecessor] Time: O(D); Space: O(1)
func (*SBTree[T, S]) RankOf ¶
RankOf [Tree.RankOf] This function utilizes the fact that SBTree balances according to the sizes of each subtree to provide O(D) performance with very small constant. Time: O(D); Space: O(1)
func (*SBTree[T, S]) Remove ¶
Remove [Tree.Remove]. Recursive. It is a wrapper for remove. Time: O(D)
type Tree ¶
type Tree[T any] interface { //Insert v to the Tree. Returning true if successful, false otherwise. //Exact behavior depend on implementation. Insert(v T) bool //Remove v from the Tree. Returning true if successful, false otherwise. //Exact behavior depend on implementation. Remove(v T) bool //Minimum element of the tree. Minimum() (T, bool) //Maximum element of the tree. Maximum() (T, bool) //Predecessor returns the greatest element less than v. Predecessor(v T) (T, bool) //Successor returns the smallest element greater than v. Successor(T) (T, bool) //KLargest find the k largest element. //1<=k<=Size(). KLargest(k uint) (T, bool) //RankOf v in the tree according to in-order. //1<=r<=Size() RankOf(v T) uint //Has element v. Note that even though by utilizing the second //return value of other methods achieves the same functionality //as Has, it is encouraged to use Has for the purposes of checking //if some value exists, as Has should be optimized for this purpose //in implementations. Has(v T) bool //Size of the tree. Size() uint //InOrder returns A closure function f acting like an iterator. f //gives nodes in the in-order traversal of the tree. //Calling f is like calling "Next()" of iterators: val, valid=f() //val is meaningful only if valid is true. When valid==false, //then f is exhausted. valid can't turn true after it first became false. //The tree must not be modified during the iteration of f, otherwise //it could corrupt the tree. There will be no panic if such cases //happens so design the algorithm with this in mind. InOrder() func() (T, bool) //Corrupt returns whether the tree has corrupt structures, when the value //at some node violates the properties of that specific implementation. //This is to be distinguished from whether the tree is balanced or not. Corrupt() bool }
Tree represents A tree like structure implemented using nodes. Receivers that has A bool as A second return value indicates whether the first return value is defined. For example, if calling Minimum on an empty tree, the return value will be (x T, false bool). In this case the value of x should be undefined. However, depending on specific implementations, the value of x might have A meaning, but it's advised that x not to be used. If an implementation didn't specify anything special, then the implemented receivers follows the behaviors defined here. Methods implemented recursively should be noted, otherwise functions are implemented iteratively.
Source Files