avl_tree

Documentation

Index

• type ApplyFunction
• type AvlTree
  • func NewAvlTree[T comparable.Comparable]() *AvlTree[T]
  • func (tt *AvlTree[T]) Delete(find *T) (found bool)
  • func (tt *AvlTree[T]) DeleteAtHead() (found bool)
  • func (tt *AvlTree[T]) DeleteAtTail() (found bool)
  • func (tt *AvlTree[T]) Depth() (d int)
  • func (tt *AvlTree[T]) Dump(fo io.Writer)
  • func (tt *AvlTree[T]) FindMax() (item *T)
  • func (tt *AvlTree[T]) FindMin() (item *T)
  • func (tt *AvlTree[T]) Front() (rv *AvlTreeIter[T])
  • func (tt AvlTree[T]) Height(e *AvlTreeElement[T]) int
  • func (tt *AvlTree[T]) Index(pos int) (item *T)
  • func (tt *AvlTree[T]) Insert(item *T)
  • func (tt AvlTree[T]) IsEmpty() bool
  • func (tt *AvlTree[T]) Length() int
  • func (tt *AvlTree[T]) Reverse()
  • func (tt *AvlTree[T]) Search(find *T) (item *T)
  • func (tt *AvlTree[T]) Truncate()
  • func (tt *AvlTree[T]) WalkInOrder(fx ApplyFunction[T], userData interface{})
  • func (tt *AvlTree[T]) WalkPostOrder(fx ApplyFunction[T], userData interface{})
  • func (tt *AvlTree[T]) WalkPreOrder(fx ApplyFunction[T], userData interface{})
• type AvlTreeElement
  • func NewAvlTreeElement[T comparable.Comparable](x *T) *AvlTreeElement[T]
  • func (ee *AvlTreeElement[T]) GetData() *T
• type AvlTreeIter

Types

type ApplyFunction

type ApplyFunction[T comparable.Comparable] func(pos, depth int, data *T, userData interface{}) bool

type AvlTree

type AvlTree[T comparable.Comparable] struct {
	// contains filtered or unexported fields
}

AvlTree is a generic binary tree

func NewAvlTree

func NewAvlTree[T comparable.Comparable]() *AvlTree[T]

Create a new AvlTree and return it. Complexity is O(1).

func (*AvlTree[T]) Delete

func (tt *AvlTree[T]) Delete(find *T) (found bool)

func (*AvlTree[T]) DeleteAtHead

func (tt *AvlTree[T]) DeleteAtHead() (found bool)

func (*AvlTree[T]) DeleteAtTail

func (tt *AvlTree[T]) DeleteAtTail() (found bool)

func (*AvlTree[T]) Depth

func (tt *AvlTree[T]) Depth() (d int)

func (*AvlTree[T]) Dump

func (tt *AvlTree[T]) Dump(fo io.Writer)

Dump will print out the tree to the file `fo`.

func (*AvlTree[T]) FindMax

func (tt *AvlTree[T]) FindMax() (item *T)

FindMax returns the largest value in the tree.

func (*AvlTree[T]) FindMin

func (tt *AvlTree[T]) FindMin() (item *T)

func (*AvlTree[T]) Front

func (tt *AvlTree[T]) Front() (rv *AvlTreeIter[T])

Front will start at the inorder traversal beginning of the tree for iteration over tree.

func (AvlTree[T]) Height

func (tt AvlTree[T]) Height(e *AvlTreeElement[T]) int

func (*AvlTree[T]) Index

func (tt *AvlTree[T]) Index(pos int) (item *T)

func (*AvlTree[T]) Insert

func (tt *AvlTree[T]) Insert(item *T)

Insert will add a new item to the tree. If it is a duplicate of an exiting item the new item will replace the existing one.

func (AvlTree[T]) IsEmpty

func (tt AvlTree[T]) IsEmpty() bool

IsEmpty will return true if the binary-tree is empty

func (*AvlTree[T]) Length

func (tt *AvlTree[T]) Length() int

Length returns the number of elements in the list.

func (*AvlTree[T]) Reverse

func (tt *AvlTree[T]) Reverse()

Reverse swaps the order of all the nodes in the AVL Tree

func (*AvlTree[T]) Search

func (tt *AvlTree[T]) Search(find *T) (item *T)

Search will walk the tree looking for `find` and retrn the found item if it is in the tree. If it is not found then `nil` will be returned.

func (*AvlTree[T]) Truncate

func (tt *AvlTree[T]) Truncate()

Truncate removes all data from the tree.

func (*AvlTree[T]) WalkInOrder

func (tt *AvlTree[T]) WalkInOrder(fx ApplyFunction[T], userData interface{})

func (*AvlTree[T]) WalkPostOrder

func (tt *AvlTree[T]) WalkPostOrder(fx ApplyFunction[T], userData interface{})

func (*AvlTree[T]) WalkPreOrder

func (tt *AvlTree[T]) WalkPreOrder(fx ApplyFunction[T], userData interface{})

type AvlTreeElement

type AvlTreeElement[T comparable.Comparable] struct {
	// contains filtered or unexported fields
}

func NewAvlTreeElement

func NewAvlTreeElement[T comparable.Comparable](x *T) *AvlTreeElement[T]

func (*AvlTreeElement[T]) GetData

func (ee *AvlTreeElement[T]) GetData() *T

Complexity is O(1).

type AvlTreeIter

type AvlTreeIter[T comparable.Comparable] struct {
	// contains filtered or unexported fields
}

An iteration type that allows a for loop to walk the tree inorder.

This is more moemory effecient than the Walk* functions becasue it manages the stack interally. It is a tiny bit faster than the Walk* functions.

The main benefit is that it can be used to make cleaner code.