Data Structure

Unit-3

Lectuer-1

Tree

Lecture-2

Types of Tree

Lecture-3

Traversing of Binary Tree -1

Lecture-5

Traversing of Binary Tree -2

Lecture-6

Binary Search Tree

Lecture-7

Lecture-8

Lecture-9

Lecture-10

UNIT – 3

Unit-03/Lecture-01

Trees:[RGPV/Dec2014/(2)]

A tree is a Non-Linear Data Structure which consists of set of nodes called vertices and set of edges which links vertices.

· A tree is a data structure that is made of nodes and pointers, much like a linked list. The difference between them lies in how they are organized:

In a linked list each node is connected to one “successor” node (via next pointer), that is, it is linear.

In a tree, the nodes can have several next pointers and thus are not linear.

· The top node in the tree is called the root and all other nodes branch off from this one.

· Every node in the tree can have some number of children. Each child node can in turn be the parent node to its children and so on.

Basic Terminology: BACK

Root Node: The starting node of a tree is called Root node of that tree
Terminal Nodes: The node which has no children is said to be terminal node or leaf
Nodes.
Non-Terminal Node: The nodes which have children is said to be Non-Terminal Nodes
Degree: The degree of a node is number of sub trees of that node
Depth: The length of largest path from root to terminals is said to be depth or height of the tree
Siblings: The children of same parent are said to be siblings
Ancestors: The ancestors of a node are all the nodes along the path from the root to the node

High Calorific value - The calorific intensity of fuel should be high enough to melt the

Metal. BACK

5. Efficiency – Fuels on burning should not pollute the environment with any toxic gases as Combustion products.

6. Low storage cost - Storage cost in bulk should be low.

Fig-3.1 .1Tree

Binary Tree:[RGPV/June2014] BACK

Binary trees are special class of trees in which max degree for each node is 2

Recursive definition:

A binary tree is a finite set of nodes that is either empty or consists of a root and two disjoint binary trees called the left subtree and the right subtree.

Any tree can be transformed into binary tree. By left child-right sibling representation.

Fig 3.1.2

BACK

· A common example of a tree structure is the binary tree.

Definition of binary tree: A binary tree is a tree that is limited such that each node has only two children.

Examples: Fig-3.1.3

· The following are NOT binary trees:

Fig-3.1.4 BACK

Property of Binary Tree: [RGPV/Dec2012 (7)]

· If n1 is the root of a binary tree and n2 is the root of its left or right tree, then n1 is the parent of n2 and n2 is the left or right child of n1.

· A node that has no children is called a leaf.

· The nodes are siblings if they are left and right children of the same parent.

· The level of a node in a binary tree:

The root of the tree has level 0

The level of any other node in the tree is one more than the level of its parent.

Fig-3.1.5

S.NO	RGPV QUESTIONS	Year	Marks
Q.1	Prove that a binary tree with k internal nodes have (k+1) external nodes.	Dec 2012	7
Q.2	Define tree .prove that a binary tree with n nodes has exactly(n-1)edges or branches.	Dec 2014	2

Unit-03/Lecture-02

Types of Tree

Complete Binary Tree:[RGPV/June 2014/(2)]

A binary tree is said to be complete if all its level except possibly the last, have maximum number of possible nodes, and if all the nodes at the last level appear as far left as possible.

Full binary tree:

A binary tree said to be full if all its level have maximum number of possible node.

Extended Binary Tree (Strictly Binary Tree or 2-tree):

A binary tree is said to be Extended binary tree if each node has either 0 or 2 children. In this case the leaf nodes are called external nodes and the nodes with two children are called internal nodes.

BACK

Representation of Algebraic Expressions : Fig-3.2.1

Algebraic expressions such as

a/b+(c-d)e

have an inherent tree-like structure. Above example is a representation of the expression in Equation . This kind of tree is called an expression tree .

