Data Structures and Trees

Data structures.

The organized collection of data is known as Data Structure

Data structure = Organized data + Allowed operations

Data type = permitted Data Values + Operations.

Simple Data structure can be used as building blocks of complex data structure, Array is type of Data structure using which we can build more complex data structure. Data structure can be classified in to two different types according to three types.

1. Linear & Non-linear: which means the data stored in a sequence is called Linear, other is Non-linear (array is Linear & Tree is non-linear).

2. Homogeneous & Non-homogeneous: Which means the data structure, which contains single type of data, is known as Homogeneous & other or different. Record is a Non-Homo.

3. Static & Dynamic: This is means the allocation of memory, either static or Dynamic.:

Array is a finite, ordered set of homogeneous elements stored in a contiguous memory location.

Arrays can be traversed either in Row major or Column Major order.

A Sparse array is which contains a relatively number of Zero elements.

List is a Linear data structure which contains the Homogeneous data objects. The first element in a list is called “head” and last element is known as “tail”. The element next to head is called successor and element previous to tail is known as predecessor.

Storage Allocation is done with First Fit or Best Fit method.

Storage Pools are

1. Bit tables

2. Table of contents

3. Linked Allocation.

A tree is a non-empty collection of vertices & edges that satisfies certain requirements. A vertex is a simple object (node) that can have a name and carry other associated information. An edge is a connection between two vertices.

A Tree is a finite set of a zero or more vertices such that there is one specially designated vertex called Root and the remaining vertices are partitioned into a collection of sub-trees, each of which is also a tree. A node may not have children, such node is known as Leaf (terminal node). The line from parent to a child is called a branch or an edge. Children to same parent are called siblings.

A path in a tree a list of distinct vertices in which successive vertices are connected by edges in the tree. There is exactly one path between the root and the other nodes in tree.

A Length is a path is a number of ranches on the path, in path from m to n, m is a ancestor of n & n is descendent of m.

A Depth of any node m is the length of the path from root to m. Thus root is always at 0 depth. The Height of a node m is the longest path from m to leaf. Thus all leaves ate at heght zero. Sometime Depth is referred as level of the tree from root.

A set of tree is called forest.

A Binary Tree is tree which either empty or consists of a root node & two disjoint trees called left & right sub-tree. 2-tree or strict binary tree, is a binary tree, which either contains no children or two disjoint children.

A binary tree can be implemented by a simple linked list. The number of nodes at level I is 2^I. Therefore for a complete binary tree with K levels contains k

E 2^I

I=0.

A binary tree can be traversed using four different algorithms

1. Inorder: Left-Root-Right.

2. Post-order: Left-Right-Root

3. Pre-order: Root-Left-Right, It employs Depth First Search.

4. Level-by-level.

Binary Search Tree is an ordered tree such that

•  It is an empty tree
•  Each data value in its left sub-tree less than the root value
•  Each data value in its right sub-tree is greater than the root value.
•  No value is duplicated at level of the tree.
•  Left & right sub-trees are again binary search trees.

While deleting a node from a tree..

1. If node is a leaf.

2. If node is having one child

3. If node is having children.

A tree which is having a two values in its node & can have max of three branches, one values lesser than node value, second value in between of two values in node & lastly value grater than the values in node. Such type of tree is known as Multi-way tree (M-WAY).

An almost height balanced tree is known as AVL tree. Each subsequent levels will be as full as possible i.e. 2 nodes at level 2.4 nodes at level 3 and so on. In general there will be 2^L-1, where L is the level. There fore the number of nodes from level 1 to level h-1 will be

(2^h-1) –1.

So, total number of nodes n of the tree may range as (2^h-1) to (2^h) -1

Each node of AVL tree has the property that the height of the left sub-tree is, one more, equal or one less than the height of the right sub-tree. The factor is

BF =height of right sub-tree -- height of left sub-tree.

If the two sub-tree are at same height BF=0

If right Sub-tree is higher BF=+1

If left sub-tree is higher BF=-1

To balance the AVL tree keep on rotating the nodes in clockwise to have a balance tree.

A B-Tree is a balanced M-way tree. It’s also known as balanced sort tree. It finds its use in external sorting. It’s not a Binary Tree.

Conditions to be a B-Tree.

1. The height of the tree must be kept at minimal

2. There must be no empty sub-trees above the leaves of the tree.

3. The leaves of the tree must all be on the same level

4. All nodes except the leaves must have at least some minimum number of children.

B-tree of M-way properties.

1. Each node has a max of M children and a min of M/2 children or any number from 2 to max.

2. Each node has one fewer keys than children with maximum of M-1 keys.

3. Keys are arranged in a defined order within the node. All keys in the subtree to the left of a key are predecessors of the key & that on the right is successors of the key.

4. When a new key is to be inserted into a full node, the node is split into two nodes and the key with the median value is inserted in parent node. In case the parent node is the root, a new root is created.

5. All leaves are on the same level i.e. there is no empty subtree above the level of the levels.