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 r