avl

avl is an implementation of avl binary search trees in Go

The underlying interface for types in avl is the Comparable interace. Any type can be used as long as it implements the following methods in the interface
   - Compare(other Comparable) int

Search, Insert, and Delete operations have O(lgn) run-time complexity. This is achieved by recognizing inbalances in subtrees after Insert and Delete operations and re-balancing the subtrees.

API

• type Comparable interface {
    Compare(other Comparable) int
  }

type Key Comparable

• type Tree struct
    root *Node

• type Node struct
    height int
    key Key
    left *Node
    right *Node

• TreeInit() *Tree
    Initializes the tree structure with a nil root.

• (t *Tree) Height() int
    Returns the height of the tree structure. This operation is constant since the root height is updated after each   operation.

• NodeHeight(n *Node) int
    Returns the height at a given node.

• (t *Tree) Search(k Key) bool
    Searches a given string in the tree. Returns true if found, false if not found.

• (t *Tree) Insert(k Key)
    Inserts a newly allocated node with the given val string into the tree.

• (t *Tree) Probe(k Key)
     Searches for an existing node with the given value and inserts it if the value was not found.

• (t *Tree) Delete(k Key) bool
    Deletes a node with the given query string if it exists in the tree. The method returns true if deletion was   successfull, otherwise false.

• (t *Tree) GetRootNode() *Node
    Returns the root node if it exists, otherwise nil.

• (n *Node) GetLeftChild() *Node   Returns the left child of a given node, nil if there is no left child.

• (n *Node) GetRightChild() *Node
    Returns the right child of a given node, nil if there is no right child.

• (n *Node) GetKey() Key
    Returns the key of the specified node.