CS131: Tree

A tree is a collection of nodes and edges. Edges connects the edges together. In a tree there is one and only one path between any two nodes.

Fig: A tree - here we have A,B,C,D,E,F nodes and l,m,n,o,p, edges.

In a tree we define a path using connected sequence of edges. Number of edges on the path is called the length of the path. In above figure from B to F there is exactly one path and that is (m,n,p).

Rooted tree

In a tree we can pick a node and call it to be the root of the tree. We call this tree to be a rooted tree.

We choose C to be the root and we redraw the tree to keeping the root on top and others in different level based on distance from the root.

Fig1: Original tree Fig2: Redrawn tree

If we look carefully we see that nothing has changed for the tree but we have chosen C to be root and placed the nodes differently on paper. We draw the like figure 2 for convenience of understanding levels and relations.

If we choose any node and find a path from that node to the root the first node we encounter is called the parent of that node. All node except the root has exactly one parent. Root has no parent.

On the path fopm node F to root node C we encounter D first. So D is the parent of F and F is called to be child of D. A node may have any number of children including zero child. A node without any child is called a leaf node. A,F,E are leaf nodes.

All the nodes on the path to root including F itself and the root is called to be ancestor of F. So F's ancestors are F,D and C and F is called to be their descendents.

Length of the path from an node to the root is the depth of that node. Depth of F is 2. Length of path from a node to its deepest descendent is the height of the node. height of D is 1 nad height of root C is 2. Height of the root is also height of the tree. So the tree has a height of 2.

Nodes having same parent is called to be siblings. B and D are siblings. Similarly E and F are siblings.

Binary tree

A binary tree is a special type of three where no node is allowed to have more than two children.

Fig: Binary tree - a node may hav zero, one or two children.

Each child of a node is either left child or a right child. Even there is only one child that child must be either left child or a right chi

Representing rooted tree in memory

-----------------------
|  data   | Parent ref|
-----------------------
|Children list        |
-----------------------

Fig:

-----------------------------
|  data   |     Parent ref  |
-----------------------------
|First child | Next sibling |
-----------------------------

Fig:

Traversal

The process of visiting each node in a tree once is called traversal. Depending on the order of visiting nodes in a tree we ma traverse in a few different ways:

• Pre-order traversal
• Post-order traversal
• Binary tree inorder traversal
• Level order traversal

We will discuss them in details.

Preorder traversal

We visit each node starting from root and then recursively visit its children from left to right.

Preorder(node):
    Visit(node)
    for each child c of node
        Preorder(c)

Fig: Preorder traversal - numbers show the order of nodes getting visited

Postorder traversal

We visit each node's children left to right and then visit the node itself.

Preorder(node):    
    for each child c of node
        Preorder(c)
    Visit(node)

Fig: Postorder traversal

Binary tree inorder traversal

We visit left child then the node itself and then right chhild.

Inorder(node)
    if node.left exists
        Inorder(node.left)

    Visit(node)

    if node.right exists
        Inorder(node.right)

Fig: Inorder traversal

Level order traversal

We visit each level of the tree left to right before visiting any deeper level.

Fig: Level order traversal

We use a queue to keep track of the visited nodes children.

LevelOrder(tree)
   Q = new empty Queue
   Q.enque(tree.root)

   while Q is not empty
       node = Q.deque()
       Visit(node)
       for each child c of node from left to right
           Q.enqueue(c)

CS131: Disjoint Set

Disjoint set is a collection of sets that allows one key to be present only in one set.

All possible items that can be a member of a set is called "Universe of items".

Collection of disjoint sets are called partition.

Each set has a unique identifier that identifies the set.

Operations

We can perfoorm Union and Find operations on disjoint sets.

Union - Merges two sets into one set.

Find- It takes an item as parameter and returns its set.

Here is an example of a series of union and find operations:

[a], [b], [c], [d], [e], [f]

find(b) => b

union(a, b)
union(c,d)
union(e,f)

[a, b], [c, d], [e, f]

find(b) => a

union(a,c)

[a, b, c, d], [e, f]

find(d) => a

Disjoint sets can be implemented using list or using.

List based disjoint set and Quick find algorithm

Each set references list of items in the set and each item references the set that contains the item.

Fig: List based disjoint set and union operation

Running time

Find takes O(1) time but union is slow since it requires to reset set reference to all the items in one set which takes O(n) time.

Tree based disjoint set and Quick union algorithm

