Binary search tree (Java)

From LiteratePrograms

Jump to: navigation, search
Other implementations: C | C++ | Haskell | Java | Scheme | Standard ML

Contents

Overview

A simple binary search tree, implemented as an object-oriented, recursive data structure in Java, for objects that extend Comparable. Note that Java already provides efficient tree-based data structures, e.g. TreeSet and TreeMap.

Implementation

A node in a binary tree has three attributes: the left and the right child nodes and a value. The tree has one root node. This is the structure of the binary tree, as represented in the UML class diagram below.

Construction

When adding an element to the tree, if the element is in the tree already, it is not added. The proper place to insert at is searched recursivley by calling the insert method.

<<add>>=
public void add(E element) {
    if (root == null && element != null) {
        root = new Node<E>(element);
        size++;
    } else if (element != null) {
        root = insert(root, element);
    }
}

The recursive insertion method takes two parameters: the node to search from and the element to add. It returns the node including the inserted new element. When the value is already in the tree, nothing is done. For a more sophisticated tree, we could add the new element, count frequencies, etc.

<<equal>>=
if (compare == 0) {
    return result;
}
  • In case the new value needs to be inserted in the left subtree:
<<left>>=
if (compare > 0) {
    if (result.left != null) {
        result.left = insert(result.left, value);
    } else {
        result.left = new Node<E>(value);
        size++;
    }
}
  • In case the new value needs to be inserted in the right subtree:
<<right>>=
else if (compare < 0) {
    if (result.right != null) {
        result.right = insert(result.right, value);
    } else {
        result.right = new Node<E>(value);
        size++;
    }
}
  • Search for a value in the tree, return the element if found or null if the element is not in the tree. Iteratively search a value in the tree, starting from the root, continuing either in the left or in the right subtree. Return the element, if found:
<<get>>=
public E get(E key) {
    if (root == null)
        return null;
    Node<E> node = root;
    int compareResult;
    while ((compareResult = node.value.compareTo(key)) != 0) {
        if (compareResult > 0) {
            if (node.left != null)
                node = node.left;
            else
                return null;
        } else {
            if (node.right != null)
                node = node.right;
            else
                return null;
        }
    }
    return node.value;
}

Traversal

  • Create a List from the tree and return it:
<<array>>=
public List<E> toList() {
    List<E> result = new ArrayList<E>();
    treeToList(root, result);
    return result;
}
  • Recursive preorder traversal of the tree, saving the values to the array:
<<traversal>>=
private void treeToList(Node<E> node, List<E> goal) {
    if (node != null) {
        treeToList(node.left, goal);
        goal.add(node.value);
        treeToList(node.right, goal);
    }
}

Usage

  • Sample usage: we create a tree and add a few strings. We check if it's sorted and if searching works (uses JUnit 4, requiring Java 5):
<<usage>>=
BinaryTree<String> tree = new BinaryTree<String>();
tree.add("Hanno");
tree.add("Zacharias");
tree.add("Berhard");
assertEquals(new String[]{ "Berhard", "Hanno", "Zacharias" }, tree.toList().toArray(new String[3]));
assertEquals(null, tree.get("Otto"));
assertEquals("Hanno", tree.get("Hanno"));
  • The complete program:
<<BinaryTree.java>>=
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import static org.junit.Assert.*;
import org.junit.Test;
class Node<E extends Comparable<? super E>> {
	public Node<E> left;
	public Node<E> right;
	public final E value;
	Node(E value) {
		this.value = value;
	}
	Node(Node<E> node) {
		left = node.left;
		right = node.right;
		value = node.value;
	}
}
public class BinaryTree<E extends Comparable<? super E>> {
	Node<E> root;
	int size = 0;
	int i;
	@Test
	public void testTree() {
		usage
	}
	add
	private Node<E> insert(Node<E> node, E value) {
		Node<E> result = new Node<E>(node);
		int compare = result.value.compareTo(value);
		equal
		left
		right
		return result;
	}
	get
	array
	traversal
}
Views