Non Linear Data Structures PDF

Preview

Summary

This lecture notes covers Non linear data structures such as trees and it its types and how to find its height along with complexities....

Description

Non Linear Data Structures

Trees:

Trees are hierarchical data structures. The topmost node is called root of the tree. The elements that are directly under an element are called its children. The element directly connected above the node is called its parent.Elements with no children Are called leaves

Words used while talking about trees Ancestor : Parent or Parent of parent etc Descendant : Child or child of child etc Sibling : Sharing the same parent Leaf node : Node with no children Interior node : Non- leaf node. Have 1 or 2 children

Level : 1+ number of edges between root and node Height : Maximum depth of subtree node and farthest leaf Forest : Collection of trees

Why trees are needed and why are they known as important data structures? Storing information in hierarchy. File systems are represented in hierarchical order Trees (with some ordering e.g., BST) provide moderate access/search (quicker than Linked List and slower than arrays). Trees provide moderate insertion/deletion (quicker than Arrays and slower than Unordered Linked Lists). Like Linked Lists and unlike Arrays, Trees don’t have an upper limit on number of nodes as nodes are linked using pointers. Main applications of trees include:     

Manipulate hierarchical data. Make information easy to search Manipulate sorted lists of data. Router algorithms Form of a multi-stage decision-making

Binary Tree: A tree whose elements have at most 2 children is called a binary tree. A tree is represented by a pointer to the topmost node in tree. If the tree is empty, then value of root is NULL. A Tree node contains following parts. 1. Data 2. Pointer to left child 3. Pointer to right child

The maximum number of nodes at level ‘l’ of a binary tree is 2l-1. Maximum number of nodes in a binary tree of height ‘h’ is 2h – 1. In a Binary Tree with N nodes, minimum possible height or minimum number of levels is Log2(N+1) A Binary Tree with L leaves has at least ⌈ Log2L ⌉ + 1 levels In Binary tree, number of leaf nodes is always one more than nodes with two children

Complete Binary Tree: A Binary Tree is Complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible Perfect Binary Tree A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at same level. Balanced Binary Tree : A binary tree is balanced if height of the tree is O(Log n) where n is number of nodes. For Example, AVL tree maintain O(Log n) height by making sure that the difference between heights of left and right subtrees is 1.

Tree traversal: A traversal is a process that visits all the nodes in the tree. Since a tree is a nonlinear data structure, there is no unique traversal. We will consider several traversal algorithms with we group in the following two kinds  

depth-first traversal breadth-first traversal

There are three different types of depth-first traversals, : PreOrder traversal - visit the parent first and then left and right children; InOrder traversal - visit the left child, then the parent and the right child; PostOrder traversal - visit left child, then the right child and then the parent; There is only one kind of breadth-first traversal--the level order traversal. This traversal visits nodes by levels from top to bottom and from left to right....