Binary Search Trees

Notes

Definitions

A rooted binary tree is recursively defined as being either (1) empty, or (2) consisting of a node called root, with two rooted binary trees called the left and right subtrees.

Skiena Section 3.4

Binary search requires fast access to two elements - the media elements above and below the given node.

Search trees utilize this fact and a linked structure to create binary search trees.

Binary search tree labels each node in the binary tree with a single keys such that for any node labeled x, all of the nodes in the left subtree of x will have keys < x,while all nodes in the right subtree of x will have keys > x.

For any binary tree on n nodes and any set of n keys there is exactly one labeling that makes it a binary tsearch tree.

Implementation

Implement via:

• left and right pointer fields
• optional parent pointer

Operations:

• searching
• finding minimum/maximum element
• traversal (in order)
• insertion
• deletion

balanced search trees:

• trees exist, and can be used as black boxes.
• suppose that we have access to a balanced dictionary or tree data structure - and go from there.
• insert should automatically balance the tree

Weiss

Weiss, Data Structures in C++, covers binary search trees in Chapter 4, covering trees generally. This book is a good advanced data structures textbook, so it moves through trees quickly and spends most of its time on detailed implementations of types of trees.

The binary search tree covered on page 133 of the textbook provides an entire abstract data type that is as follows:

• Class name is BinarySearchTree
• Data member is pointer to root node (null for empty trees)
• public member functions use general technique of calling private recursive functions
• insert, remove, contains
• find min, find max
• binary node class:
  • single element of data
  • left pointer
  • right pointer

These methods are covered in more detail below. Implementations are all here: https://charlesreid1.com:3000/cs/java/src/master/trees/search-trees/Weiss.java

Contains

The contains method uses Recursion. The basic approach boils down to handling four possible cases as we recurse through all the nodes in the tree:

• We have reached an empty node, and should return false to the method that called us
• Our element is less than the search target, and we should go left
• Our element is greater than the search target, and we should go right
• Our element is just right, and this node is equal to the search target

def contains(target, node):
    if(node is null):
        return false
    elif target < node.getvalue():
        return contains(target, node.left)
    elif target > node.getvalue():
        return contains(target, node.right)
    else:
        return true

findMin and findMax

private routines returning pointers to the nodes containing the minimum and maximum elements in the tree.

These both assume a sorted binary tree. This means the find minimum method just has to return the left-most element, while the find maximum method just has to return the right-most element.

Here are two non-recursive implementations of findMin and findMax. Like many recursive patterns, this non-recursive implementation uses a while loop. The body of the while loop is typically converted directly to a recursive function body.

Here is the Java implementation of non-recursive versions:

	// Non-recursive versions of findMin/findMax

	/** Private method that returns the smallest element in the tree.
	 * This assumes the tree is sorted.
	 * */
	private BinaryNode findMin(BinaryNode node) { 
		if(node!=null) { 
			while(node.getLeft() != null) {
				node = node.getLeft();
			}
		}
		return node;
	}

	/** Private method that returns the largest element in the tree. 
	 * This assumes the tree is sorted.
	 * */
	private BinaryNode findMax(BinaryNode node) { 
		if(node!=null) { 
			while(node.getRight() != null) {
				node = node.getRight();
			}
		}
		return node;
	}

and the Java implementation of recursive versions:

	// Recursive versions of findMin/findMax

	/** Private method that returns the smallest element in the tree, recursively.
	 * This assumes the tree is sorted.
	 * */
	private BinaryNode findMin_r(BinaryNode node) { 
		if(node==null){
			// base case: we're nobody
			return null;
		}
		if(node.getLeft()==null) { 
			// base case: it's us
			return node;
		}
		// recursive case:
		// keep going
		return findMin_r(node.getLleft());
	}

	/** Private method that returns the largest element in the tree, recursively. 
	 * This assumes the tree is sorted.
	 * */
	private BinaryNode findMax_r(BinaryNode node) { 
		if(node==null){
			// base case: we're nobody
			return null;
		}
		if(node.getRight()==null) { 
			// base case: it's us
			return node;
		}
		// recursive case:
		// keep going
		return findMax_r(node.getRight());
	}

Link on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/trees/search-trees/Weiss.java

Insert

Insertion is conceptually simple - you insert a new node X into a tree T. You proceed down the tree as you do when searching the tree via contains() method. (See above.) If we find X, we stop immediately (no duplicates in tree.) Otherwise we insert X at the last spot in the tree that we traversed. (Where we exited the tree.)

Remove

Tricky to do in a sorted binary tree. Consider the three cases:

• No children
• One child
• Two children (tricky case; needs to recursively replace the node with its smallest left-most replacement)

Binary Search Tree Implementation

Implementation following Weiss: https://charlesreid1.com:3000/cs/java/src/master/trees/search-trees

See Java/Binary Search Tree