The terminal nodes (leaves) of an expression tree are the variables or constants in the expression (a, b, c, d, and e). The non-terminal nodes of an expression tree are the operators (+, -, , and ). Notice that the parentheses which appear in Equation do not appear in the tree. Nevertheless, the tree representation has captured the intent of the parentheses since the subtraction is lower in the tree than the multiplication.

BACK
Figure: 3.2.2 Tree representing the expression a/b+(c-d)e.

The common algebraic operators are either unary or binary. For example, addition, subtraction, multiplication, and division are all binary operations and negation is a unary operation. Therefore, the non-terminal nodes of the corresponding expression trees have either one or two non-empty sub trees. That is, expression trees are usually binary trees.

What can we do with an expression tree? Perhaps the simplest thing to do is to print the expression represented by the tree. Notice that an in order traversal of the tree in Figure visits the nodes in the order

Except for the missing parentheses, this is precisely the order in which the symbols appear in Equation ! BACK

This suggests that an inorder traversal should be used to print the expression. Consider an inorder traversal which, when it encounters a terminal node simply prints it out; and when it encounters a non-terminal node, does the following:

Print a left parenthesis; and then
traverse the left subtree; and then
print the root; and then
traverse the right subtree; and then
print a right parenthesis.

which, despite the redundant parentheses, represents exactly the same expression as Equation

Expression trees are useful as a vehicle for discussing the traversal of a tree.

An expression tree is a binary tree which is used to represent a mathematical expression. For example, if we have the expression (2 * (4 + (5 + 3))), we could construct a tree to represent it.

In an expression tree, the parent nodes are the operators, and the children are the operands. To find the result of this expression, we need to first solve (5 + 3), which is 8, then solve (4 + 8), which is 12, and then finally solve 2 * 12, which is 24. So our root node will contain the operator within the outermost set of parentheses, its left child will be the value "2", and the right child will be the remaining expression that needs to be solved, which would be (4 + (5 + 3)).

BACK exprtree3 Fig-3.2.3

When we talked about solving expressions using stacks, we had three different ways we could represent an expression:

Infix, where the operator comes between its two operands
Prefix, where the operator comes before its two operands
Postfix, where the operator comes after its two operands

Given an expression tree, we can generate any of the three representations using one of the three traversals of a binary tree: in-order, pre-order, and post-order.

S.NO	RGPV QUESTIONS	Year	Marks
Q.1	Prove that a binary tree with k internal nodes have (k+1) external nodes.	Dec 2012	7
Q.2	Why complete binary tree structure considered as efficient space and time complexity?	June 2014	2

Unit-03/Lecture-03

Binary Tree

Binary Tree Representations :

Sequential Representation :

The sequential representation of tree stores data in an array as per the following rules:

1. The root node is stored in 1^st position.

2. Every left and right child of a parent node at location k will be stored in (2*K)^th position and (2*K+1)^th position respectively.

The following example shows the representation of binary tree in an array.

F	B	H	A	D	G	I			C	E
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16

Fig-3.2.4

Suppose an array is representing a tree then its tree representation will be drawn using the same rule and an example is shown bellow.

BACK

A	B	C	D	E		F	G	H					I	J
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16

Fig-3.3.1

Linked Representation of Tree: [RGPV/Dec2012 (7)]

The Linked representations of tree, maintains three parallel arrays. An INFO array contains the data of each node, LEFT array contains the location of left child and RIGHT array contains location of right child. A ROOT pointer points to the root node of the tree.

LEFT INFO RIGHT

	null	C	1	null
			2	4
3	5	D	3	9
ROOT			4	6
	7	B	5	1
			6	8
2	null	A	7	null
AVAIL			8	10
	null	E	9	null
			10	null

Fig-3.3.2

BACK

S.NO	RGPV QUESTIONS	Year	Marks
Q.1	Explain the linked representation of binary tree	Dec 2012	7

Unit-03/Lecture-04

Traversing of Binary Tree - 1

Binary Tree Traversal Techniques: [RGPV/Dec2011 (7)] [RGPV/Dec2013 (7)]

