Documentation ¶
Overview ¶
Package splay provides splay tree implementation. It is used to implement List by using splay tree.
Index ¶
- Variables
- type Node
- type Tree
- func (t *Tree[V]) CheckWeight() bool
- func (t *Tree[V]) Delete(node *Node[V])
- func (t *Tree[V]) DeleteRange(leftBoundary, rightBoundary *Node[V])
- func (t *Tree[V]) Find(index int) (*Node[V], int, error)
- func (t *Tree[V]) IndexOf(node *Node[V]) int
- func (t *Tree[V]) Insert(node *Node[V]) *Node[V]
- func (t *Tree[V]) InsertAfter(prev *Node[V], node *Node[V]) *Node[V]
- func (t *Tree[V]) Len() int
- func (t *Tree[V]) Splay(node *Node[V])
- func (t *Tree[V]) String() string
- func (t *Tree[V]) ToTestString() string
- func (t *Tree[V]) UpdateWeight(node *Node[V])
- type Value
Constants ¶
This section is empty.
Variables ¶
var ErrOutOfIndex = fmt.Errorf("out of index")
ErrOutOfIndex is returned when the given index is out of index.
Functions ¶
This section is empty.
Types ¶
type Node ¶
type Node[V Value] struct { // contains filtered or unexported fields }
Node is a node of Tree.
func (*Node[V]) InitWeight ¶ added in v0.2.10
func (t *Node[V]) InitWeight()
InitWeight sets initial weight of this node.
type Tree ¶
type Tree[V Value] struct { // contains filtered or unexported fields }
Tree is weighted binary search tree which is based on Splay tree. original paper on Splay Trees: https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf
func (*Tree[V]) CheckWeight ¶ added in v0.2.12
CheckWeight returns false when there is an incorrect weight node. for debugging purpose.
func (*Tree[V]) DeleteRange ¶ added in v0.2.10
DeleteRange separates the range between given 2 boundaries from this Tree. This function separates the range to delete as a subtree by splaying outer boundary nodes. leftBoundary must exist because of 0-indexed initial dummy node of tree, but rightBoundary can be nil means range to delete includes the end of tree. Refer to the design document: ./design/range-deletion-in-slay-tree.md
func (*Tree[V]) InsertAfter ¶
InsertAfter inserts the node after the given previous node.
func (*Tree[V]) ToTestString ¶ added in v0.4.8
ToTestString returns a string containing the metadata of the Node for debugging purpose.
func (*Tree[V]) UpdateWeight ¶ added in v0.2.8
UpdateWeight recalculates the weight of this node with the value and children.