avl

Documentation

Index

• Variables
• type IntKey
  • func (a IntKey) Compare(b IntKey) int
• type Key
• type Node
  • func NewBalancedNode[K Key[K], V Value[V]](key K, value V, left *Node[K, V], right *Node[K, V]) *Node[K, V]
  • func (n *Node[K, V]) Clean() bool
  • func (n *Node[K, V]) Depth() int64
  • func (n *Node[K, V]) Key() K
  • func (n *Node[K, V]) Left() *Node[K, V]
  • func (n *Node[K, V]) Right() *Node[K, V]
  • func (n *Node[K, V]) String() string
  • func (n *Node[K, V]) Value() V
• type PostOrderCommitTraverser
  • func (p *PostOrderCommitTraverser[K, V]) SetClean(n *Node[K, V])
  • func (p *PostOrderCommitTraverser[K, V]) Traverse(n *Node[K, V])
• type Traverser
• type Tree
  • func New[K Key[K], V Value[V]]() *Tree[K, V]
  • func NewWithTraverser[K Key[K], V Value[V]](traverser Traverser[K, V]) *Tree[K, V]
  • func NewWithTraverserAndRoot[K Key[K], V Value[V]](traverser Traverser[K, V], root *Node[K, V]) *Tree[K, V]
  • func (t *Tree[K, V]) Add(key K, value V) error
  • func (t *Tree[K, V]) Clone() *Tree[K, V]
  • func (t *Tree[K, V]) Commit()
  • func (t *Tree[K, V]) Delete(key K) error
  • func (t *Tree[K, V]) Get(key K) (v V, err error)
  • func (t *Tree[K, V]) IsClean() bool
  • func (t *Tree[K, V]) Root() *Node[K, V]
  • func (t *Tree[K, V]) String() string
  • func (t *Tree[K, V]) Traverse(traverser Traverser[K, V])
  • func (t *Tree[K, V]) Update(key K, value V) error
• type Value

Variables

var ErrNotFound = errors.New("not found")

Types

type IntKey

type IntKey int

func (IntKey) Compare

func (a IntKey) Compare(b IntKey) int

Compare returns 0 if a == b, 1 if a > b, and -1 if a < b.

type Key

type Key[K any] interface {

	// Compare returns a negative integer, zero, or a positive integer as this Key is less than,
	// equal to, or greater than the specified key k.
	Compare(k K) int
}

Key represents the type of the key and is used to insert, update, search, and delete values from the AVL Tree.

type Node

type Node[K Key[K], V Value[V]] struct {
	// contains filtered or unexported fields
}

Node represents a single value in the AVL Tree, with a key of type K and a value of type V. If the node is a leaf, its left and right fields are nil. If the node is an inner node, it has at least one non-nil left or right field.

The depth of a leaf node is 1. The depth of an inner node is equal to the maximum depth of its children plus 1. For example, if the left child has a depth of 3 and the right child has a depth of 2, the depth of the inner node would be max(3, 2) + 1 = 3 + 1 = 4. Depth value is used to rebalance the AVL Tree.

To enable destructive updates, a node in an AVL tree has a "clean" field. Whenever a new node is added or an existing node is changed (including rotations), a copy of the node is made with the clean field set to false (see Tree.Clone function for more information).

func NewBalancedNode

func NewBalancedNode[K Key[K], V Value[V]](key K, value V, left *Node[K, V], right *Node[K, V]) *Node[K, V]

func (*Node[K, V]) Clean

func (n *Node[K, V]) Clean() bool

func (*Node[K, V]) Depth

func (n *Node[K, V]) Depth() int64

func (*Node[K, V]) Key

func (n *Node[K, V]) Key() K

func (*Node[K, V]) Left

func (n *Node[K, V]) Left() *Node[K, V]

func (*Node[K, V]) Right

func (n *Node[K, V]) Right() *Node[K, V]

func (*Node[K, V]) String

func (n *Node[K, V]) String() string

func (*Node[K, V]) Value

func (n *Node[K, V]) Value() V

type PostOrderCommitTraverser

type PostOrderCommitTraverser[K Key[K], V Value[V]] struct{}

