Question

Additional Problem (25%)

• Chapters 9 and 10 discuss the different types of tree data structures that you can build. For all the ones listed below, define them and discuss the differences in each. Also for each of them, discuss the advantages and disadvantages of using them to create an Abstract Data Type.

• general tree
• binary tree
• binary search tree
• heaps
• B-trees

Answer 1

Solution:

General Tree: A Tree in which each node having either 0 or more child nodes is called general tree. So we can say that a Binary Tree is a specialized case of General tree.
General Tree is used to implement File System.

1.) Binary Tree:- A binary tree is types of general tree. A general tree have maximum two children then that tree called as binary tree. Each child is designated as either left child or right child.

In simple words we can say that a binary tree is a finite set of nodes that is (i) either child is empty (ii) or consist of distinguished node called root and remaining nodes are partitioned into two disjont sets of subtree.

In the above example we can see that its have maximum two child of each root node in tree.

There are many types of binary tree like complete binary tree, extended binary tree full binary tree etc.

2,) Binary search Tree:- A binary search tree is ordered binary tree in which nodes are arranged in order. In left side all elements in its left subtree are less to the node, and all the elements in its right subtree are greater than the node.

In the above image we can see that in left side of node all elements value are less while right side greater.

3.) Binary heap tree:- A heap tree is complete binary heap tree in which the value of element insert in heap order property.

This is complete tree and this element is in sorted order.

There are two types of binary heap:-

a) Min heap : A binary heap tree in which root node value is less than child nodes.

b) max heap: A binary heap tree in which root node value is greater than child nodes.

5) B tree is self balancing binary search tree
Properties of B-Tree
1) All leaves are at same level.
.2) Every node except root must contain at least t-1 keys. Root may contain minimum 1 key.
3) All nodes may contain at most 2n– 1 keys.
4) Number of children of a node is equal to the number of keys in it plus 1.
5) B-Tree grows and shrinks from root which is unlike Binary Search Tree. Binary Search Trees grow downward and also shrink from downward.

6) A B-Tree is defined by the term minimum degree ‘n’. The value of t depends upon disk block size