Data Structures and
Algorithms
B- TREE
B+- TREE
THREADED BINARY TREE
1
m-way Search Tree (Multi
way)
The m-way search trees are multi-way trees which
are generalised versions of binary trees where each
node contains multiple elements. In an m-Way tree
of order m, each node contains a maximum of m –
1 elements or keys and m children.
The goal of m-Way search tree of height h calls for
O(h) no. of accesses for an insert/delete/retrieval
operation. Hence, it ensures that the height h is close
to log_m(n + 1).
2
M-way Serach Tree
3
M-way Serach Tree
4
B- TREE
M-way search tree has the advantage of minimizing file accesses due to
their restricted height. However height of the tree be kept as low as
possible and therefore there arises a need to balance m-way search tree.
Such a balanced m-way search trees are called B- trees.
Definition:
A B- tree of order m is a m-way search tree in which:
The root has at least two child nodes (one key) and at most m child
nodes or (m-1) keys
All the internal nodes should have maximum ‘m’ child nodes or ‘m-1’
keys and at least m/2 (CEIL function) child nodes or ‘m/2’ keys.
All the leaf nodes are at same level i.e. tree is perfectly balanced
5
Insertion in a B-Tree
The insertion of a key in a B tree requires the first traversal in B-tree.
Through the traversal, it is easy to find that key which needs to be
inserted is already existed or not. There are basically two cases for
inserting the key that are:
Node is not full
Node is already full
If the leaf node in which the key is to be inserted is not full, then the
insertion is done in the node.
If the node were to be full then insert the key in order into existing set
of keys in the node, split the node at its median into two nodes at the
same level, pushing the median element up by one level.
Let us create a B-Tree of order 5.
6
Insertion in a B-Tree
7
Insertion in a B-Tree
8
Insertion in a B-Tree
9
Deletion in a B-Tree
10
Deletion in a B-Tree
11
Deletion in a B-Tree
12
Deletion in a B-Tree
13
B+ Tree
One of the major drawback of B-tree is the difficulty of
traversing the keys sequentially. A variation of B-tree
structure, the B+ tree retains the random access property
while it also allows the sequential access.
In B+ tree, all the keys are maintained in leaves and some
keys are replicated in non-leaf nodes to define path for
locating individual records.
The leaves are linked together to provide sequential access.
B+ tree retains the efficiency of searching and insertion in a
B-tree but increases the efficiency of finding the next record
in a tree from O(logn) to O(1)
14
B+ Tree
15
Difference between B- Tree
and B+ Tree
B + Tree B Tree
Search keys can be repeated. Search keys cannot be redundant.
Data is only saved on the leaf nodes. Both leaf nodes and internal nodes can
store data
Data stored on the leaf node makes the Searching is slow due to data stored on
search more accurate and faster. Leaf and internal nodes.
Linked leaf nodes make the search You cannot link leaf nodes.
efficient and quick.
16
Threaded Binary Tree
A binary tree can be represented using array representation or linked
list representation. When a binary tree is represented using linked list
representation, the reference part of the node which doesn't have a
child is filled with a NULL pointer. In any binary tree linked list
representation, there is a number of NULL pointers than actual
pointers.
A. J. Perlis and C. Thornton have proposed new binary tree called
"Threaded Binary Tree", which makes use of NULL pointers to
improve its traversal process. In a threaded binary tree, NULL pointers
are replaced by references of other nodes in the tree. These extra
references are called as threads.
17
Threaded Binary Tree
Types of threaded binary trees:
Single Threaded or one-way threading: each node is threaded
towards either the in-order predecessor or successor (left or right) means
all right null pointers will point to inorder successor OR all left null
pointers will point to inorder predecessor.
Double threaded or two way threading: each node is threaded
towards both the in-order predecessor and successor (left andright) means
all right null pointers will point to inorder successor AND all left null
pointers will point to inorder predecessor.
18
Threaded Binary Tree
1,3,5,6,7,8,9,11,13
19
Threaded Binary Tree
D,B,F,E,A,G,C,I,J,H,K
20
Threaded Binary Tree
D,B,F,E,A,G,C,I,J,H,K
21
Inorder traversal of threaded
binary tree
22
Advantages of Threaded
Binary Tree
In this Tree it enables linear traversal of elements.
It eliminates the use of stack as it perform linear
traversal.
Enables to find parent node without explicit use of
parent pointer
Threaded tree give forward and backward traversal of
nodes by in-order fashion
Nodes contain pointers to in-order predecessor and
successor
23