Monday, January 16, 2017

Binary Tree

Binary Tree - A binary tree has a special condition that each node can have a maximum of two children.

Binary Search Tree - Binary Search tree exhibits a special behavior. A node's left child must have a value less than its parent's value and the node's right child must have a value greater than its parent value.

Full Binary Tree - A full binary tree (sometimes proper binary tree or 2-tree or strictly binary tree) is a tree in which every node other than the leaves has two children.

Complete Binary Tree - A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

B Tree -In B-Tree every node can store more than one value (key) and it can have more than two children. B-Tree was developed in the year of 1972 by Bayer and McCreight with the name Height Balanced m-way Search Tree. Later it was named as B-Tree.

B-Tree can be defined as follows...

B-Tree is a self-balanced search tree with multiple keys in every node and more than two children for every node.
Here, number of keys in a node and number of children for a node is depend on the order of the B-Tree. Every B-Tree has order.

B-Tree of Order m has the following properties...

Property #1 - All the leaf nodes must be at same level.
Property #2 - All nodes except root must have at least [m/2]-1 keys and maximum of m-1 keys.
Property #3 - All non leaf nodes except root (i.e. all internal nodes) must have at least m/2 children.
Property #4 - If the root node is a non leaf node, then it must have at least 2 children.
Property #5 - A non leaf node with n-1 keys must have n number of children.
Property #6 - All the key values within a node must be in Ascending Order.
For example, B-Tree of Order 4 contains maximum 3 key values in a node and maximum 4 children for a node.

No comments: