AVL

Documentation

Overview

Package AVL implements the AVL (Adelson-Velskii and Landis) self-balancing binary search tree.

Index

• type Comparable
• type Node
  • func NewNode(v Comparable) *Node
  • func (b *Node) Find(v Comparable) (c, p *Node)
  • func (b *Node) Fix() (root *Node)
  • func (b *Node) HCalc()
  • func (b *Node) Insert(v Comparable) *Node
  • func (b *Node) LRot()
  • func (b *Node) Largest() Comparable
  • func (b *Node) RRot()
  • func (b *Node) RTraverse(f func(interface{}))
  • func (b *Node) Remove(v Comparable) *Node
  • func (b *Node) Smallest() Comparable
  • func (b *Node) Traverse(f func(interface{}))

Types

type Comparable

type Comparable interface {
	Equal(Comparable) bool
	Less(Comparable) bool
}

Any value type that satisifies AVL.Comparable interface can be managed by an AVL data structure

type Node

type Node struct {
	H int
	V Comparable
	// contains filtered or unexported fields
}

func NewNode

func NewNode(v Comparable) *Node

func (*Node) Find

func (b *Node) Find(v Comparable) (c, p *Node)

return node and parent returning a nil parent means it's the node itself

func (*Node) Fix

func (b *Node) Fix() (root *Node)

Fix the node imbalance going up the tree, return the new root

func (*Node) HCalc

func (b *Node) HCalc()

Calculate the height of the node

func (*Node) Insert

func (b *Node) Insert(v Comparable) *Node

Insert a node at the right place; return the new root.

func (*Node) LRot

func (b *Node) LRot()

Rotate b Left

func (*Node) Largest

func (b *Node) Largest() Comparable

return the largest value

func (*Node) RRot

func (b *Node) RRot()

Rotate b Right

func (*Node) RTraverse

func (b *Node) RTraverse(f func(interface{}))

Traverse the tree in descending order (as determined by Comparable.Less)

func (*Node) Remove

func (b *Node) Remove(v Comparable) *Node

Remove a node, rebalance and return the new root

func (*Node) Smallest

func (b *Node) Smallest() Comparable

return the smallest value

func (*Node) Traverse

func (b *Node) Traverse(f func(interface{}))

Traverse the tree in ascending order (as determined by to Comparable.Less)