Binary Search Trees
CSE205
Concepts of Computer Science and
Data Structure
Outline
•Binary Search Trees (BSTs)
•BST Implementation
•Balanced Binary Search Trees
Binary Search Trees (BSTs)
•A search tree is a tree whose elements are organized to
facilitate finding a particular element when needed
•A binary search tree is a binary tree that, for each node n
–the left subtree of n contains elements less than the element
stored in n
–the right subtree of n contains elements greater than or equal to
the element stored in n
Binary Search Trees (BSTs)
Binary Search Trees (BSTs)
•To determine if a particular value exists in a tree
–start at the root
–compare target to element at current node
–move left from current node if target is less than element in the
current node
–move right from current node if target is greater than element in
the current node
•We eventually find the target or encounter the end of a
path (target is not found)
Binary Search Trees (BSTs)
•The particular shape of a binary search tree depends on
the order in which the elements are added to the tree
•The shape may also be dependant on any additional
processing performed on the tree to reshape it
•Binary search trees can hold any type of data, so long as
we have a way to determine relative ordering
•Objects implementing the Comparable interface provide
such capability
Adding an Element to a BST
•Process of adding an element is similar to finding an
element
•New elements are added as leaf nodes
•Start at the root, follow path dictated by existing elements
until you find no child in the desired direction
•Add the new element
Adding an Element to a BST
77
24 82
5817
40
97
Next to add:
77245882174097
Degenerate Tree
•Degenerate tree – a grossly unbalanced tree, usually
favoring one side
•Occurs if the input is completely or mostly sorted
•Essentially degrades into a linked list
•Removes the value of a binary search tree – ability to
exclude large amount of data with each comparison
operation
A Degenerate Tree
Removing an Element from a BST
•Removing a target in a BST is not as simple as that for
linear data structures
•After removing the element, the resulting tree must still
be valid
•Three distinct situations must be considered when
removing an element
–The node to remove is a leaf
–The node to remove has one child
–The node to remove has two children
Situation
1
Situation
2
Removing an Element from a BST
Removing an Element from a BST
•Dealing with the situations
–Node is a leaf: it can simply be deleted
–Node has one child: the deleted node is replaced by the child
–Node has two children: an appropriate node is found lower in
the tree and used to replace the node
•Good choice: inorder successor (node that would follow the removed
node in an inorder traversal)
•The inorder successor is guaranteed not to have a left child
•Thus, removing the inorder successor to replace the deleted node will
result in one of the first two situations (it’s a leaf or has one child)
After the Root Node is Removed
Outline
•Binary Search Trees (BSTs)
•BST Implementation
•Balanced Binary Search Trees
BST Implementation
•Our BST implementation
is based on the binary
tree implementation
shown in BinaryTree
•The BinarySearchTree
interface class adds
support for the add,
remove, find, findMin,
and findMax methods
javafoundations.BinarySearchTree
//********************************************************************
// BinarySearchTree.java Java Foundations
//
// Defines the interface to a binary search tree.
//********************************************************************
package javafoundations;
public interface BinarySearchTree<T extends Comparable<T>> extends
BinaryTree<T>
{
// Adds the specified element to the tree.
public void add (T element);
// Finds and returns the element in the tree matching the
// specified target. Overrides the find method of BinaryTree.
public T find (T target);
// Returns the minimum value in the binary search tree.
public T findMin();
// Returns the maximum value in the binary search tree.
public T findMax();
// Removes and returns the specified element from the tree.
public T remove (T target);
}
javafoundations.LinkedBinarySearchTree
//*******************************************************************
// LinkedBinarySearchTree.java Java Foundations
//
// Implements the binary tree using a linked representation.
//*******************************************************************
package javafoundations;
import javafoundations.*;
import javafoundations.exceptions.*;
public class LinkedBinarySearchTree<T extends Comparable<T>>
extends LinkedBinaryTree<T> implements BinarySearchTree<T>
{
//-----------------------------------------------------------------
// Creates an empty binary search tree.
//-----------------------------------------------------------------
public LinkedBinarySearchTree()
{
super();
}
(more…)
javafoundations.LinkedBinarySearchTree
//-----------------------------------------------------------------
// Creates a binary search tree with the specified element at its
// root.
//-----------------------------------------------------------------
public LinkedBinarySearchTree (T element)
{
root = new BSTNode<T>(element);
}
//-----------------------------------------------------------------
// Adds the specified element to this binary search tree.
//-----------------------------------------------------------------
public void add (T item)
{
if (root == null)
root = new BSTNode<T>(item);
else
((BSTNode)root).add(item);
}
(more…)
javafoundations.LinkedBinarySearchTree
//-----------------------------------------------------------------
// Removes and returns the element matching the specified target
// from this binary search tree. Throws an ElementNotFoundException
// if the target is not found.
//-----------------------------------------------------------------
public T remove (T target)
{
BSTNode<T> node = null;
if (root != null)
node = ((BSTNode)root).find(target);
if (node == null)
throw new ElementNotFoundException ("Remove operation failed. "
+ "No such element in tree.");
root = ((BSTNode)root).remove(target);
return node.getElement();
}
(more…)
javafoundations.LinkedBinarySearchTree
//-----------------------------------------------------------------
// The following methods are left as programming projects.
//-----------------------------------------------------------------
// public T findMin() { }
// public T findMax() { }
}
javafoundations.BSTNode
//*******************************************************************
// BSTNode.java Java Foundations
//
// Represents a node in a binary search tree, storing Comparable
// elements.
//*******************************************************************
package javafoundations;
public class BSTNode<T extends Comparable<T>> extends BTNode<T>
{
//-----------------------------------------------------------------
// Creates a new tree node with the specified data.
//-----------------------------------------------------------------
public BSTNode (T element)
{
super(element);
}
(more…)
javafoundations.BSTNode
//-----------------------------------------------------------------
// Adds a new node containing the specified element at the
// appropriate place in this tree.
//-----------------------------------------------------------------
public void add (T item)
{
if (item.compareTo(element) < 0)
if (left == null)
left = new BSTNode (item);
else
((BSTNode)left).add (item);
else
if (right == null)
right = new BSTNode (item);
else
((BSTNode)right).add (item);
}
(more…)
javafoundations.BSTNode
//-----------------------------------------------------------------
// Returns the node in this subtree whose element matches the
// specified target. Returns null if the target is not found.
// Overrides the find method of BTNode to capitalize on the
// binary search tree characteristics.
//-----------------------------------------------------------------
public BSTNode<T> find (T target)
{
BSTNode<T> result = null;
if (target.compareTo(element) == 0)
result = this;
else
{
if (target.compareTo(element) < 0)
{
if (left != null)
result = ((BSTNode)left).find (target);
}
else
if (right != null)
result = ((BSTNode)right).find (target);
}
return result;
}
(more…)
javafoundations.BSTNode
//-----------------------------------------------------------------
// Removes the specified target from this subtree. Returns a
// reference to the revised tree. The tree will be unchanged if
// the target is not found.
//-----------------------------------------------------------------
public BSTNode<T> remove(T target)
{
BSTNode<T> result = this;
if (target.compareTo(element) == 0)
{
if (left == null && right == null)
result = null;
else if (left != null && right == null)
result = (BSTNode)left;
else if (left == null && right != null)
result = (BSTNode)right;
else
{
result = getSuccessor();
result.left = left;
result.right = right;
}
(more…)
javafoundations.BSTNode
}
else
if (target.compareTo(element) < 0)
if (left != null)
left = ((BSTNode)left).remove(target);
else
if (right != null)
right = ((BSTNode)right).remove(target);
return result;
}
//-----------------------------------------------------------------
// Finds and returns the node containing the inorder successor of
// this node, and then removes the successor from its original
// location in the tree.
//-----------------------------------------------------------------
protected BSTNode<T> getSuccessor()
{
BSTNode<T> successor = (BSTNode)right;
while (successor.getLeft() != null)
successor = (BSTNode) successor.getLeft();
((BSTNode)right).remove (successor.getElement());
return successor;
}
}
Implementation Notes
•The BinarySearchTree interface is designed to operate
on a generic type T
•However, elements placed in the BST also need to be
Comparable in order to determine their relative position
in the tree
public class LinkedBinarySearchTree<T extends Comparable<T>>
public class BSTNode<T extends Comparable<T>> extends BTNode<T>
Implementation Notes
•The LinkedBinarySearchTree class inherits the
reference to the root node from the LinkedBinaryTree
class
•The BSTNode class inherits the left and right
references to child nodes from the BTNode class
•The add method of LinkedBinarySearchTree creates a
new root node if the tree is empty
•Otherwise it invokes the add method of BSTNode, which
searches the location to add the new element as a leaf
Outline
•Binary Search Trees (BSTs)
•BST Implementation
•Balanced Binary Search Trees
Balanced Binary Search Trees
•The find and add operations of a balanced tree of n
nodes have an efficiency of O(log2n) [length of the
longest path]
•The more degenerate a tree becomes, the find and add
operations approach O(n)
•Our BST implementation does not guarantee a balanced
tree
•The shape of a BST is determined by the order which
elements are added to the tree
Balanced Binary Search Trees
•Other types of trees exist to ensure that they stay balanced
•They include AVL trees and red/black trees
• Operations such as rotations on binary search trees assist
in the process of keeping a tree balanced
•Rotations do not solve all problems created by unbalanced
trees, but show the basic algorithmic processes that are
used to manipulate tree
