Binary Trees/LinkedBinTree

Linked memory structure binary tree

This page describes a Binary Trees implemented using a linked memory structure.

Java Implementation

Final implementation left a large amount of the work to the final concrete class.

public class LinkedBinTree<E> extends AbstractBinaryTree<E> {

node

To begin with, the implementation of positions in the tree was implemented as a concrete Node class, a protected static class defined within the LinkedBinTree class and used only by it.

	/////////////////////////////////////////////////
	// Node class

	/**
	 * Node class - implements a Position interface.
	 *
	 * This is a concrete implementation of 
	 * positions in a binary tree that compose 
	 * a linked binary tree.
	 */
	protected static class Node<E> implements Position<E> {
		// No need to expose things.
		// (in general, how do you test a private/protected class?)
		private E element;
		private Node<E> parent; // pointer to parent node
		private Node<E> left;  // pointer to left child
		private Node<E> right; // pointer to right child
		// constructor with element and neighbors
		public Node(E e, Node<E> above, Node<E> lefty, Node<E> righty) { 
			element = e;
			parent = above;
			left = lefty;
			right = righty;
		}
		// get methods - one for each attribute
		public E getElement() { return element; }
		public Node<E> getParent() { return parent; }
		public Node<E> getLeft() { return left; }
		public Node<E> getRight() { return right; }
		// update methods
		public void setElement(E e) { element = e; }
		public void setParent(Node<E> up) { parent = up; }
		public void setLeft(Node<E> lefty) { left = lefty; }
		public void setRight(Node<E> righty) { right = righty; }

	}

factory method

a factory method is implemented by the linked binary tree class to generate new nodes with a given element value:

	////////////////////////////////////////////
	// Utility method


	/** Factory function: make a new node storing element e. */
	protected Node<E> createNode(E e, Node<E> parent, Node<E> left, Node<E> right) { 
		return new Node<E>(e, parent, left, right);
	}

linked bin tree class

This finally brings us to methods and fields of the linked binary tree.

	////////////////////////////////////////////
	// Linked Binary Tree class:


	// Linked binary tree instance variables:
	// - protect root and size
	protected Node<E> root; // = null
	private int size; // = 0 

	// Linked binary tree default constructor - empty tree
	public LinkedBinTree() {}


	
	// useful/accessor methods

	public int size() { return size; }
	public boolean isEmpty() { return size==0; }

	// Get methods for useful nodes:
	// root, right, 
	// left, parent

	/** Returns the position of tree root. */
	public Position<E> root() {
		return root; 
	}

	/** Returns the position of p's right child. */
	public Node<E> right(Position<E> p) throws IllegalArgumentException {
		Node<E> node = validate(p);
		return node.getRight();
	}

	/** Returns the position of p's left child. */
	public Position<E> left(Position<E> p) throws IllegalArgumentException {
		Node<E> node = validate(p);
		return node.getLeft();
	}

	/** Returns the position of p's parent. */
	public Position<E> parent(Position<E> p) throws IllegalArgumentException {
		Node<E> node = validate(p);
		return node.getParent();
	}

utility methods

The following utility methods are all O(1) operations:

(see Trees/Operations_Performance for empirical verification of big-O runtime of each)

	// These are all O(1):
	// - addRoot
	// - addLeft
	// - addRight
	// - set
	// - attach


	// Add methods for useful nodes:
	// this,
	// root, right,
	// left, parent

	/** Add a root node to an empty tree. */
	public Node<E> addRoot(E e) throws IllegalStateException {
		if(!isEmpty()) {
			throw new IllegalStateException("Tree is not empty");
		}
		root = createNode(e, null, null, null);
		size = 1;
		return root;
	}

	/** Add a left child to the specified position in the tree. */
	public Node<E> addLeft(Position<E> p, E e) throws IllegalStateException { 
		Node<E> parent = validate(p);
		if(left(parent)!=null) {
			throw new IllegalStateException("Left child already exists!");
		}
		Node<E> c = createNode(e, parent, null, null);
		parent.setLeft(c);
		return c;
	}

	/** Add a right child to the specified position in the tree. */
	public Node<E> addRight(Position<E> p, E e) throws IllegalStateException { 
		Node<E> parent = validate(p);
		if(right(parent)!=null) { 
			throw new IllegalStateException("Right child already exists!");
		}
		Node<E> c = createNode(e, parent, null, null);
		parent.setRight(c);
		return c;
	}


	/** At this node, p, replace the element/data with e, and return the old/replaced value. */
	public E set(Position<E> p, E e) throws IllegalArgumentException {
		Node<E> node = validate(p);
		E temp = node.getElement();
		node.setElement(e);
		return temp;
	}

	/** Attach trees t1 and t2 as left and right subtrees of external node (leaf node) p. */
	public void attach(Position<E> p, LinkedBinTree<E> t1, LinkedBinTree<E> t2) throws IllegalArgumentException {

		Node<E> node = validate(p);
		if(isInternal(p)) {
			throw new IllegalArgumentException("Position p must be a leaf.");
		}
		size += t1.size() + t2.size();
		if(!t1.isEmpty()) {
			t1.root.setParent(node);
			node.setLeft(t1.root);
			t1.root = null;
			t1.size = 0;
		}
		if(!t2.isEmpty()) { 
			t2.root.setParent(node);
			node.setRight(t2.root);
			t2.root = null;
			t2.size = 0;
		}
	}

	/** Remove the node at position p and replace the node with its (single) child. 
	 * Throws IllegalArgumentException if 2 children. 
	 */
	public E remove(Position<E> p) throws IllegalArgumentException {
		Node<E> node = validate(p);
		if(numChildren(p)==2) { 
			throw new IllegalArgumentException("Position p cannot be removed, has two children");
		}

		// Get the correct child
		Node<E> child = ( node.getLeft()==null ? node.getRight() : node.getLeft() );
		if(child!=null) {
			// Child grand-parent becomes parent
			child.setParent(node.getParent()); 
		}
		if(node==root) { 
			// Child becomes root
			root = child; 
		} else { 
			Node<E> parent = node.getParent();
			if(node==parent.getLeft()) {
				parent.setLeft(child);
			} else {
				parent.setRight(child);
			}
		}
		size--;
		E temp = node.getElement();

		// Garbage collection
		node.setElement(null); 
		node.setLeft(null);
		node.setRight(null);

		// Defunct mode 
		node.setParent(node); 
		return temp;
	}

Iterators

	///////////////////////////////////
	// Binary Tree Iterators
	//
	// We still have not defined a positions() method.
	// We define a way to iterate over all positions 
	// in the tree here.


	// When user calls positions(), we should return an iterable container
	// with all the positions.


	/** Define a method that returns an iterable Position pointer that 
	 * iterates through the tree in the specified order. */
	public Iterable<Position<E>> positions() { return preorder(); }



	// Define some tree traversal methods below.
	// We can use whichever one we want to generate all the positions in the tree.
	// These methods should be private.


	/** Pre-order tree traversal. 
	 *
	 * This returns an iterable.
	 * Pre-order means the visit action is performed on the node
	 * before any of its children are visited. 
	 * This is a recursive method. */ 
	private Iterable<Position<E>> preorder() {
		List<Position<E>> snapshot = new LinkedList<Position<E>>();
		preorderSubtree(root(), snapshot);
		return snapshot;
	}

	/** Utility method for pre-order tree traversal. */
	private void preorderSubtree(Position<E> p, List<Position<E>> snapshot) { 
		// Base case is, no children, no loop.
		// Recursive case is, this will be called on child nodes.

		// 1. Perform visit action for Position p
		snapshot.add(p);

		// 2. Recurse through children
		for(Position<E> c : children(p)) {
			preorderSubtree(c,snapshot);
		}
	}


	/** Post-order tree traversal. 
	 *
	 * Returns an iterable.
	 *
	 * Post-order means the visit action happens on the node
	 * AFTER all the children have been visited.
	 * This is a recursive method. */
	public Iterable<Position<E>> postorder() { 
		List<Position<E>> snapshot = new LinkedList<Position<E>>();
		postorderSubtree(root(), snapshot);
		return snapshot;
	}

	/** Utility method for post-order tree traversal.  */
	private void postorderSubtree(Position<E> p, List<Position<E>> snapshot) { 
		// 1. Recurse through children
		for(Position<E> c : children(p)) {
			postorderSubtree(c,snapshot);
		}

		// 2. Perform visit action for Position p
		snapshot.add(p);
	}

	/** In-order tree traversal. */
	public Iterable<Position<E>> inorder() { 
		List<Position<E>> snapshot = new LinkedList<Position<E>>();
		inorderSubtree(root(), snapshot);
		return snapshot;
	}

