Binary_search_tree

 

 AverageWorst case
SpaceO(n)O(n)
SearchO(log n)O(n)
InsertO(log n)O(n)
DeleteO(log n)O(n)

Properties

Has binary tree properties:

  • Collection of nodes
  • Each node has at most two children, left and right

Along with the following added properties:

  • Ordered, the left subtree contains only nodes with keys less than the node’s key.
  • The right subtree contains only nodes with keys greater than the node’s key.
  • Duplicates may or may not be allowed.  See dealing with duplicates in a binary search tree.

Common Operations

Insert

Search

Delete

Tree Traversal

  • In-Order Traversal – left, current, right
  • Pre-Order Traversal – current, left, right
  • Post-Order Traversal – left, right, current

Balanced Tree

  • A balanced tree refers to how evenly the nodes are distributed.
  • Having a balanced tree ensures optimal performance (O(log n)) Search , Insert and Delete
  • Common types of balanced trees:
    • Red-Black Trees
    • AVL Trees

Types of completeness:

  • Complete Binary Tree – binary tree in which every level is fully filled, except perhaps the last level. To the extent that the last level is filled, it is filled left to right.
  • Full Binary Tree – every node has either zero or two children. That is, no nodes have only one child
  • Perfect Binary Tree – A perfect binary tree is both full and complete. All leaf nodes will be the same level and this level has the maximum number of nodes. Must ave exactly (2^k) – 1 nodes where k is the number of levels.