Binary Search Trees

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.


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.


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).

Disadvantages of Binary Search Trees: The shape of the tree depends on the order of insertions, and it can be degenerated. When inserting or searching for an element, the key of each visited node has to be compared with the key of the element to be inserted/found. Keys may be long and the run time may increase much.

Improving the efficiency of Binary Search Trees:

•  Keeping the tree balanced: AVL trees (Adelson - Velskii and Landis) Balance condition: left and right subtrees of each node can differ by at most one level. It can be proved that if this condition is observed the depth of the tree is O(logN). 
• Reducing the time for key comparison: Radix trees - comparing only the leading bits of the keys.

 Advantages:

• BST is fast in insertion and deletion etc when balanced. 
• Very efficient and its code is easier than link lists.

Disadvantages:

•  Shape of the tree depends upon order of insertion and it can be degenerated.
•  Searching takes long time. 

  If the tail of a linked list is stored, then insertion into a linked list is decidedly faster than insertion into a binary tree. Insertion into a binary tree is O(N) at worst case (O(log N) at best) if it's unbalanced. If it's balanced, then insertions are O(log N), but there is house keeping involved in keeping it balanced. Insertion into a linked list is O(1) if the tail is kept.  Also, as BillyONeal mentioned, a binary tree is usually an associative structure, whereas linked lists are not.

Binary Trees

• medium complexity to implement (assuming you can't get them from a library)
• inserts are O(logN)
• lookups are O(logN)

Linked lists (unsorted)

• low complexity to implement
• inserts are O(1)
• lookups are O(N)