Binary Search Tree(BST)
Binary search tree is a binary tree in which each internal node 'x' stores an element such that the element stored in the left sub-tree of 'x' are less than or equal to 'x' and element stored in the right sub-tree of 'x' are greater than or equal to 'x'. This is called Binary Search Tree(BST).
Advantages/Characteristics/properties of BST
The main advantage of BST is that,it remains ordered---which provided quicker search items than many other data structers. The common properties of BST are as follows :
- The left sub-tree of a node, contains only node with keys less than the node keys.
- The right sub-tree of a node,contains only node with keys greater than the nodes key.
- The left and right sub-tree each must also be a binary search tree.
- Each node can have up to two successor nodes.
- There must be no duplicate nodes.
- A unique path should exist from the root to every other node.
Optimal Binary Search Tree
An Optimal Binary search tree is a binary search tree--- for which the nodes are arranged on levels such that, the tree cost is minimum. For the purpose of better presentation of optimal binary search trees , we will consider "extended binary search trees" which have the keys stored at their internal nodes of a binary search tree.Suppose 'n' keys are-- K1 K2 K3 ...... Kn are stored at the internal nodes of binary search tree. It assumed that, keys are given order, so that K1 < K2<... < Kn.
Quote: