Lab46 Wiki

A binary search tree can also be named as a sorted/ordered search tree. Its a tree that has nodes that stem off into small search trees. It uses a linked list (doubly) that goes left and right. Numbers are placed in the nodes throughout the tree and with the correct algorithm it can traversed through going least to greatest or vice versa. Generally the left tree will have values that are less then the root (starting node) and the right tree will have values greater. The first node is called the root and the final nodes (depending on where it ends) are considered the leaves of the trees since that are the last on the tree.

* http://en.wikipedia.org/wiki/Binary_search_tree

tree rebalancing

In computer science, a self-balancing (or height-balanced) binary search tree is any node-based binary search tree that automatically keeps its height (number of levels below the root) small in the face of arbitrary item insertions and deletions. These structures provide efficient implementations for mutable ordered lists, and can be used for other abstract data structures such as associative arrays, priority queues and sets.

List any sites, books, or sources utilized when researching information on this topic. (Remove any filler text).

* Reference 2:wikipedia.com

One example of a self-balancing tree is an AA tree. AA trees require O(log(N)) bits of metadata per node, in the form of an integer “level”. The following is an example of a function that this tree would use, split:

function split is
    input: T, a node representing an AA tree that needs to be rebalanced.
    output: Another node representing the rebalanced AA tree.
 
    if nil(T) then
        return Nil
    else if nil(right(T)) or  nil(right(right(T))) then
        return T
    else if level(T) == level(right(right(T))) then
        We have two horizontal right links.  Take the middle node, elevate it, and return it.
        R = right(T)
        right(T) := left(R)
        left(R) := T
        level(R) := level(R) + 1
        return R
    else
        return T
    end if
end function