	/** Utility method for in-order tree traversal.  */
	private void inorderSubtree(Position<E> p, List<Position<E>> snapshot) { 
		// 1. Recurse through left child
		inorderSubtree(left(p),snapshot);

		// 2. Perform visit action for Position p
		snapshot.add(p);

		// 3. Recurse through right child
		inorderSubtree(right(p),snapshot);
	}

	/** Breadth-first tree traversal. 
	 *
	 * Breadth first traversal/search uses a queue.
	 * Classic fencepost.
	 * */
	public Iterable<Position<E>> bft() {
		// Pseudocode:
		//
		// Fencepost algorithm:
		//
		// Plant a fencepost by starting with root node
		// Perform visit action on root node
		// Iterate over the children, add them to the queue. 
		// While queue not empty, 
		//			Pop from the queue, 
		//			perform visit action, 
		//			iterate over the children, 
		//			and add them to the queue.
		// Done.
	
		List<Position<E>> snapshot = new LinkedList<Position<E>>();

		// Use the Position interface, rather than the Node class, 
		// so that you aren't tied to a particular implementation.
		//
		// Create Grand Master Q
		Queue<Position<E>> q = new LinkedList<Position<E>>();

		// Plant a fencepost by starting with the root node.
		// Set the pointer p to root.
		// Perform action on the node, then add children of the node.
		Position<E> p = root();

		// Perform visit action on point
		snapshot.add(p);

		// Enqueue children of point in queue
		for(Position<E> c : children(p)) {
			q.add(c);
		}

		// Mind your p's and q's.
		while(!q.isEmpty()) { 
			p = q.remove();

			// Perform visit action on point p
			snapshot.add(p);

			for(Position<E> c : children(p)) {
				q.add(c);
			}
		}

		return snapshot;
	}

supporting shorthand iterator syntax

The basic and easiest way to extend shorthand iterator syntax to a class is to implement Iterator<E> that will return the elements E, rather than the less useful and protected Position<E> class, is to define a new kind of iterator, and have it privately wrap the Position iterator.

	// Finally, we can now define an iterator 
	// that iterates over the elements, rather than the positions,
	// of the Binary Tree.
	// 
	// This uses the positions() method and traversals we defined above.


	/** Element iterator class for iterating over elements, rather than positions, in a tree. */
	private class ElementIterator implements Iterator<E> {
		Iterator<Position<E>> piter;
		public ElementIterator() { 
			piter = positions().iterator();
		}
		/** Returns true if there is a next position. */
		public boolean hasNext() { return piter.hasNext(); }
		/** Returns the element at the next node in the tree. */
		public E next() { return piter.next().getElement(); }
		/** Removes the selected position from the tree - yikes. */
		public void remove() { piter.remove(); }
	}

	/** Define the Linked Binary Tree iterator to be 
	 * an element iterator, not a position iterator. */
	public Iterator<E> iterator() { return new ElementIterator(); }

Notes

An abstraction for implementing a linked binary tree is to think about the positions (or locations in the tree) independently of the nodes (or bundles of links that represent elements). This starts to make more sense when you see either an array-based implementation or an object-oriented abstract interface, but essentially we want to think of each of the potential positions of nodes in a binary tree, and number them one level at a time (1, 2 3, 4 5 6 7, etc.). This way, we have a "shadow tree" and can think about "positions" in that frame of reference.

In Java, this is performed by creating a Position interface that provides a way for abstract data structures to still define useful general functionality, but leave most of the definitions to the concrete implementation. In Python, it is performed by creating an abstract class.

Each node has pointer to left and right children, a pointer to the parent, and a pointer to the element that the node stores.

Here's what the Goodrich book says about nodes versus positions: "We define a simple, nonpublic _Node class to represent a node, and a public Position class that wraps a node. We provide a _validate utility for robustly checking the validity of a given position instance when unwrapping it, and a _make_position utility for wrapping a node as a position to return to a caller.

In Python, position class can also define __eq__ and __neq__ to get p==q or p!=q syntax

Algorithmic Analysis

The efficiency of operations are as follows:

• Single list quantities - length and is_empty - will run in O(1) time
• Accessor methods root, left, right, parent, and num_children will take O(1)
• Sibling and children methods are based on constant number of calls to other ancestors, so run in O(1) time
• Depth method runs in O(d+1) time, where d is depth of given position; height method runs in O(n) time
• add_root, add_left, add_right, replace, delete, attach each run in O(1) time

Traversal:

• pre and post order traversal, in-order traversal
• theoretically will take O(N) time if we store links and O(N log N) time if we don't (worst case: have to traverse the height of the tree log(N))