Tree Variations

Various TREES

Binary Search Tree

It is the one which has following properties:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

B Tree

The B tree is a balanced sort tree.

It is not a binary tree. B tree of order M  satisfies the following conditions:

• Each node has maximum of M children and minimum of M/2
• Each node has one fewer keys than children with a maximum of M-1 keys
• Keys are arranged in a defined order
• When a new key is inserted into a full node, the tree splits into two nodes
• All leaves are on the same level

B+  Trees

It has got two parts: 1. Index part             – interior nodes

2. Sequence set          – leaf nodes

• The keys can be accessed by both directly as well as sequentially
• The key value in the sequence set are the key value of the record collection
• The key value in the index part are used for the purpose of direct access to the sequence set

The leaves similarly contain the properly arranged numbers within the tree.