Binary Search Trees

Binary Search Trees

Comparisions of Computational Complexities of Various Data Structures

The following table describes the speed advantages of using a BST. Note how the advantages of a BST go away as the tree becomes increasingly unbalanced.

ItemArray (unsorted)Array (sorted)Link ListBST (balanced)BST (max unbalanced)
SearchO(n)O(log n)O(n)O(log n)O(n)
InsertO(1)O(n)O(1)O(log n)O(n)
DeleteO(n)O(n)O(n)O(log n)O(n)

BST Basics

Reflection Questions on Binary Search Trees (BST):

  1. What properties turn a binary tree into a Binary Search Tree (BST)?
  2. Why is the search process in a BST similar to a binary search of a sorted array?
  3. How do we insert new elements into a BST?
  4. Between insertions and deletions, which are more difficult for a BST?

Deleting Elements from a BST

Deleting nodes from a BST is tricky. The algorithm is often a topic for software interview questions. Be sure you understand the process fully after watching this video:

Keeping Binary Search Trees Balanced

We have previously seen that as BSTs become more and more unbalanced, their advantages in processing with fast computational speeds goes away. There are various strategies available to make sure that BSTs remain balanced as insertions and deletions take place. In this introductory course, we will not further delve into these strategies. However, you are encouraged to research on your own the following two methods that are commonly used to maintain balance in Binary Search Trees. 

  1. Red-Black Trees
  2. AVL Trees

1 point
A list of numbers in unknown order is inserted into a binary search tree. Which of the following is true?