PostOrderCommitTraverser is a Traverser that visits all non-clean nodes and sets the clean value to true.

func (*PostOrderCommitTraverser[K, V]) SetClean

func (p *PostOrderCommitTraverser[K, V]) SetClean(n *Node[K, V])

func (*PostOrderCommitTraverser[K, V]) Traverse

func (p *PostOrderCommitTraverser[K, V]) Traverse(n *Node[K, V])

type Traverser

type Traverser[K Key[K], V Value[V]] interface {
	Traverse(n *Node[K, V])
}

Traverser is an interface to traverse Tree.

type Tree

type Tree[K Key[K], V Value[V]] struct {
	// contains filtered or unexported fields
}

Tree represents an AVL tree.

This implementation is not safe for concurrent use by multiple goroutines. If multiple goroutines access a tree concurrently, and at least one of them modifies the tree, it must be synchronized externally.

Clone method may be used to make a copy of the tree (lazily). The original tree and the cloned tree can be used by different goroutines.

Tree is indexed according to the function Key.Compare result. Node value V can be any struct that implements Value interface.

func New

func New[K Key[K], V Value[V]]() *Tree[K, V]

New returns an empty AVL tree. - K is the type of the node's key (e.g. IntKey) - V is the type of the node's data (e.g. any kind of value that implements Value interface)

func NewWithTraverser

func NewWithTraverser[K Key[K], V Value[V]](traverser Traverser[K, V]) *Tree[K, V]

NewWithTraverser creates a new AVL tree with a custom Traverser.

func NewWithTraverserAndRoot

func NewWithTraverserAndRoot[K Key[K], V Value[V]](traverser Traverser[K, V], root *Node[K, V]) *Tree[K, V]

NewWithTraverserAndRoot creates a new AVL tree with a custom Traverser and a balanced root node.

func (*Tree[K, V]) Add

func (t *Tree[K, V]) Add(key K, value V) error

Add inserts the given value to the tree. The value is first inserted into the tree in the appropriate position as determined by the rules of a binary search tree. If the insertion causes the tree to become unbalanced, one or more tree rotations are performed to restore balance to the tree.

If a value with given key exists, returns an error.

This method should NOT be called concurrently!

func (*Tree[K, V]) Clone

func (t *Tree[K, V]) Clone() *Tree[K, V]

Clone clones the AVL tree, lazily.

This method should NOT be called concurrently!

The original tree and the cloned tree can be used by different goroutines. Writes to both old tree and cloned tree use copy-on-write logic, creating new nodes whenever one of nodes would have been modified. Read operations should have no performance degradation. Write operations will initially experience minor slow-downs caused by additional allocs and copies due to the aforementioned copy-on-write logic, but should converge to the original performance characteristics of the original tree.

func (*Tree[K, V]) Commit

func (t *Tree[K, V]) Commit()

Commit saves the changes made to the tree.

func (*Tree[K, V]) Delete

func (t *Tree[K, V]) Delete(key K) error

Delete removes a node with the given key from the AVL Tree. If no such value exists, returns an error.

This method should NOT be called concurrently!

func (*Tree[K, V]) Get

func (t *Tree[K, V]) Get(key K) (v V, err error)

Get looks for the value with given key in the AVL tree, returning it. Returns nil if unable to find that value.

func (*Tree[K, V]) IsClean

func (t *Tree[K, V]) IsClean() bool

IsClean returns true if t does not contain uncommitted changes, false otherwise.

func (*Tree[K, V]) Root

func (t *Tree[K, V]) Root() *Node[K, V]

func (*Tree[K, V]) String

func (t *Tree[K, V]) String() string

String returns a string of the AVL Tree. Should not be used to print out large trees.

func (*Tree[K, V]) Traverse

func (t *Tree[K, V]) Traverse(traverser Traverser[K, V])

Traverse traverses the given tree with the given traverser. Does nothing if the given traverser is nil.

func (*Tree[K, V]) Update

func (t *Tree[K, V]) Update(key K, value V) error

Update updates the given value with given key. If a value with given key does not exist, returns an error.

This method should NOT be called concurrently!

type Value

type Value[V any] interface {
	Clone() V
}

Value represents a value of the node.