Each set is maintained as a tree. Therefore the data structure is a forest. Child or sibling reference is not maintained. So union operation can be performed in constant time by just setting one set's tree root to be parent of another set's tree root. The identity of the set is maintained at the root item. The root also maintains the size of the set to keep the depth of the tree lower while doing union operation.

Union operation

We make one set's root to be the child of other set's root.

If we have for items a, b,c and d each item is initially root of its own tree.

(a) (b) (c)  (d)

Union(a,b)

  (a)   (c)  (d)
 /
(b)

Union(a,c)

  (a)   (d)
 /   \
(b)  (c)

Union(a,d)

   (a)
 /  \ \
(b)(c)(d)

Union by size

Form above illustration note that (d) is made a child of (a). This is because (a) is a larger tree than (d) and this keeps the tree depth lower than if we make (a) to be child of (d). This way we get a tree with height n when we union two trees with at least (n-1) nodes each. We are able to double the number of nodes in the tree by increasing tree depth by one.

public class Node
{
    Node parent;
    int size;
}

public class DisjointSet
{
Dictionary<object, Node> set;

public void union(Node item1, Node item2)
{
    if(item1.size > item2.size)
    {
        item2.parent = item1;
        item1.size += item2.size;
    }
    else
    {
        item1.parent = item2;
        item2.size += item1.size;
    }
}
}

Find operation

For a given key we find the root of the tree which contains the key. We follow the parent reference until we reach the root node.

public Node find(Node node)
{
    if(node.parent == null)
    {
        return node;
    }
    else
    {
        Node parent_node = find(node.parent);
        node.parent = parent_node;
        return parent_node;
    }
}

Running time

Union is fast and takes O(1) time. Find is slower but it depends on the depth of the tree which grows slowly and is bound by the total number of unions. Also when we use path compression the node height is shorten on first find operation making consecutive find very fast. This way quick union algorithm based on a tree will be faster overall for any sequence of union and find operation.

CS131: Hash Tables

A hash table (also called map or dictionary) is an abstract collection of items where any data item can be stored and accessed with an associated key. Both data and key can be of any type.

The word hash is used as a term for transformation of a given key.

Direct address tables

If total number of possible items are reasonably small we may use direct address table where key is the index of the data array. Array is a direct address table.

Search()

Insert()

Delete()

Hash function

When direct address table is not a feasible option, for example when possible keys are too big, we use a function that takes the key k and return the index i of the table.

        i = h(k)   [ 0 <= i <= M - where M is total number of buckets in the table]

If the possible number of keys are bigger than available buckets in the hash table two keys may map the same index. This situation is called collision.

Let us consider the following keys

5, 13, 15, 17, 21, 24

We define the hash function as

    h(k) = k mod M

                  5  13
+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+

Fig: The mapping of the keys for M=7

Now for the first five keys (5, 13, 15, 17, 21) we can put the keys in the hash table buckets without any problem. But if we try to insert 24 we find 24 mod 7 = 3 and we have already 17 mapped to the 3rd bucket. We will look at a few techniques to solve the problem.

It is possible to create a very big hash table to minimize the number of collision. But we will be wasting a lot of memory if the table is mostly empty. So we want the average number of elements per bucket, which is called load factor, to be larger.

Load factor = n/M

The bigger the load factor the less wasted space.

Choosing a hash method

A good hash function should minimize collision, be easy to compute and distribute keys evenly through the available buckets.

The division method

h(k) = k mod M

For a good choice of M take a prime number that is distant from the values those are power of 2.

If M = 2^p the function will map two keys with same last character/digit to the same bucket [verify]

If M = 2^p-1 the function maps keys with same set of characters / digits to the same bucket. [verify]

The multiplication method

