Binary Search Trees: Insertion, Search, and Traversal

Chapter 19

Objectives

In this lecture, we will:

• Explore various binary-tree traversal algorithms.

• Explore how to implement the basic operations on a binary tree.

• Learn about binary search trees to:

  • Organize data

  • Insert and delete items

• Explore recursive and non-recursive tree traversal algorithms.

Lecture Video

Motivation

The Problem with Arrays

Binary search is an efficient search algorithm that relies
on splitting a sorted list in half with each comparison.

Binary search works well on arrays. However,

• Insertion in an array is impossible, requiring the data to be copied to a new array. Deletion is also slow.

• Finding a specific value in a linked list is slow (needed for searching, insertion, and deletion).

The Problem with Linked Lists

Linked Lists, while great for insertion and deletion at the
ends, pose challenges for binary search due to the lack
of contiguous memory.

• Must start iterating from the first/last node (i.e., sequential search).

• Cannot jump right to the middle to perform a binary search.

Solution

Solution: Modify the linked-lists structure into a binary
search tree, where the binary search can be performed
in logarithmic time (usually).

Binary Search Trees:

• Are binary trees that maintain the binary-search property (more on that in a moment).

• Have the benefits of binary search with the flexibility of linked lists.

• Are fundamental in computer science and widely used in various algorithms and applications.

Binary Trees

A binary tree is empty or has:

• One root (topmost) node.

• Left subtree and right subtree, which are binary trees.

A Binary Tree

A Binary Tree

Example Trees:

Example binary trees with 1 to 3 nodes

Example binary trees with 1 to 3 nodes

More 3-node binary trees

More 3-node binary trees

• A node (called a vertex in graph theory):

  • Has at most two children.

  • Stores its own information.

  • Keeps track of its left subtree and right subtree using pointers
    (e.g., left and right).

• A pointer to the root node of the binary tree is stored outside the tree.

Binary tree with the pointers shown

Binary tree with the pointers shown

• Leaf: a node that has no children.

• A parent has a branch to a child node.

• There is a unique path from the root to every node.

• The path length is the number of branches on that path.

• Edge: The connection from a parent to a child.

• level of a node: number of branches from the root to the node.

  • The root node is at level 0.

• Height of a binary tree: number of edges on the longest path from the root to a leaf.

Binary Search Tree

Definition: A binary search tree is either empty or has these properties:

• Has a root node.

• Has two sets of nodes: the left and right subtrees.

• The key in the root node is larger than every key in the left subtree and smaller than every key in the right subtree.

• The left subtree and right subtree are binary search trees.

Example Binary Search Tree

Example Binary Search Tree

Applications

Used when data is frequently added/removed and a quick search is needed (e.g., maps, sets).
Quick Operations:

• Insertion

• Removal

• Search (a.k.a., find, lookup) existing values

Example domains:

• The base structure for many database engines.

• Computer graphics for determining object intersection.

Searching for a Value in a Binary Search Tree

Can be implemented iteratively or recursively.

If the node…

1. is null, return “not found”.

2. contains the key,
   return true.

3. contains a key is greater,
   search the left subtree.

4. contains a key is less,
   search the right subtree.

Inserting Values into a Binary Search Tree

1 / 1

Binary Search tree with the keys inserted in this order:
59, 70, 50, 58, 30, 44, 98, 77

The helper function for the recursive insert needs a reference to a Node pointer.

Click here to visualize why.

How do we handle duplicate keys?

We must choose one of three options. The duplicate key is…

1. not inserted (don’t permit duplicate keys).

2. inserted to the left of the matching key.

3. inserted to the right of the matching key.

As long as the insert() and contains() functions follow the same behavior, everything will work.

Performance Analysis for a Binary Search Tree

What is the Big-O performance of an operation?

Best-Case (Perfectly-Balanced Tree) is

Best-Case (Perfectly-Balanced Tree) is

A Worst-Case Example is

A Worst-Case Example is

Average Performance a Binary Search Tree

• There are possible orderings of the keys (assuming that all orderings are possible).

• For both average successful and unsuccessful searches of a nonempty tree:
  Number of comparisons
  Number of nodes visited

What is the average-case Big-O of the following operations on a binary search tree?

	Array	Linked List	Binary Search Tree
Random Access			NA
Insert/Remove
Search
Sort			NA *

* A binary-search tree is already sorted. To convert it to a sorted list, a inorder traversal will take .