Traversal of a binary tree refers to the process of visiting all the nodes of the tree, in some specific sequence. For a linked list, the traversal was done in the natural order of the list, starting from the first node and ending at the last. In a tree, there are many ways in which one could traverse all the nodes.

Visiting a node generally means retrieving the data item contained in the node, and sending it to some process (printing, for example).

The three traversal orders are defined as follows:

(i) Preorder Traversal: (VLR)

o Visit the current node.

o Traverse the left sub-tree of the current node.

o Traverse the right sub-tree of the current node.

Preorder traversal can be implemented as a recursive function : BACK

We can generate a prefix expression using a pre-order traversal. Much like for the in-order traversal, we will use recursion to print the entire left subtree and the entire right subtree. In a prefix expression, the operator comes before its two operands, so we will have to print out the parent node's data before recursively printing its left and right children.

void preorder(BinaryTreeNode root)

               if (null == root) return;

               System.out.println(root. data());

               preOrder(root.left());   // print the entire left subtree

               preOrder(root. right());  // print the entire right subtree

               return;

So instead of printing the data after we have printed the left subtree, we are going to print the data first, so that the operator will print out before its operands, giving us the prefix representation of the expression.

(ii) Inorder Traversal: (LVR)

o Traverse the left sub-tree of the current node.

o Visit the current node.

o Traverse the right sub-tree of the current node.

Inorder traversal can be implemented as a recursive function:

In an infix expression, the operator comes between its operands, so if we want to generate the infix expression from an expression tree, we will need to print the operand on the left before we print out the operator. But what if the left operand is another expression to evaluate? We use recursion. We print out the entire left subtree, then print the current node, then print out the entire right subtree.

void inOrder(BinaryTreeNode root)

               if (null == root) return;

               inOrder(root.left());   // print the entire left subtree

               System.out.println(root. data());

               inOrder(root. right());  // print the entire right subtree

               return;

In this code, "root" refers to the root of the current subtree, not the root of the whole tree (although we would have to start at the root of the whole tree). So, how does this work? Let's look at the steps that this method takes for the simple expression 5 + 3 (for convenience, the nodes have been numbered):

(iii) Postorder Traversal: (LRV) [RGPV/June 2011 (10)] BACK

o Traverse the left sub-tree of the current node.

o Traverse the right sub-tree of the current node.

o Visit the current node.

Postorder traversal can be implemented as a recursive function:

By now, you should see a pattern. The last representation is postfix, and we will use a post-order traversal to obtain it. Since in postfix the operator comes after its two operands, will recursively print the left and right subtrees before we print out the data at the current node.

void postOrder(BinaryTreeNode root)

               if (null == root) return;

               postOrder(root.left());  // print the entire left subtree

               postOrder(root. right()); // print the entire right subtree

               System.out.println(root. data());

               return;

Example:

a

g

f

e

d

c

b

root

Fig -3.4.1

Preorder: a b c d f g e

Inorder: b a f d g c e

Postorder: b f g d e c

BACK

S.NO

RGPV QUESTIONS

Year

Marks

Q.1

Write the recursive Inorder,Preorder,and PostorderTree traversing algorithms

Dec 2013

Dec 2011

Q.2

Write the non recursive PostorderTree traversing algorithms

June 2011

Unit-03/Lecture-05
Traversing of Binary Tree-2
Example on Binary tree Traversing [RGPV/June 2011 (10)] Fig-3.5.1 BACK Threads and Threaded Binary Tree: [RGPV/Dec 2013 (7)] Approximately half of the entries in the pointer fields Left and right of any binary tree contains null elements. Replacing the null entries by some other type of information may more efficiently use this space. Specifically, we will replace certain null entries by special pointers, which point to nodes higher in the tree. These special pointers are called threads and the tree is called threaded binary tree. There are many ways to thread a binary tree, but each threading will correspond to a particular traversal of tree. Unless otherwise stated, threading will correspond to in-order traversal.There are two types of threading: Ø One way threading Ø Two way threading In one way threading, either left pointer or right pointer will be used for threading. When left pointer used to point the predecessor node of the tree according to in-order traversal, then the threading is called left-in threading. When a right pointer is used to point the successor node according to in-order traversal, then the threading is called right-in threading. In two way threading both left and right pointers are used to point predecessor and successor nodes of the tree according to in-order traversal Binary Search Tree (BST) A Binary Search Tree (BST) is a binary tree which follows the following conditions Every element has a unique key. The keys in a nonempty left subtree are smaller than the key in the root of subtree. The keys in a nonempty right subtree are greater than the key in the root of subtree. The left and right subtrees are also binary search trees. BACK Fig-3.5.2 Example: Fig-3.5.3 BACK
S.NO	RGPV QUESTIONS	Year	Marks
Q.1	What is threaded binery tree ?Explain and Create the threaded binary tree for the given tree	Dec 2013	7
Q.2	Using the sequence given below,construct Binary tree Preorder :A B C D E F G H I Inorder :B C A E D G H F I	June 2011	10

UNIT 3/LECTURE 6

Binary Search Tree

Valid Operations on Binary Search Tree: [RGPV/June 2012 (3.5)] [RGPV/Dec 2012 (3.5)]

[RGPV/Dec 2011 (3.5)]

Inserting an element
Deleting an element
Searching for an element

Inserting Nodes to a BST :

In a BST, a new node will always be inserted at a NULL pointer. We never have to rearrange existing nodes to make room for a new one.

BACK

Deleting Nodes from a BST : [RGPV/Dec 2011 (7)]

a) Deleting a leaf node: Replace the link to the deleted node by NULL.

b) Deleting a node with one empty subtree.

Fig-3.6.1

BACK

c) Deleting a node with both left and right subtrees. Any deleted value that has two children must be replaced by an existing value that is one of the following:

- The largest value in the deleted node’s left subtree

- The smallest value in the deleted node’s right subtree.

Fig-3.6.2 BACK

Searching a binary search tree:

Starting at the root node, the search algorithm compares the search key with the data stored in the current node.

(a) If the search key is equal to the data of the current node, the value has been found, and the search is terminated.

(b) If the search key is greater than the data of the current node, the search proceeds with the right child as the new current node.

(c) If the search key is less than the data of the current node, the search proceeds with the left child as the new current node.

(d) If the current node is null, the search is terminated as unsuccessful.

Algorithm SearchBST(val root <pointer>,Val argument <key>)

Search a binary search tree for a given value

Pre : root is the root to a binary tree

Return the node address if the value is found or null if the node is not in the tree

1 if (root is null)

1 return null

2 end if

3 if (argument < root->key)

1 return searchBST(root->left, argument) BACK

4 elseif (argument > root->key)

1 return searchBST(root->right, argument)

5 else

1 return root

6 end if

end searchBST

6 end if

end searchBST

Since the above search algorithm visits at most one node in each level of the binary tree, the algorithm runs in Q(h) time, where h is the height of the tree.

BACK

S.NO	RGPV QUESTION	YEAR	MARKS
Q.1	Following nodes are inserted into empty tree in order(5,16,20,40,5,10,18,30,40,12,1). Construct BST	Dec 2012	3.5
Q.2	Following nodes are inserted into empty tree in order(5,10,20,40,2,9,18,30,45,12,3). Construct BST	June 2012	3.5
Q.3	Following nodes are inserted into empty tree in order(5,16,20,40,5,10,18,30,40,12,1). Construct BST	Dec 2011	3.5
Q.4	Write an algorithm to delete operation in any Binary search tree	Dec 2011	7

UNIT 3/LECTURE 7

AVL Tree - 1

Avl Tree: [RGPV/Dec 2012 (7)] [RGPV/June 2012 (7)]

Definition :

· Empty BST is an AVL tree

· Non-empty BST is an AVL tree if

1. Balance factor-Height of the left and right subtrees don’t differ by more than 1

2. Left and right subtrees are AVL trees

· If height of left subtree is same as the height of right subtree, balance factor is 0

· If height of left subtree is 1 more than the height of right subtree, balance factor is 1

· If height of left subtree is 2 more than the height of right subtree, balance factor is 2

· If height of left subtree is 1 less than the height of right subtree, balance factor is -1

· If height of left subtree is 2 less than the height of right subtree, balance factor is -2

BACK

· Whenever balance factor of a subtree becomes +/- 2, we use rotation to fix that subtree.

· We have to identify what type of rotation we need and where we need it

· WHERE: Start from the item inserted last and keep going up until we see a non-AVL tree

· WHAT TYPE:

1. LL type: Left subtree was longer, the new item went to the left of left subtree. See board for example.
Single clockwise rotation

2. LR type: Left subtree was longer, the new item went to the right of left subtree. See board for example.
Double rotation: Counter clock wise on the left subtree and clockwise on the tree

3. RR type: Right subtree was longer, the new item went to the right of right subtree. See board for example.
Single counter clockwise rotation

4. RL type: Right subtree was longer, the new item went to the left of right subtree. See board for example.
Double rotation: clock wise on the right subtree and counter clockwise on the tree

· Clock-wise rotation:

· root of left subtree is the new root

· old root is the right child of new root

· old right child of new root is now the left child of old root

· Counter Clock-wise rotation:

· root of right subtree is the new root

· old root is the left child of new root

· old left child of new root is now the right child of old root

BACK

Fig-3.7.1

Operations of Avl tree: [RGPV/Dec 2011 (7)]

Inserting an element
Deleting an element
Searching for an element

BACK

Here are the four cases we will look at:

1) insertion into the left subtree of the left child of the root.(LL)

2) insertion into the right subtree of the left child of the root.(LR)

3) insertion into the left subtree of the right child of the root.()RL

4) insertion into the right subtree of the right child of the root.(RR)

The left picture is case 2 of this description, and the right picture is case 4. Why is the case on the left called a double rotation? Because we can achieve it by performing two rotations on the root node:

C C

/ \ / \

A T₃ B T₃

/ \ ====> / \

T₀ B L A T₂

/ \ / \

T₁T₂T₀T₁

/ \

====> A C

R / \ / \

T₀T₁T₂T₃

Fig-3.7.2

Insertion into an AVL Tree BACK

So, now the question is, how can we use these rotations to actually perform an insert on an AVL tree?

Here are the basic steps involved:

1) Do a normal binary tree insert.

2) Restoring the tree based on this leaf node.

This restoration is more difficult than just following the steps above. Here are the steps involved in the restoration of a node:

1) Calculate the heights of the left and right subtrees, use this to set the potentially new height of the node.

2) If they are within one of each other, just go up to the parent node and continue.

3) If not, then perform the appropriate restructuring described above on that particular node, THEN go to the parent node and continue.

4) Stop when you've reached the root node.

With insertion, we are guaranteed that we will at most rebalance the tree once.

When we march up the tree, at each step we are updating the height of that node, if necessary. The only nodes that need to be updated are those on the ancestral "lineage" of the inserted node.

Deletion from an AVL Tree BACK

First we will do a normal binary search tree delete. Note that structurally speaking, all deletes from a binary search tree delete nodes with zero or one child. For deleted leaf nodes, clearly the heights of the children of the node do not change. Also, the heights of the children of a deleted node with one child do not change either. Thus, if a delete causes a violation of the AVL Tree height property, this would HAVE to occur on some node on the path from the parent of the deleted node to the root node.

Thus, once again, as above, to restructure the tree after a delete we will call the restructure method on the parent of the deleted node. One thing to note: whereas in an insert there is at most one node that needs to be rebalanced, there may be multiple nodes in the delete that need to be rebalanced. Technically speaking, at any point in the restructuring algorithm ONLY one node will ever be unbalanced. But, what may happen is when that node is fixed, it may propagate an error to an ancestor node. But, this is NOT a problem because our restructuring algorithm goes all the way to the root node.

S.NO	RGPV QUESTION	YEAR	MARKS
Q.1	Explain AVL Tree with suitable example.	Dec 2012	7
Q.2	Explain AVL tree with all four rotation (LL,RR,LR,RL)	June 2012	7
Q.3	Explain the operations of AVL Tree	Dec 2011	7
Q.4	In an AVL tree at what condition the balancing is to be done.	June 2014	2

UNIT 3/LECTURE 8

AVL Tree -2

AVL Tree Examples : [RGPV/June 2011 (10)] [RGPV/June 2012 (7)] [RGPV/Dec 2011 (3.5)] [RGPV/Dec 2012 (3.5)]

1) Consider inserting 46 into the following AVL Tree: BACK

/ \

16 48

/ \ / \

8 24 40 56

/ \ / \

36 44 52 60

46, inserted here

Fig-3.8.1

Initially, using the standard binary search tree insert, 46 would go to the right of 44. Now, let's trace through the rebalancing process from this place.

First, we call the method on this node. Once we set its height, we check to see if the node is balanced. (This simply looks up the heights of the left and right subtrees, and decides if the difference is more than 1.) In this case, the node is balanced, so we march up to the parent node, that stores 44.

We will trace through the same steps here, setting the new height of this node (this is important!) and determining that this node is balanced, since its left subtree has a height of -1 and the right subtree has a height of 0.

Similarly, we set the height and decide that the nodes storing 40 and 48 are balanced as well. Finally, when we reach the root node storing 32, we realize that our tree is imbalanced.

Now, we finally get to execute the code inside the if statement in the rebalance method. Here we set xPos to be the tallest grandchild of the root node. (This is the node storing 40, since its height is 2.) Thus, the restructuring occurs on the nodes containing the 32, 48 and 40. Using the method described from last lecture, we will restructure the tree as follows:

/ \

32 48

/ \ / \

16 36 44 56

/ \ \ / \

8 24 46 52 60

Fig-3.8.2

Using the variables from the last lecture, the node storing 40 is B, the node storing 32 is A, and the node storing 48 is C. T₀ is the subtree rooted at 16, T₁ is the subtree rooted at 36, T₂ is the subtree rooted at 44, and T₃ is the subtree rooted at 56.

2) Now, for the second example, consider inserting 61 into the following AVL Tree:

/ \

16 48

/ \ / \

8 24 40 56

/ / \ / \

4 36 44 52 60

/ \

58 62

61, inserted

Fig-3.8.3

Tracing through the code, we find the first place an imbalance occurs tracing up the ancestry of the node storing 61 is at the noce storing 56. This time, we have that node A stores 56, node B stores 60, and node C stores 62. Using our restucturing algorithm, we find the tallest grandchild of 56 to be 62, and rearrange the tree as follows:

/ \

16 48

/ \ / \

8 24 40 60

/ / \ / \

4 36 44 56 62

/ \ /

52 58 61

Fig-3.8.4

T₀ is the subtree rooted at 52, T₁ is the subtree rooted at 58, T₂ is the subtree rooted at 61, and T₃ is a null subtree.

3) For this example, we will delete the node storing 8 from the AVL tree below:

/ \

16 48

/ \ / \

8 24 40 56

\ / \ / \

28 36 44 52 60

/ \

58 62

Fig-3.8.5

BACK

Tracing through the code, we find that we must first call the rebalance method on the parent of the deleted node, which stores 16. This node needs rebalancing and gets restructured as follows:

/ \

24 48

/ \ / \

16 28 40 56

/ \ / \

36 44 52 60

/ \

58 62

Fig-3.8.6

Notice that all four subtrees for this restructuring are null, and we only use the nodes A, B, and C. Next, we march up to the parent of the node storing 24, the node storing 32. Once again, this node is imbalanced. The reason for this is that the restructuring of the node with a 16 reduced the height of that subtree. By doing so, there was in INCREASE in the difference of height between the subtrees of the old parent of the node storing 16. This increase could propogate an imbalance in the AVL tree.