For all k h(k) = floor(M(kA-(floor(kA)) - where A is a constant with value range from 0 to 1. The value of M is not critical here.

Collision resolution by chaining

When two keys maps to same index we can use a linked list for that key to store multiple values. If there are M buckets we can maintain M linked list each of which may contain zero or more items.

Head(1) [*]-->[Value 1 | * ]-->[Value 2 | $ ]
Head(2) [*]-->[Value 3 | $ ]
Head(3) [*]-->[Value 5 | * ]-->[Value 6 | * ]-->[Value 7 | $ ]
Head(4) [$]
Head(5) [*]-->[Value 8 | $ ]

Fig: Using linked list for collision resolution

I <-- H(k) +1   [1 <= I <= M]
If I is present in HashTable 
    Do
        If k = KEY[I] return I        
        I = Link[I]
    While (I != 0)

Open addressing with Linear probing and insertion

Open addressing with Double hashing

Deletion

We can not simply delete a key from hash table since there could be more than one keys that hashed to the same bucket.

Deletion with linear probing

Universal hashing

For any hash function it is possible that someone will be able to come up with a set of keys such that every key maps to the same bucket or a set of very small number of buckets making the hash table a linked list and accessing any item will take O(n) time instead of expected O(1) time.

To solve this problem we can define a set of different hash functions and pick one function randomly when we initialize the hash table before first use. This technique is called universal hashing and operation on any element is expected to take O(1) average time.

Once chosen the hash function is not changed for the lifetime of the hash table so that each key hashed to the same bucket.

Linear Hashing

The hash table grows or shrinks as items are inserted or deleted from the hash table. It is not related to linear probing.

If N is initially chooses as number of buckets the number of total bucket of the hash table is chosen as 2N, 4N, 8N, 16N etc. that is, power of 2 * N. The power used is called level. So total number of bucket is 2^level * N. Level 2 has 4N buckets.

Linear hashing is implemented using dynamic array, a variable size array that allows random access of keys. When the size of array is changed

Extendible Hashing

Growing the size of hash table requires rehashing the keys and could be big performance hit when it is done. To avoid this situation, extendible hashing technique uses a trie as a hierarchical storage so that the rehashing can be done incrementally, one bucket at a time, as the hash table grows.

CS131: Prioryty Queue

A priority queue is a data structure that stores a set of entries where each entry has an associated key and total order of the keys are maintained.

Prioroty key can be either min priority queue which maintains keys in increasing order or max priority queue which maintains keys in decreasing order. In this chapter we will use min priority queue.

Priority queue can identify and remove the smallest key very fast and an item can be inserted at any time.

Operations:

Priority queue supports following operations:

Insert - which inserts item into the priority queue Min - which returns the item with smallest key RemoveMin - which removes the item with smallest key and returns it

Here is a few example of the operations:

[ | | | | | ]

Insert(4)

[4| | | | | ]

Insert(8)

[4|8| | | | ]

Insert(2)

[2|4|8| | | ]

Min() -> returns 2 and the priority queue is unchanged

[2|4|8| | | ]

RemoveMin() -> returns 2 and remove it from the priority queue

[4|8| | | | ]

Priority tree can be implemented using a Binary Heap.

Complete Binary Tree A binary tree in which every level of the three is full except the bottom row- which is filled from left to right. A complete binary tree has 1+log(n) levels where n is the number of items.

Fig: Complete Binary Tree

Binary heap

A binary heap is a complete binary tree where entries must satisfy heap order property, that is, no child element has a key less than its parents key. Multiple copies of same keys are allowed.

                (1)
             /       \
         /               \
      (3)                 (4) 
     /   \               /   \
   /       \           /       \
  (9)       (11)      (12)      (17)
 /   \     /   \     /
(13) (14) (15) (16) (12)

          Fig: Binary heap

Storing binary heap in a array

We do a level order traversal and on each level we traverse from left to right and store the keys sequentially in an array. If we do this for the binary heap from above figure we get following array.

[x|1|3|4|9|11|12|17|13|14|15|16|12|---]

Notice that we have kept the first cell unused.

In the array any item i's children is located at 2i and 2i+1 indexes and item i's parent is located at index |i/2|

For example item at index 4 is 9. Its children are 8th ad 9th item and the keys are 13 and 14. Its parent is at 2nd index which is 3. From the above binary heap tree figure you may verify that these are correct keys.

Operations

Min():
Return the entry at the root. In the array the root is stored at index 1. 
This is a constant time operation.

Insert(k):
1. Place k at the first open position on the bottom level from left. In the array 
   put k at the first empty space at the end of existing item.
2. Bubble up the element untill the heap order property is satisfied.
        If the parent key is bigger than the items key swap the item with its 
        parent and repeat this process as long as parent's key is bigger or the item is at the root.

Fig: Insert example

RemoveMin():
    1. Remove the entry at root
    2. Take the last entry from bottom level of  the tree feom left and put it at root 
       position. In array this is the last item.
    3. Bubble the root entry down through the heap-
         until the items key is smaller than both of its children's key swap with smaller child 

Fig: Remove example

Worst case performsnce Theta(log n) Best case performance Theta(1)

Bottom up heap construction

If we are given an array of items and we need to create a heap, we can insert each item in the tree one by one which will take Theta(n log n) time or we can use bottom up heap construction technique to do it in Theta(n)

BottomUpHesp(itemArray): [ref:]
1. Make a complete binary tree without considering order. For a given array of 
items no operation is required. 
2. For each nonleaf node starting from last one bubble the item 
down (swap with smaller child) until its key both of its children's key.

Fig: Bottom up heap construction example

CS131: Queue

Que is a linear list data structure. The insert and remove operations are performed at the opposite ends of the list which are called the rear and the front respectively.

enqueue   ---->   |  3 |  4 |  2 |  <------ dequeue
              rear              front

Fig: Queue showing rear and front

A que can be implemented using a circular array or a linked list that maintains the rear and front item reference.

enqueue   -----+                       +------ dequeue
               |                       |    
               v  rear           front v
     +---->  |  |  3 |  4 |  2 | 7 | 10 |  |  | >-----+
     |                                                |
     +------------------------------------------------+

Fig: Circular list implementation using array

enqueue   -----+                       +------ dequeue
               |                       |    
               v  rear           front v
   [head]---> [3|*]-->[4|*]-->[2|*]-->[9|*]--->$

Fig: Linked list implementation

Operations

    public interface Queue
    {
        /// <summary>
        /// Inserts an item to the rear of the list of items.
        /// </summary>
        /// <param name="item">item to be inserted</param>
        void enqueue(object item);

        /// <summary>
        /// Removes an item from the front of the list of items and returns it.
        /// </summary>
        /// <returns>The removed item</returns>
        object dequeue();

        /// <summary>
        /// Returns the item in front of the list of items. The list is not altered in any way.
        /// </summary>
        /// <returns>The item at the front of the queue</returns>
        object front();

        /// <summary>
        /// Check if the queue is empty or not
        /// </summary>
        /// <returns>true if queue is empty, false otherwise</returns>
        bool empty();

        /// <summary>
        /// Checks if the queue is full or not
        /// </summary>
        /// <returns>true if queue is full, false otherwise</returns>
        bool full();

        /// <summary>
        /// Calculates the number of items in the queue
        /// </summary>
        /// <returns>Number of items in teh queue</returns>
        int size();
    }

Implementation

    public class Node
    {
        public Node next, previous;
        public object data;
    }


    public class LinkedListQueue : Queue
    {
        Node rear_item, front_item;
        int item_count;

        public LinkedListQueue()
        {
            rear_item = front_item = null;
            item_count = 0;
        }

        public void enqueue(object data)
        {
            SNode new_item = new SNode();
            new_item.data = data;
            new_item.next = null;
            new_item.previous = front_item;

            if (front_item != null)
            {
                front_item.next = new_item;
            }

            front_item = new_item;

            if (item_count == 0)
            {
                rear_item = new_item;
            }

            item_count++;
        }

        public object dequeue()
        {
            if (front_item == null)
            {
                return null;
            }

            object data = front_item.data;

            item_count--;

            if (item_count == 0)
            {
                rear_item = null;
                front_item = null;
            }
            else
            {
                front_item = front_item.previous;
                front_item.next = null;
            }

            return data;
        }

        public object front()
        {
            if (front_item == null)
            {
                return null;
            }

            return front_item.data;
        }

        public bool empty()
        {
            return (item_count == 0);
        }

        public bool full()
        {
            return false;
        }

        public int size()
        {
            return item_count;
        }

        public static void Test()
        {
            Queue queue = new LinkedListQueue();
            object data = 10;
            queue.enqueue(data);
            object item = queue.dequeue();
            TestEngine.AssertEquals(item, data, "Dequeue does not return expected data");
        }
    }    

Deque

A double ended queue where insertion and deletion are allowed on both end of the list.

Problem: Implement a deque

CS131: Stack

Stack is linear list data structure which allows all operations at one end of the list. The operations are usually performed at one end called the top. The top item is inserted last. Any other item that is not at the top of the stack is not allowed to be accessed. Since we can access last item inserted in the list first stack is called to be a Last In First Out (LIFO) data structure.

Fig: Stack with top, insert and remove positions

Stack supports three operations- push, pop and top

Push operation

Inserts an item on top of the stack.

push(item)
    if top >= max items allowed  //overflow
        throw error
    stack[top]=data
    top=top+1

Pop operation

Removes the item at the top from the stack and returns it.

Pop()
    if top<0
        throw error

    item= stack[top]
    top=top-1
    return item

Top operation

Returns the item at top of the stack

Top()
    if top<0
        throw error  //underflow
    return stack[top]

Stack operation example

Start with an empty stack

[    |    |     |    |     |    |     ]  top=-1

Push(15)

[ 15 |    |     |    |     |    |     ] top = 0

Push(18)

[ 15 | 18 |     |    |     |    |     ] top = 1

Push(3)

[ 15 | 18 |  3  |    |     |    |     ] top = 2

Pop() ---> returns 3

[ 15 | 18 |     |    |     |    |     ] top = 1

Overflow and underflow

Stack usually has an upper limit of number of items that can be inserted before we run out of memory. If we try to push an item on the stack when stack is full and no more memory can be allocated an error condition is occured. This condition is known as overflow.

Another error condition occured when the stack is empty and pop() method is called. This is called underflow.

Fixed and Dynamic stack

Stack can be implemented such that maximum amount of memory that can be used is allocated when stack in created nad this amount is fixed. This type of implementation may use a fixed array.

Another implementation may allocate memory dynamically as the stack grows and overflow occurs only when the application can no longer allocate more memory. When items are popped from the stack the extra memory may be released. This type of application may use a linked list that grows and shrinks dynamically.

CS131: Linked List

A linked list is a linear data structure where each element keeps a pointer to track elements in linear order. If the foirst element of the list is accessible, it is possible to access any element of the list. Each element of the list is called to a node which stores data and reference to next node of the list.
We use a special node marked as head to reference the first node of the list.
In a singly linked list each node stores data and keeps reference to the next node. First node is referenced by head and last node does not have a next node reference.

[head|o]--->[data1|o]--->[data2|o]--->[data3|o]--->%

Fig: A singly linked list
I a doubly linked list each node stores data and keeps reference to the previous node and the next node. First node does not have a previous node reference and last node does not have a next node reference.

[head|o]--->[o|data1|o]--->[o|data2|o]--->[o|data3|o]--->%
             |     ^        |    ^         |
       %<----+     +--------+    +---------+

Fig: A doubly linked list
A circular list is similar to singly where each nor keeps reference to the next node adn the last node references the first node as its next node reference. Head points to the first item which can be any item in the list because of the circular nature of the list.

[head|o]--->[data1|o]--->[data2|o]--->[data3|o]---+
              ^                                   |
              |                                   |
              +-------------[o|data4]<------------+

Fig: A circular linked list

Representing linked list

class SNode
{  
    object data;
    SNode next;
};

class SNode
{  
    object data;
    SNode next, prev;
};

class SList
{      
    SNode head;
    int itemCount;
};

class DList
{      
    DNode head;
    int itemCount;
};

Insert Operation

We want to insert a node at the front of the list

void insert(SList list, object data)
{
    SNode node = new SNode();
    node.data = data;
    node.next = list.head;
    list.head = node;
}

Quiz: Hou would ypu modify the list or the insert method to insert an item at the end of the list in O(1) time.
Quiz: How would you implement a stack using a linked list
Problem: Implement a doubly linked list
Problem: Implement a circular list

Find operation

Given a data value we need to find the node that stores that data. We the head item to get first item in the list and follow the next reference to find the item with given data or we reach the end of the list.

SNode find(SList list, object data)
{
    SNode cur = list.head;
    while(cur != null && !cur.data.equals(data))
    {
        cur = cur.next;
    }
    return cur;
}

Since there is no way to find a middle item of the list directly, find takes O(n) time even for a sorted list.

Delete operation

Let us consider the following list:

[head|o]--->[  5 |o]--->[  9 |o]--->[  6 |o]--->[ 13 |o]--->%

If we want to delete the element with data 9 the list will be like this after deletion:

[head|o]--->[  5 |o]--->[  6 |o]--->[ 13 |o]--->%

One way to do this is by finding previous element in the list and then delete the item and copying the next reference from the node we are deleting. This will take O(n) time. If the node is not last node in the list we can do it in O(1) time by copying the data and next reference from the next node and then deleting the next node.

[head|o]--->[  5 |o]--->[  6 |o]-X->[  6 |o]--->[ 13 |o]--->%
                            |       delete        ^
                            +---------------------+

void delete(SList list, SNode node)
{
    if(node.next != null)
    {
        node.data=node.next.data;
        node.next = node.next.next;
    }
    else
    {
        SNode cur = list.head;

        if(cur == node)
            list.head=null;

        while(cur.next != node)
        {
            cur = cur.next;
        }
        cur.next = node.next;                
    }
}

Most of the time the delete operation will complete in constant time. But for the last node it'll take O(n) time. To avoid the situation we can use a specual node called sentinel node to mark the end of the list. So, if we need to delete the last node of the list we just mark the last node as sentinel node.
Problem: Implement the list that uses a sentinel node to mark end of list and rewrite the delete operation by using sentinel node so that it always completes in constant time.