Tree Data Structures and Priority Queues

Tree Data Structures

Tree is a collection of nodes. If the collection is empty the tree is empty otherwise it contains a distinct node called root (r) and zero or more sub-trees whose roots are directly connected to the node r by edges. The root of each tree is called child of r, and r the parent. Any node without a child is called leaf. We can also call the tree as a connected graph without a cycle. So there is a path from one node to any other nodes in the tree. The main concern with this data structure is due to the running time of most of the operation require O(logn). We can represent tree as an array or linked list.

Some of the definitions

Level h of a full tree has d^(h-1) nodes.

The first h levels of a full tree have 1 + d + d^2 + …………………….. d^(h-1) = (d^h -1)/(d-1)

Binary Search Trees

BST has at most two children for each parent. In BST a key at each vertex must be greater than all the keys held by its left descendents and smaller or equal than all the keys held by its right descendents. Searching and insertion both takes O(h) worst case time, where h is height of tree and the relation between height and number of nodes n is given by log n < h+1 <= n. for e.g. height of binary tree with 16 nodes may be anywhere between 4 and 15. When height is 4 and when height is 15? So if we are sure that the tree is height balanced then we can say that search and insertion has O(log n) run time otherwise we have to content with O(n).

AVL Trees

Balanced tree named after Adelson, Velskii and Landis. AVL trees consist of a special case in which the sub-trees of each node differ by at most 1 in their height. Due to insertion and deletion tree may become unbalanced, so rebalancing must be done by using left rotation, right rotation or double rotation.

Priority Queues

Priority queue is a queue in which the elements are prioritized. The least element in the priority queue is always removed first. Priority queues are used in many computing applications. For example, many operating systems used a scheduling algorithm where the next process executed is the one with the shortest execution time or the highest priority. Priority queues can be implemented by using arrays, linked list or special kind of tree (I.e. heap).

boolean isEmpty ();

Return true if and only if this priority queue is empty.

int size ();

Return the length of this priority queue.

int getLeast ();

Return the least element of this priority queue. If there are several least elements, return any of them.

void clear ();

Make this priority queue empty.

void add (int elem);

Add elem to this priority queue.

int delete();

Remove and return the least element from this priority queue. (If there are several least elements, remove the same element that would be returned by getLeast.