When we restructure at the node storing the 32, we identify the node storing the 56 as the tallest grandchild. Following the steps we've done previously, we get the final tree as follows:

BACK

/ \

32 56

/ \ / \

24 40 52 60

/ \ / \ / \

16 28 36 44 58 62

Fig-3.8.7

4) The final example, we will delete the node storing 4 from the AVL tree below:

/ \

16 48

/ \ / \

8 24 40 56

/ / \ / \

4 36 44 52 60

/ \

58 62

Fig-3.8.8

When we call rebalance on the node storing an 8, (the parent of the deleted node), we do NOT find an imbalance at an ancestral node until we get to the root node of the tree. Here we once again identify the node storing 32 as node A, the node storing 48 as node B and the node storing 56 as node C. Accordingly, we restructure as follows:

/ \

32 56

/ \ / \

16 40 52 60

/ \ / \ / \

8 24 36 44 58 62

Fig-3.8.9

BACK

S.NO	RGPV QUESTION	YEAR	MARKS
Q.1	Following nodes are inserted into empty tree in order(5,16,20,40,5,10,18,30,40,12,1). Construct AVL tree	Dec 2012 Dec 2011	3.5 3.5
Q.2	Following nodes are inserted into empty tree in order(5,10,20,40,2,9,18,30,45,12,3). Construct AVL tree	June 2012	3.5
Q.3	Following nodes are inserted into empty tree in order(20,30,40,50,60,57,56,55,52). Construct AVL tree	June 2011	10

UNIT 3/LECTURE 9

B Trees

B Trees :

B Trees are a special case of the tree data structure. First we will review tree structures and search trees, then talk about B-Trees and later B+ Trees. BACK

Fig-3.9.1

· A common way to implement a tree is to have as many pointers in a node as there are children of the node.

· As well, a parent pointer can also be stored in each node.

· Nodes usually contain some type of stored information. When a multilevel index is implemented as a tree structure, the information includes values of the files’ indexing field that are used to guide the search for a record.

Multilevel Indexes as Special Search Trees

Multilevel indexes can be thought of as a variation of a search tree(a special type of tree that is used to guide the search for a record with record field value V)

Each node can have as many as fo pointers and fo key values, where fo is the index fo (blocking factor of the index).

Fig-3.9.2

BACK

The index values in each node guide us to the next node, until you reach the data file block that contains the required records. By following a pointer, the search is restricted at each level to a subtree of the search tree, and the nodes not in the subtree are ignored

Search Trees :

Fig-3.9.3

A search tree of order p is such that each node contains at most p-1 search values and p pointers in the following order: <P₁, K₁, P₂, K₂…K_q-1, P_q>, where:

q<=p;
each P_i is a pointer to a child node, or a null pointer;
and each K_i is a search value from some ordered set of values.

Two constraints must hold on the search tree:

1. Within each node, the key values are ordered (K₁ < K₂ < …<K_q-1>)

2. For all values X in the subtree pointed to by P_i,

· For 1 < i < q, K_i-1<X < K_i

· For i = 1, X < K, and

· For i = q, Ki-1 < X,

When searching for a value X, you follow the pointers, P, using the above conditions.

Fig-3.9.4

BACK

The values in the tree can be one of the fields in the file called the search field. This is the same as the index field as a file. Each key value is associated with a pointer, either to a record in the data file having that search key value, or a pointer to the block containing the record with the

search key value.

The tree in the first diagram is not balanced, meaning that leaf nodes can be found at different levels. This is not an efficient organization, because some nodes may be at very high levels, requiring many block accesses.

The B-Tree addresses this problem by specifying additional constraints.

Fig-3.9.5

B Trees : [RGPV/June 2011 (10)] [RGPV/June 2012 (7)] [RGPV/Dec 2013 (7)]

The B-Tree has additional constraints to ensure the tree is aways balanced, and the space wasted by deletion never becomes excessive. BACK

Fig-3.9.6

The formal definition of a B-Tree of order p, when used as an access structure on a key field, to search for a record is as follows:

