The left subtree of each node contains values that are smaller than the value in the given node.
The right subtree of each node contains values that are greater than the value in the given node.
Example:
Operations:
- Search - compare the values and proceed either to the left or to the right.
- Insert - unsuccessful search - insert the new node at the bottom where the search has stopped.
- Delete - replace the value in the node with the
smallest value in the right subtree
or the largest value in the left subtree.
The idea behind is: all the values to the right are
greater than all the values to the left,
so the smallest one
will be greater too (i.e. after the replacement its left subtree
will contain smaller values.) And since we have taken the
smallest from the right subtree,
after the replacement the
right subtree will contain only greater values.
Creating a binary search tree:
Initially the tree is empty.
The first element to be stored is placed in a node that would be
the root of the tree.
Each next element is placed through the "unsuccessful search"
procedure.
Retrieving the elements in sorted order - by in-order traversal.
Complexity of search in a binary tree: O(logN)
The search at worst will proceed to the leaves, down a path in
the tree.
On average the depth of a binary tree with N
elements is log(N).
This is not the worst case though. The worst case is when
the items to be inserted
are sorted, then the tree degenerates
to a list:
The tree is not balanced.
Disadvantages of Binary Search Trees: