avltree

Documentation

Overview

Package AVLTree functions

Example (AvlTree)

package main

import (
	"fmt"
	"github.com/jenazads/gods/trees/avltree"
	"github.com/jenazads/goutils"
)

func main() {
	tree := avltree.NewAVLTree(goutils.IntComparator, goutils.IntOperator)

	tree.Insert(1, "x")
	tree.Insert(2, "b")
	tree.Insert(1, "a")
	tree.Insert(3, "c")
	tree.Insert(4, "d")
	tree.Insert(5, "e")
	tree.Insert(6, "f")
	tree.Insert(7, "g")
	tree.Insert(8, "h")

	tree.PrintPreOrder()
	tree.PrintInOrder()
	tree.PrintPostOrder()

	fmt.Println(tree.Ceiling(4))
	fmt.Println(tree.Floor(5))
	tree.Print()

	fmt.Println(tree.Values())
	fmt.Println(tree.Keys())

	fmt.Print(tree)
	tree.Remove(3)
	fmt.Println(tree)
	tree.Remove(2)
	fmt.Println(tree)
	tree.Remove(7)
	fmt.Println(tree)
	tree.Remove(5)
	fmt.Println(tree)
	tree.Remove(6)
	fmt.Println(tree)
	tree.Remove(1)
	fmt.Println(tree)
	tree.Remove(4)
	fmt.Println(tree)
	tree.Remove(8)
	fmt.Println(tree)

	tree.Clear()
	tree.IsEmpty()
	tree.Size()
}

Index

• func IsLeaf(node *AVLNode) bool
• type AVLNode
  • func NewAVLNode(key interface{}, value interface{}, p *AVLNode) *AVLNode
  • func (node *AVLNode) Next() *AVLNode
  • func (node *AVLNode) Prev() *AVLNode
  • func (node *AVLNode) String() string
• type AVLTree
  • func NewAVLTree(comp goutils.TypeComparator, op goutils.TypeOperator) *AVLTree
  • func (t *AVLTree) Brother(key interface{}) *AVLNode
  • func (t *AVLTree) Ceiling(key interface{}) *AVLNode
  • func (t *AVLTree) Clear()
  • func (t *AVLTree) Floor(key interface{}) *AVLNode
  • func (t *AVLTree) FromJSON(data []byte) error
  • func (t *AVLTree) Get(key interface{}) interface{}
  • func (t *AVLTree) Height() int
  • func (t *AVLTree) HeightOfNode(key interface{}) int
  • func (t *AVLTree) Insert(key interface{}, value interface{})
  • func (t *AVLTree) IsEmpty() bool
  • func (t *AVLTree) IsSameAs(otherTree *AVLTree) bool
  • func (t *AVLTree) Iterator() goutils.ReverseIteratorKey
  • func (t *AVLTree) Keys() []interface{}
  • func (t *AVLTree) LeafCount() int
  • func (t *AVLTree) Left() *AVLNode
  • func (t *AVLTree) Mirror()
  • func (t *AVLTree) Parent(key interface{}) *AVLNode
  • func (t *AVLTree) Print()
  • func (t *AVLTree) PrintInOrder()
  • func (t *AVLTree) PrintPostOrder()
  • func (t *AVLTree) PrintPreOrder()
  • func (t *AVLTree) Remove(key interface{})
  • func (t *AVLTree) Right() *AVLNode
  • func (t *AVLTree) Search(key interface{}) *AVLNode
  • func (t *AVLTree) Size() int
  • func (t *AVLTree) String() string
  • func (t *AVLTree) SumNodes() interface{}
  • func (t *AVLTree) ToJSON() ([]byte, error)
  • func (t *AVLTree) Values() []interface{}
• type Iterator
  • func (iterator *Iterator) Begin()
  • func (iterator *Iterator) End()
  • func (iterator *Iterator) First() bool
  • func (iterator *Iterator) Key() interface{}
  • func (iterator *Iterator) Last() bool
  • func (iterator *Iterator) Next() bool
  • func (iterator *Iterator) Prev() bool
  • func (iterator *Iterator) Value() interface{}

Examples

• Package (AvlTree)

Functions

func IsLeaf

func IsLeaf(node *AVLNode) bool

Return true if the node is leaf

Types

type AVLNode

type AVLNode struct {
	Key      interface{}
	Value    interface{}
	Parent   *AVLNode    // Parent node
	Children [2]*AVLNode // Children nodes, 0-> left, 1-> right
	// contains filtered or unexported fields
}

Node

func NewAVLNode

func NewAVLNode(key interface{}, value interface{}, p *AVLNode) *AVLNode

New AVL Node

func (*AVLNode) Next

func (node *AVLNode) Next() *AVLNode

Return next or sucessor node

func (*AVLNode) Prev

func (node *AVLNode) Prev() *AVLNode

Return previous or predecessor node

func (*AVLNode) String

func (node *AVLNode) String() string

Print Node with fmt.Print*

type AVLTree

type AVLTree struct {
	Root *AVLNode // Root node
	// contains filtered or unexported fields
}

AVLTree object

func NewAVLTree

func NewAVLTree(comp goutils.TypeComparator, op goutils.TypeOperator) *AVLTree

New AVL Tree

func (*AVLTree) Brother

func (t *AVLTree) Brother(key interface{}) *AVLNode

Return the brother of a specific value

func (*AVLTree) Ceiling

func (t *AVLTree) Ceiling(key interface{}) *AVLNode

Return the smallest node that is larger than or equal to the given node.

func (*AVLTree) Clear

func (t *AVLTree) Clear()

Removes all nodes

func (*AVLTree) Floor

func (t *AVLTree) Floor(key interface{}) *AVLNode

Return the largest node that is smaller than or equal to the given node.

func (*AVLTree) FromJSON

func (t *AVLTree) FromJSON(data []byte) error

FromJSON Convert to JSON format the elements

func (*AVLTree) Get

func (t *AVLTree) Get(key interface{}) interface{}

Get Value

func (*AVLTree) Height

func (t *AVLTree) Height() int

return AVL Tree Height

func (*AVLTree) HeightOfNode

func (t *AVLTree) HeightOfNode(key interface{}) int

Return the height of a specific node

func (*AVLTree) Insert

func (t *AVLTree) Insert(key interface{}, value interface{})

Insert New Node by Key

func (*AVLTree) IsEmpty

func (t *AVLTree) IsEmpty() bool

IsEmpty, true if tree doesnt have nodes

func (*AVLTree) IsSameAs

func (t *AVLTree) IsSameAs(otherTree *AVLTree) bool

Compare 2 AVLTree

func (*AVLTree) Iterator

func (t *AVLTree) Iterator() goutils.ReverseIteratorKey

Iterator returns a stateful iterator whose elements are key/value pairs.

func (*AVLTree) Keys

func (t *AVLTree) Keys() []interface{}

Keys returns all keys in-order

func (*AVLTree) LeafCount

func (t *AVLTree) LeafCount() int

Return number of Leaf

func (*AVLTree) Left

func (t *AVLTree) Left() *AVLNode

Return minimum element

func (*AVLTree) Mirror

func (t *AVLTree) Mirror()

Return avl mirror

func (*AVLTree) Parent

func (t *AVLTree) Parent(key interface{}) *AVLNode

Return the parent node of a specific value

func (*AVLTree) Print

func (t *AVLTree) Print()

Print the AVLTree

func (*AVLTree) PrintInOrder

func (t *AVLTree) PrintInOrder()

print inorder

func (*AVLTree) PrintPostOrder

func (t *AVLTree) PrintPostOrder()

print postorder

func (*AVLTree) PrintPreOrder

func (t *AVLTree) PrintPreOrder()

print preorder

func (*AVLTree) Remove

func (t *AVLTree) Remove(key interface{})

Remove Node by key

func (*AVLTree) Right

func (t *AVLTree) Right() *AVLNode

Return maximum element

func (*AVLTree) Search

func (t *AVLTree) Search(key interface{}) *AVLNode

Search Value, return the node

func (*AVLTree) Size

func (t *AVLTree) Size() int

Return Size of tree

func (*AVLTree) String

func (t *AVLTree) String() string

Print Tree with fmt.Print*

func (*AVLTree) SumNodes

func (t *AVLTree) SumNodes() interface{}

Return sum of all nodes

func (*AVLTree) ToJSON

func (t *AVLTree) ToJSON() ([]byte, error)

ToJSON return JSON format of elements

func (*AVLTree) Values

func (t *AVLTree) Values() []interface{}

Values returns all values in-order based on the key.

type Iterator

type Iterator struct {
	// contains filtered or unexported fields
}

Iterator

func (*Iterator) Begin

func (iterator *Iterator) Begin()

Set pointer to Begin state

func (*Iterator) End

func (iterator *Iterator) End()

Set pointer to last state

func (*Iterator) First

func (iterator *Iterator) First() bool

Moves to the first element

func (*Iterator) Key

func (iterator *Iterator) Key() interface{}

Return current Key

func (*Iterator) Last

func (iterator *Iterator) Last() bool

Moves to the Last element

func (*Iterator) Next

func (iterator *Iterator) Next() bool

Moves to the next element

func (*Iterator) Prev

func (iterator *Iterator) Prev() bool

Move to the Prev element

func (*Iterator) Value

func (iterator *Iterator) Value() interface{}

Return current value