avl_tree

Documentation

Index

• type AVLTree
  • func New[K any, V any](predicate func(K, K) int) AVLTree[K, V]
  • func (a *AVLTree[K, V]) Begin() Iterator[K, V]
  • func (a *AVLTree[K, V]) Get(key K) (V, bool)
  • func (a *AVLTree[K, V]) Insert(key K, value V)
  • func (a *AVLTree[K, V]) Len() int
  • func (a *AVLTree[K, V]) Max() (K, V)
  • func (a *AVLTree[K, V]) Min() (K, V)
  • func (a *AVLTree[K, V]) Remove(key K)
• type Iterator
  • func (i *Iterator[K, V]) Get() (K, V)
  • func (i *Iterator[K, V]) HasNext() bool
  • func (i *Iterator[K, V]) Next()

Examples

• AVLTree.Get
• AVLTree.Insert
• AVLTree.Max
• AVLTree.Min
• AVLTree.Remove
• Iterator

Types

type AVLTree

type AVLTree[K any, V any] struct {
	// contains filtered or unexported fields
}

func New

func New[K any, V any](predicate func(K, K) int) AVLTree[K, V]

func (*AVLTree[K, V]) Begin

func (a *AVLTree[K, V]) Begin() Iterator[K, V]

Return an iterator points to the first element.

func (*AVLTree[K, V]) Get

func (a *AVLTree[K, V]) Get(key K) (V, bool)

Return the value and the exist indicator.

If the key exists, it returns (value, true).

Otherwise, it returns (zero value, false).

Example

tree := New[int, int](func(a, b int) int { return a - b })
tree.Insert(10, 20)
tree.Insert(5, 10)
tree.Insert(15, 125)

fmt.Println(tree.Get(10))
fmt.Println(tree.Get(199))

Output:

20 true
0 false

func (*AVLTree[K, V]) Insert

func (a *AVLTree[K, V]) Insert(key K, value V)

Insert a key value pair to the tree.

If the key value pair entry already exists, it updates the value.

Example

tree := New[int, int](func(a, b int) int { return a - b })
tree.Insert(10, 20)
tree.Insert(5, 10)
tree.Insert(15, 125)
fmt.Println(tree.Len())

Output:

3

func (*AVLTree[K, V]) Len

func (a *AVLTree[K, V]) Len() int

Return the number of element.

func (*AVLTree[K, V]) Max

func (a *AVLTree[K, V]) Max() (K, V)

Return the max key value pair.

Example

tree := New[int, int](func(a, b int) int { return a - b })
tree.Insert(10, 20)
tree.Insert(5, 10)
tree.Insert(15, 125)

fmt.Println(tree.Max())

Output:

15 125

func (*AVLTree[K, V]) Min

func (a *AVLTree[K, V]) Min() (K, V)

Return the min key value pair.

Example

tree := New[int, int](func(a, b int) int { return a - b })
tree.Insert(10, 20)
tree.Insert(5, 10)
tree.Insert(15, 125)

fmt.Println(tree.Min())

Output:

5 10

func (*AVLTree[K, V]) Remove

func (a *AVLTree[K, V]) Remove(key K)

Remove key entry from the tree.

Example

tree := New[int, int](func(a, b int) int { return a - b })
tree.Insert(10, 20)
tree.Insert(5, 10)
tree.Insert(15, 125)

fmt.Println(tree.Get(5))
tree.Remove(5)
fmt.Println(tree.Get(5))

Output:

10 true
0 false

type Iterator

type Iterator[K any, V any] struct {
	// contains filtered or unexported fields
}

Iterator that iterate through the tree using in-order traversal.

Example

tree := New[int, int](func(a, b int) int { return a - b })
tree.Insert(10, 4)
tree.Insert(-436, 8)
tree.Insert(5, 3)
tree.Insert(15, 12)
tree.Insert(12, 54)
tree.Insert(8, 123)
tree.Insert(6, 83)

for iter := tree.Begin(); iter.HasNext(); iter.Next() {
	fmt.Println(iter.Get())
}

Output:

-436 8
5 3
6 83
8 123
10 4
12 54
15 12

func (*Iterator[K, V]) Get

func (i *Iterator[K, V]) Get() (K, V)

Return the key value pair.

func (*Iterator[K, V]) HasNext

func (i *Iterator[K, V]) HasNext() bool

Return true if the iterator is not the end.

func (*Iterator[K, V]) Next

func (i *Iterator[K, V]) Next()

Advance the iterator.