Binary Trees

Transcribed by John Jachna on 4/28/11

Visualization of a Binary Tree: upload.wikimedia.org/wikipedia/commons/f/f7/Binary_tree.svg

The top is called the Root Items that point to other nodes are Parents. The nodes a parent points to are called children.
A node may have 2, 1, or 0 children. If a node has no children, it is called a leaf.
The links connecting parents to children are called edges.
In a Binary Search Tree, the left value is always less than the right value.

Binary Trees are made up of structures containing a value and pointers to structures for left and right values:

typedef struct Node
{
int value;
struct Node *left, *right;
} Node;

            | Sorted Array | BST*
----------|--------------------|--------
insert | O(n) | Olog(n)
delete | O(n) | Olog(n)
search | Olog(n) | Olog(n)

• (if balanced)
  
  Recall that a constant ( O(1) ) is ideal. Olog(n) (logarithmic) is good, followed by O(n) (linear) and then O(n^2) (squared)

A node N in a Binary Search Tree:
- has two or less children
- N->value is greater than N->left
- N-> value is less than N->right

Node* Tree_insert(Node* root, Node* n)
{
if (root == NULL) return n;
if (n->value < root->value)
{
root->left = Tree_insert(root->right, n)
}
return root;
} Node* Tree_search(Node* root, int value)
{
if (root == NULL) return NULL;
if (root->value == value) return root;
if (root->value > value) return Tree_search(root->left, value);
else return Tree_search(root->right, value);
}

Deleting an element:
Case 1: element is a leaf => just delete the node
Case 2: element has one child => replace the node with its child
Case 3: element has two children =>
- Delete the node, then
- Replace with the biggest number in the left subtree (PREDECESSOR) or the smallest in the right subtree (SUCCESSOR)
- To find the largest value in a tree, go as far right as possible (go right until the right pointer is NULL)
- To find the smallest value in a tree, go as far left as possible