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 & Nonlinear: which
means the data stored in a sequence
is called Linear, other is Nonlinear
(array is Linear & Tree is
nonlinear).
2. Homogeneous & Nonhomogeneous:
Which means the data structure,
which contains single type of
data, is known as Homogeneous
& other or different. Record
is a NonHomo.
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.
TREES:
A tree is a nonempty 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 subtrees,
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 subtree. 2tree 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: LeftRootRight.
2. Postorder: LeftRightRoot
3. Preorder: RootLeftRight,
It employs Depth First
Search.
4. Levelbylevel.
Binary Search Tree is an ordered
tree such that
Ø It is an empty tree
Ø Each data value in its
left subtree less than the root
value
Ø Each data value in its
right subtree is greater than
the root value.
Ø No value is duplicated
at level of the tree.
Ø Left & right subtrees
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 Multiway tree (MWAY).
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^L1, where L is the
level. There fore the number of
nodes from level 1 to level h1
will be
(2^h1) –1.
So, total number of nodes n of
the tree may range as (2^h1)
to (2^h) 1
Each node of AVL tree has the
property that the height of the
left subtree is, one more, equal
or one less than the height of
the right subtree. The factor
is
BF =height of
right subtree  height of left
subtree.
If the two subtree are at same
height BF=0
If right Subtree is higher BF=+1
If left subtree is higher BF=1
To balance the AVL tree keep
on rotating the nodes in clockwise
to have a balance tree.
A BTree is a balanced Mway
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 BTree.
1. The height of the tree must
be kept at minimal
2. There must be no empty subtrees
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.
Btree of Mway 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
M1 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.
Cont..
