avltree

Documentation

Index

• func GetRootValue[T cmp.Ordered](t *AvlTree[T]) T
• func ToArray[T cmp.Ordered](tree *AvlTree[T]) []T
• type AvlTree
  • func Delete[T cmp.Ordered](tree *AvlTree[T], value T) *AvlTree[T]
  • func Insert[T cmp.Ordered](tree *AvlTree[T], value T) *AvlTree[T]
  • func NewAvlTree[T cmp.Ordered]() *AvlTree[T]
  • func Search[T cmp.Ordered](tree *AvlTree[T], value T) *AvlTree[T]
  • func (tree *AvlTree[T]) String() string

Functions

func GetRootValue

func GetRootValue[T cmp.Ordered](t *AvlTree[T]) T

GetRootValue returns the value of the root node. If the tree is nil, returns the zero value of the type.

func ToArray

func ToArray[T cmp.Ordered](tree *AvlTree[T]) []T

ToArray returns an array with the values of the tree in order.

Types

type AvlTree

type AvlTree[T cmp.Ordered] struct {
	// contains filtered or unexported fields
}

AvlTree struct for an AVL Tree of any ordered type. This is a self-balancing binary tree. The difference between the heights of the left and right subtree cannot be more than one for all nodes. For more information about theory, see https://en.wikipedia.org/wiki/AVL_tree

func Delete

func Delete[T cmp.Ordered](tree *AvlTree[T], value T) *AvlTree[T]

Delete the value in the tree. If the tree is nil, it returns nil. If the value is equal to the root, it deletes the root. If the value is less than the root, it deletes in the left subtree. If the value is greater than the root, it deletes in the right subtree. After deleting, it rebalances the tree. It returns the new root of the tree.

func Insert

func Insert[T cmp.Ordered](tree *AvlTree[T], value T) *AvlTree[T]

Insert a value in the tree. If the tree is nil, it creates a new node with the value. If the value is already in the tree, it does nothing. If the value is less than the root, it inserts in the left subtree. If the value is greater than the root, it inserts in the right subtree. After inserting, it rebalances the tree. It returns the new root of the tree.

func NewAvlTree

func NewAvlTree[T cmp.Ordered]() *AvlTree[T]

NewAvlTree is factory function for avlTree struct. Return a nil pointer to avlTree.

func Search

func Search[T cmp.Ordered](tree *AvlTree[T], value T) *AvlTree[T]

Search returns the node with the value or nil if it is not found.

func (*AvlTree[T]) String

func (tree *AvlTree[T]) String() string

String returns a string representation of the tree.