1. Each internal node in the tree is of the form:

<P₁, <K₁, Pr₁>, P₂, <K₂, Pr₂>… <K_q-1, Pr_q-1>, P_q> , where q<=p. Each P is a tree pointer, a pointer to a node in the tree, and each Pr is a data pointer, a pointer to the record whose search key field value is equal to K.

2. The key values, K_i…K_q-1 are ordered within each node.

3. For all search key values X in the subtree pointed at by P_i, the ith subtree, we have:

· For 1 < i < q, K_i-1 < X < K_i,

· For i = 1, X < K_i,

· For i = q, K_i-1 < X

4. Each node has at most p tree pointers. BACK

5. Each node except the root has at least ép/2ù tree pointers. The root node has at least two tree pointers unless it is the only node in the tree.

6. A node with q tree pointers, q<=p had q-1 search key field values and hence q-1 data pointers.

7. All leaf nodes are at the same level. Leaf nodes have the same structure as internal nodes except that all of their tree pointers P_i are null.

We assumes the B-Tree access structure is on a key field, therefore the values are unique. If the B-Tree is used on a non-key field, the pointer would point to a cluster of blocks that contain blocks of file pointers, similar to option 3 for secondary indexes.

B-Tree starts with a single root node, which is also a leaf node, at level 0.
Once the root node is full with p-1 search key values, the root node splits evenly into two nodes at level 1. Only the middle value is kept in the root.
When a non root node is full, and a new entry is inserted into it, the node is split into two nodes at the same level, and the middle entry is moved to the parent node along with two pointers to the split nodes.
If the parent node is full, it is also split. BACK
Splitting can propogate all the way to the root, creating a new level if the root is split.
If deletion of a value causes a node to be less that half full, it is combined with its neighboing nodes, this can propogate all the way to the root.
After numerous random insertions and deletions, the nodes are approximately 69 percent full when the number of values in the tree stabilizes. If this happens, node splitting and combining will occur only rarely.

S.NO	RGPV QUESTION	YEAR	MARKS
Q.1	Create B-Tree of order 5 from the following lists of data items : 20,30,40,10,5,40,50,60,55,65	Dec 2013	7
Q.2	Explain B-tree with suitable example.	June 2012	7
Q.3	What is a B Tree? Discuss the algorithm used for insertion of a node into a B tree.	June 2011	10

UNIT 3/LECTURE 10/ADDITIONAL TOPIC

Huffman Coding

Huffman Coding Algorithm :

The idea behind Huffman coding is to find a way to compress the storage of data using variable length codes. Our standard model of storing data uses fixed length codes. For example, each character in a text file is stored using 8 bits. There are certain advantages to this system. When reading a file, we know to ALWAYS read 8 bits at a time to read a single character. But as you might imagine, this coding scheme is inefficient. The reason for this is that some characters are more frequently used than other characters. Let's say that the character 'e' is used 10 times more frequently than the character 'q'. It would then be advantageous for us to use a 7 bit code for e and a 9 bit code for q instead because that could shorten our overall message length.

Huffman coding finds the optimal way to take advantage of varying character frequencies in a particular file. On average, using Huffman coding on standard files can shrink them anywhere from 10% to 30% depending to the character distribution. (The more skewed the distribution, the better Huffman coding will do.)

The idea behind the coding is to give less frequent characters and groups of characters longer codes. Also, the coding is constructed in such a way that no two constructed codes are prefixes of each other. This property about the code is crucial with respect to easily deciphering the code. BACK

Now, repeat this process until only one tree is left:

Fig-3.1a.1

Fig-3.1a.2

Once the tree is built, each leaf node corresponds to a letter with a code. To determine the code for a particular node, walk a standard search path from the root to the leaf node in question. For each step to the left, append a 0 to the code and for each step right append a 1. Thus for the tree above we get the following codes:

Letter Code

'a' 001

'b' 0000

'c' 0001

'd' 010

'e' 011

'f' 1