Recursive Tree Traversals

Recursive functions are also commonly used to perform depth-first searches of a tree.  Consider a binary tree in which each node has a value and then pointers to its left and right children (left and right).  Then, consider the following code, which prints out the contents of a tree in a particular order:

void print_inorder(Node *T) {  
    if (T == nullptr)     
        return;        // base case  
  
    print(T->left);  
    cout << T->value << " ";  
    print(T->right);  
}
	

This tree traversal is known as an "inorder" traveral.  It first prints out the left subtree of the node pointed to by T (with the first recursive call).  Second, it prints out the value of the node pointed to by T.  Finally, it prints out the right subtree of the node pointed to by T (with the second recursive call).  This function is called an inorder traversal because, if the data is sorted as in a binary search tree (a topic we will cover soon), it prints the data out in order.

In addition to inorder traversals, there are also preorder and postorder traversals that are sometimes useful to perform.  These traversals differ in the order in which the node itself, the node's left subtree, and the node's right subtree are visited.  In the preorder travels, the node is visited (printed out) before either of its children.  In a postorder travels, a node is visited after visiting all of its posterity in both the left and right subtrees.  The following two snippets of code show these preorder and postorder traversals, respectively.

void print_preorder(Node *T) {  
    if (T == nullptr)     
        return;        // base case  
  
    cout << T->value << " ";  
    print(T->left);  
    print(T->right);  
}

void print_postorder(Node *T) {  
    if (T == nullptr)     
        return;        // base case  
  
    print(T->left);  
    print(T->right);  
    cout << T->value << " ";  
}

Ideally, you should be able to trace the code to determine what order the nodes values are printed out for each traversal.  It is worth studying it out to see how this code operates if you are having a hard time understanding it.

Binary Search Tree

The binary search tree property is extremely useful because it allows us to quickly locate a value, x, in a binary search tree. To do this we start searching for x at the root, r. When examining a node, u, there are four cases:

1. If u is null, the tree doesn't contain a node with a value of x, so we're done.
2. If x == u.x, then we have found the node u containing x, so we're done.
3. If x < u.x, then the search proceeds to u.left.
4. If x > u.x, then the search proceeds to u.right.

The C++ STL set class uses a Binary Search Tree as its underlying data structure to hold its values. So let's talk a bit about how efficient BSTs are at finding, inserting, and deleting nodes.

Finding & inserting:
Best case & average case: O(log(n))
Worst case: O(n)

AVL

Left-Left rotation

When you have a node with negative relative height balance and its left child also has negative balance, we call this a Left Left tree.  We can balance the tree shown in the previous question by rotating it right.  The rotation occurs through the following steps:

• let n be the node that is out of balance (50)
• let k be the left child of n (25)
• make the parent of n point to k instead of n (root points to 25 instead of 50)
• make n's left child pointer point to k's right child (50's left child points to b)
• make k's right child pointer point to n (25's right child points to 50)

Right-Right
When you have a node with positive balance (>1) and its right child also has positive balance, we call this a Right Right tree.  We can balance the tree by rotating it left.  The rotation occurs through the following steps:

• let n be the node that is out of balance
• let k be the right child of n
• make the parent of n point to k instead of n
• make n's right child pointer point to k's left child
• make k's left child pointer point to n

Big O for search, delete, insert: log(n)

Hash tables

O(1)

Hash Functions

Good hash functions are usually required to satisfy certain properties. The exact requirements are dependent on the application. The job of the hash function is to translate a value (data item) into an index. Ideally, every possible value that could exist in the hash table would generate a different index. In practice, that isn't possible. But the goal is to write a hash function that will take a value as input and return an index as output in such a way that the hash function typically returns different indexes for different input values.

Determinism

A hash procedure must be deterministic—meaning that for a given input value it must always generate the same hash index. There can be no element of "randomness" to it. If this is not the case, then a search will not be able to find the index where the value resides.

Uniformity

A good hash function should map the expected inputs as evenly as possible over its output range. That is, every hash value in the output range should be generated with roughly the same probability. The reason for this last requirement is that the cost of hashing-based methods goes up sharply as the number of collisions—pairs of inputs that are mapped to the same hash value—increases.

Defined range

It is often desirable that the output of a hash function have fixed size (but see below). If, for example, the output is constrained to 32-bit integer values, the hash values can be used to index into an array. Producing fixed-length output from variable length input can be accomplished by breaking the input data into chunks of specific size. Hash functions used for data searches use some arithmetic expression which iteratively processes chunks of the input (such as the characters in a string) to produce the hash value.

Efficiency

A hash function must be efficient. If a hash function takes longer to run when more values are in the hash table, then it is not efficient enough. A hash function must be O(1) with respect to the number of values in the hash table. Otherwise the insert, delete, and find functions cannot run in O(1) time.

Heaps

In order to add an item to a Min heap, you insert the item at the next available leaf (leftmost) and let the item percolate up to the correct position.  To percolate up, you first compare the item with its parent.  If the item is less than its parent, exchange the item with its parent. Let's look at the steps of inserting 1 into the following tree.

Removal

Binary Heaps are used to prioritize or sort items.  So removal usually occurs at the root (the smallest or largest value depending on whether it is a MIN or MAX heap).  When the root is removed, it is not easy to preserve the heap property while allowing the data to be stored in an array.  An O(logn) approach takes the last element added to the array and replaces the root with this item.

How do you Remove an item from a Heap?
1. replace the root with the last item added
2. percolate down until the order is correct

How do you percolate down?
1. compare an item with its smaller child (for a min heap, largest for a max heap)
2. swap if the parent is larger

A Heap is often used because it can be stored in a memory efficient way in an array.  This occurs because of the requirement that the heap be a complete binary tree except for the leaf layer where we fill from the left.

Using 0-based indexing,  the root is at A[0] the children of the root are at A[1] and A[2].  The next elements of the array will contain the next layer of the heap.

Given a node in the array at A[i]

• The left child of the node at i is at 2i+1 and the right child of the node at i is at 2i+2.
• The parent of the node at i is at (i-1)/2.

So, it is easy to find parents and children without needing pointers or complex data structures.

For example, the following heap

100
/ \
80 50
/ \ /
75 60 10 30
/
40

Could be represented in memory by

To add a node, you just put it in the next empty location (8).  To delete a node, you take the last element that was added (location 7), put that value in the root at index 0 and percolate that root to the correct place.

Given the following memory representation of a heap, what is the parent of the node at index 5?