Binary Search Trees and AVL Trees
Overview:
The Binary Search Tree (BinaryTreeSearchR.java) code that we have looked at briefly in lectures and that is posted on Blackboard contains implementations of the BST, but no program to test out the implementations. You have to write this code. You also have to compare it with an AVL Tree, also covered in the same topic. The specific steps are listed below, with marks for each part in square brackets.
Task 1 (12 marks):
Write a program, in a separate class from the BST classes, that includes the following steps:
Create an initially empty BST and add at least 12 strings (e.g. names of animals, cities, other) to it. (3 marks)
Perform an in-order traversal to see the contents of the resulting tree. Is the order of the contents as you would have expected? Explain in your report. (2 marks)
Add a string that you have previously added. What will happen with it? (2 marks)
Pick any two of the strings and remove them from the tree, and perform another in-order traversal to see the contents of the revised tree. (3 marks)
Perform searches for two strings, one that is in the tree and one that is not, and display the results. (2 marks)
Task 2 (5 marks)
Perform the same set of steps, except 1.4, on the AVL Tree implementation on Blackboard note that you have to skip 1.4 because our AVL Tree implementation does not support removal of nodes). Do you get the results you expected? Explain in your report.
Task 3 (3 marks)
Are there any statistics that you can compute for both the BST and the AVL Tree that will highlight differences in how they operate? If so, calculate the statistics and explain in your report. [3]
CODE:
/** * A class that implements the ADT AVL tree by extending BinarySearchTreeR. * The remove operation is not supported. * * @author Frank M. Carrano * @version 2.0 */ public class AVLTree> extends BinarySearchTreeR implements SearchTreeInterface, java.io.Serializable { public AVLTree() { super(); } // end default constructor public AVLTree(T rootEntry) { super(rootEntry); } // end constructor
// 29.12 public T add(T newEntry) { T result = null; if (isEmpty()) setRootNode(new BinaryNode(newEntry)); else { BinaryNodeInterface rootNode = getRootNode(); result = addEntry(rootNode, newEntry); setRootNode(rebalance(rootNode)); } // end if return result; } // end add
// 29.12 /** Task: Adds newEntry to the non-empty subtree rooted at rootNode. */ private T addEntry(BinaryNodeInterface rootNode, T newEntry) { assert rootNode != null; T result = null; int comparison = newEntry.compareTo(rootNode.getData()); if (comparison == 0) { result = rootNode.getData(); rootNode.setData(newEntry); } else if (comparison < 0) { if (rootNode.hasLeftChild()) { BinaryNodeInterface leftChild = rootNode.getLeftChild(); result = addEntry(leftChild, newEntry); rootNode.setLeftChild(rebalance(leftChild)); } else rootNode.setLeftChild(new BinaryNode(newEntry)); } else { assert comparison > 0; if (rootNode.hasRightChild()) { BinaryNodeInterface rightChild = rootNode.getRightChild(); result = addEntry(rightChild, newEntry); rootNode.setRightChild(rebalance(rightChild)); } else rootNode.setRightChild(new BinaryNode(newEntry)); } // end if return result; } // end addEntry public T remove(T entry) { throw new UnsupportedOperationException(); } // end remove
// 29.11 private BinaryNodeInterface rebalance(BinaryNodeInterface nodeN) { int heightDifference = getHeightDifference(nodeN); if (heightDifference > 1) { // left subtree is taller by more than 1, // so addition was in left subtree if (getHeightDifference(nodeN.getLeftChild()) > 0) // addition was in left subtree of left child nodeN = rotateRight(nodeN); else // addition was in right subtree of left child nodeN = rotateLeftRight(nodeN); } else if (heightDifference < -1) { // right subtree is taller by more than 1, // so addition was in right subtree if (getHeightDifference(nodeN.getRightChild()) < 0) // addition was in right subtree of right child nodeN = rotateLeft(nodeN); else // addition was in left subtree of right child nodeN = rotateRightLeft(nodeN); } // end if // else nodeN is balanced return nodeN; } // end rebalance
// 29.09 /** Task: Corrects an imbalance at the node closest to a structural * change in the left subtree of the node's left child. * @param nodeN a node, closest to the newly added leaf, at which * an imbalance occurs and that has a left child. */ private BinaryNodeInterface rotateRight(BinaryNodeInterface nodeN) { BinaryNodeInterface nodeC = nodeN.getLeftChild(); nodeN.setLeftChild(nodeC.getRightChild()); nodeC.setRightChild(nodeN); return nodeC; } // end rotateRight /** Task: Corrects an imbalance at the node closest to a structural * change in the right subtree of the node's right child. * @param nodeN a node, closest to the newly added leaf, at which an * imbalance occurs and that has a right child. */ private BinaryNodeInterface rotateLeft(BinaryNodeInterface nodeN) { BinaryNodeInterface nodeC = nodeN.getRightChild(); nodeN.setRightChild(nodeC.getLeftChild()); nodeC.setLeftChild(nodeN); return nodeC; } // end rotateLeft // 29.09 /** Task: Corrects an imbalance at the node closest to a structural * change in the left subtree of the node's right child. * @param nodeN a node, closest to the newly added leaf, at which * an imbalance occurs and that has a right child. */ private BinaryNodeInterface rotateRightLeft(BinaryNodeInterface nodeN) { BinaryNodeInterface nodeC = nodeN.getRightChild(); nodeN.setRightChild(rotateRight(nodeC)); return rotateLeft(nodeN); } // end rotateRightLeft /** Task: Corrects an imbalance at the node closest to a structural * change in the right subtree of the node's left child. * @param nodeN a node, closest to the newly added leaf, at which an * imbalance occurs and that has a left child. */ private BinaryNodeInterface rotateLeftRight(BinaryNodeInterface nodeN) { BinaryNodeInterface nodeC = nodeN.getLeftChild(); nodeN.setLeftChild(rotateLeft(nodeC)); return rotateRight(nodeN); } // end rotateLeftRight
private int getHeightDifference(BinaryNodeInterface node) { BinaryNodeInterface left = node.getLeftChild(); BinaryNodeInterface right = node.getRightChild();
int leftHeight, rightHeight;
if (left == null) leftHeight = 0; else leftHeight = left.getHeight(); if (right == null) rightHeight = 0; else rightHeight = right.getHeight(); return leftHeight - rightHeight; } // end getHeightDifference /* // For testing: displays node data in level order public void display() { QueueInterface> nodeQueue = new LinkedQueue>(); BinaryNodeInterface root = getRootNode();
if (root != null) nodeQueue.enqueue(root); int nodesPerLevel = 1; while (!nodeQueue.isEmpty()) nodesPerLevel = displayNextLevel(nodesPerLevel, nodeQueue); } // end display
private int displayNextLevel(int nodesPerLevel, QueueInterface> nodeQueue) { int nextLevelCount = 0; for (int count = 0; count < nodesPerLevel; count++) { if (!nodeQueue.isEmpty()) { BinaryNodeInterface nextNode = nodeQueue.dequeue(); BinaryNodeInterface leftChild = nextNode.getLeftChild(); BinaryNodeInterface rightChild = nextNode.getRightChild(); // add to queue in order of recursive calls if (leftChild != null) { nodeQueue.enqueue(leftChild); nextLevelCount++; } // end if if (rightChild != null) { nodeQueue.enqueue(rightChild); nextLevelCount++; } // end if System.out.print(nextNode.getData() + " "); } else throw new NoSuchElementException(); } // end for System.out.println(); return nextLevelCount; } // end displayNextLevel */ } // end AVLTree
/** * A class that represents nodes in a binary tree. * * @author Frank M. Carrano * @version 2.0 */ class BinaryNode implements BinaryNodeInterface, java.io.Serializable { private T data; private BinaryNode left; private BinaryNode right; public BinaryNode() { this(null); // call next constructor } // end default constructor public BinaryNode(T dataPortion) { this(dataPortion, null, null); // call next constructor } // end constructor
public BinaryNode(T dataPortion, BinaryNode leftChild, BinaryNode rightChild) { data = dataPortion; left = leftChild; right = rightChild; } // end constructor public T getData() { return data; } // end getData public void setData(T newData) { data = newData; } // end setData public BinaryNodeInterface getLeftChild() { return left; } // end getLeftChild public BinaryNodeInterface getRightChild() { return right; } // end getRightChild
public void setLeftChild(BinaryNodeInterface leftChild) { left = (BinaryNode)leftChild; } // end setLeftChild public void setRightChild(BinaryNodeInterface rightChild) { right = (BinaryNode)rightChild; } // end setRightChild public boolean hasLeftChild() { return left != null; } // end hasLeftChild public boolean hasRightChild() { return right != null; } // end hasRightChild public boolean isLeaf() { return (left == null) && (right == null); } // end isLeaf // 26.06 public BinaryNodeInterface copy() { BinaryNode newRoot = new BinaryNode(data); if (left != null) newRoot.left = (BinaryNode)left.copy(); if (right != null) newRoot.right = (BinaryNode)right.copy(); return newRoot; } // end copy
// 26.11 public int getHeight() { return getHeight(this); // call private getHeight } // end getHeight
// 26.11 private int getHeight(BinaryNode node) { int height = 0; if (node != null) height = 1 + Math.max(getHeight(node.left), getHeight(node.right)); return height; } // end getHeight
// 26.11 public int getNumberOfNodes() { int leftNumber = 0; int rightNumber = 0; if (left != null) leftNumber = left.getNumberOfNodes(); if (right != null) rightNumber = right.getNumberOfNodes(); return 1 + leftNumber + rightNumber; } // end getNumberOfNodes } // end BinaryNode
/** * An interface for a node in a binary tree. * * @author Frank M. Carrano * @version 2.0 */ interface BinaryNodeInterface { /** Task: Retrieves the data portion of the node. * @return the object in the data portion of the node */ public T getData(); /** Task: Sets the data portion of the node. * @param newData the data object */ public void setData(T newData); /** Task: Retrieves the left child of the node. * @return the node that is this nodes left child */ public BinaryNodeInterface getLeftChild(); /** Task: Retrieves the right child of the node. * @return the node that is this nodes right child */ public BinaryNodeInterface getRightChild(); /** Task: Sets the nodes left child to a given node. * @param leftChild a node that will be the left child */ public void setLeftChild(BinaryNodeInterface leftChild); /** Task: Sets the nodes right child to a given node. * @param rightChild a node that will be the right child */ public void setRightChild(BinaryNodeInterface rightChild); /** Task: Detects whether the node has a left child. * @return true if the node has a left child */ public boolean hasLeftChild();
/** Task: Detects whether the node has a right child. * @return true if the node has a right child */ public boolean hasRightChild(); /** Task: Detects whether the node is a leaf. * @return true if the node is a leaf */ public boolean isLeaf(); /** Task: Counts the nodes in the subtree rooted at this node. * @return the number of nodes in the subtree rooted at this node */ public int getNumberOfNodes(); /** Task: Computes the height of the subtree rooted at this node. * @return the height of the subtree rooted at this node */ public int getHeight();
/** Task: Copies the subtree rooted at this node. * @return the root of a copy of the subtree rooted at this node */ public BinaryNodeInterface copy(); } // end BinaryNodeInterface
// RECURSIVE implementation of Binary Search Tree
import java.util.Iterator; /** * A class that implements the ADT binary search tree by extending BinaryTree. * * @author Frank M. Carrano * @version 2.0 */ public class BinarySearchTreeR> extends BinaryTree implements SearchTreeInterface, java.io.Serializable { private static final long serialVersionUID = -8525107615930150549L;
public BinarySearchTreeR() { super(); } // end default constructor public BinarySearchTreeR(T rootEntry) { super(); setRootNode(new BinaryNode(rootEntry)); } // end constructor public void setTree(T rootData) // disable setTree (see Segment 27.6) { throw new UnsupportedOperationException(); } // end setTree public void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree) { throw new UnsupportedOperationException(); } // end setTree // 27.09 public T getEntry(T entry) { return findEntry(getRootNode(), entry); } // end getEntry
private T findEntry(BinaryNodeInterface rootNode, T entry) { // header uses BinaryNodeInterface instead of BinaryNode // to avoid cast of values returned from getLeftChild and // getRightChild T result = null; if (rootNode != null) { T rootEntry = rootNode.getData(); if (entry.equals(rootEntry)) result = rootEntry; // entry < rootEntry) else if (entry.compareTo(rootEntry) < 0) result = findEntry(rootNode.getLeftChild(), entry); else result = findEntry(rootNode.getRightChild(), entry); } // end if return result; } // end findEntry // 27.10 public boolean contains(T entry) { return getEntry(entry) != null; } // end contains // 27.16 public T add(T newEntry) { T result = null; if (isEmpty()) setRootNode(new BinaryNode(newEntry)); else result = addEntry(getRootNode(), newEntry); return result; } // end add
// 27.15 /** Task: Adds newEntry to the nonempty subtree rooted at rootNode.*/ private T addEntry(BinaryNodeInterface rootNode, T newEntry) { assert rootNode != null; T result = null; int comparison = newEntry.compareTo(rootNode.getData()); if (comparison == 0) // newEntry matches entry in root { result = rootNode.getData(); rootNode.setData(newEntry); } else if (comparison < 0) // newEntry < entry in root { if (rootNode.hasLeftChild()) result = addEntry(rootNode.getLeftChild(), newEntry); else rootNode.setLeftChild(new BinaryNode(newEntry)); } else // newEntry > entry in root { assert comparison > 0; if (rootNode.hasRightChild()) result = addEntry(rootNode.getRightChild(), newEntry); else rootNode.setRightChild(new BinaryNode(newEntry)); } // end if return result; } // end addEntry
// 27.29 public T remove(T entry) { ReturnObject oldEntry = new ReturnObject(null); BinaryNodeInterface newRoot = removeEntry(getRootNode(), entry, oldEntry); setRootNode(newRoot); return oldEntry.get(); } // end remove
// 27.30 /** Task: Removes an entry from the tree rooted at a given node. * @param rootNode a reference to the root of a tree * @param entry the object to be removed * @param oldEntry an object whose data field is null * @return the root node of the resulting tree; if entry matches * an entry in the tree, oldEntry's data field is the entry * that was removed from the tree; otherwise it is null */ private BinaryNodeInterface removeEntry(BinaryNodeInterface rootNode, T entry, ReturnObject oldEntry) { if (rootNode != null) { T rootData = rootNode.getData(); int comparison = entry.compareTo(rootData); if (comparison == 0) // entry == root entry { oldEntry.set(rootData); rootNode = removeFromRoot(rootNode); } else if (comparison < 0) // entry < root entry { BinaryNodeInterface leftChild = rootNode.getLeftChild(); BinaryNodeInterface subtreeRoot = removeEntry(leftChild, entry, oldEntry); rootNode.setLeftChild(subtreeRoot); } else // entry > root entry { BinaryNodeInterface rightChild = rootNode.getRightChild(); rootNode.setRightChild(removeEntry(rightChild, entry, oldEntry)); } // end if } // end if return rootNode; } // end removeEntry
// 27.32 /** Task: Removes the entry in a given root node of a subtree. * @param rootNode the root node of the subtree * @return the root node of the revised subtree */ private BinaryNodeInterface removeFromRoot(BinaryNodeInterface rootNode) { // Case 1: rootNode has two children if (rootNode.hasLeftChild() && rootNode.hasRightChild()) { // find node with largest entry in left subtree BinaryNodeInterface leftSubtreeRoot = rootNode.getLeftChild(); BinaryNodeInterface largestNode = findLargest(leftSubtreeRoot);
// replace entry in root rootNode.setData(largestNode.getData()); // remove node with largest entry in left subtree rootNode.setLeftChild(removeLargest(leftSubtreeRoot)); } // end if // Case 2: rootNode has at most one child else if (rootNode.hasRightChild()) rootNode = rootNode.getRightChild(); else rootNode = rootNode.getLeftChild(); // Assertion: if rootNode was a leaf, it is now null return rootNode; } // end removeEntry
// 27.33 /** Task: Finds the node containing the largest entry in a * given tree. * @param rootNode the root node of the tree * @return the node containing the largest entry in the tree */ private BinaryNodeInterface findLargest(BinaryNodeInterface rootNode) { if (rootNode.hasRightChild()) rootNode = findLargest(rootNode.getRightChild()); return rootNode; } // end findLargest
// 27.34 /** Task: Removes the node containing the largest entry in a * given tree. * @param rootNode the root node of the tree * @return the root node of the revised tree */ private BinaryNodeInterface removeLargest(BinaryNodeInterface rootNode) { if (rootNode.hasRightChild()) { BinaryNodeInterface rightChild = rootNode.getRightChild(); BinaryNodeInterface root = removeLargest(rightChild); rootNode.setRightChild(root); } else rootNode = rootNode.getLeftChild(); return rootNode; } // end removeLargest
private class ReturnObject implements java.io.Serializable { private T item; private ReturnObject(T entry) { item = entry; } // end constructor public T get() { return item; } // end get
public void set(T entry) { item = entry; } // end set } // end ReturnObject } // end BinarySearchTreeR
/** * A class that implements the ADT binary tree. * * @author Frank M. Carrano * @version 2.0 */ public class BinaryTree implements BinaryTreeInterface, java.io.Serializable { private BinaryNodeInterface root; public BinaryTree() { root = null; } // end default constructor public BinaryTree(T rootData) { root = new BinaryNode(rootData); } // end constructor public BinaryTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { privateSetTree(rootData, leftTree, rightTree); } // end constructor public void setTree(T rootData) { root = new BinaryNode(rootData); } // end setTree public void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree) { privateSetTree(rootData, (BinaryTree)leftTree, (BinaryTree)rightTree); } // end setTree
// 26.08 private void privateSetTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { root = new BinaryNode(rootData); if ((leftTree != null) && !leftTree.isEmpty()) root.setLeftChild(leftTree.root); if ((rightTree != null) && !rightTree.isEmpty()) { if (rightTree != leftTree) root.setRightChild(rightTree.root); else root.setRightChild(rightTree.root.copy()); } // end if if ((leftTree != null) && (leftTree != this)) leftTree.clear(); if ((rightTree != null) && (rightTree != this)) rightTree.clear(); } // end privateSetTree
private BinaryNode copyNodes() // not essential { return (BinaryNode)root.copy(); } // end copyNodes
// 26.09 public T getRootData() { T rootData = null; if (root != null) rootData = root.getData(); return rootData; } // end getRootData
// 26.09 public boolean isEmpty() { return root == null; } // end isEmpty
// 26.09 public void clear() { root = null; } // end clear
// 26.09 protected void setRootData(T rootData) { root.setData(rootData); } // end setRootData
// 26.09 protected void setRootNode(BinaryNodeInterface rootNode) { root = rootNode; } // end setRootNode
// 26.09 protected BinaryNodeInterface getRootNode() { return root; } // end getRootNode
// 26.10 public int getHeight() { return root.getHeight(); } // end getHeight
// 26.10 public int getNumberOfNodes() { return root.getNumberOfNodes(); } // end getNumberOfNodes
// 26.12 public void inorderTraverse() { inorderTraverse(root); } // end inorderTraverse
private void inorderTraverse(BinaryNodeInterface node) { if (node != null) { inorderTraverse(node.getLeftChild()); System.out.println(node.getData()); inorderTraverse(node.getRightChild()); } // end if } // end inorderTraverse } // end BinaryTree
/** M Madden, Feb 2008: * Class to demonstrate the use of BinaryTree code. * Based on code by Carrano & Savitch. * @author Michael Madden. */
public class BinaryTreeDemo { public static void main(String[] args) { // Create a tree System.out.println("Constructing a test tree ..."); BinaryTree testTree = new BinaryTree(); createTree1(testTree); // Display some statistics about it System.out.println(" Some statistics about the test tree ..."); displayStats(testTree); // Perform in-order traversal System.out.println(" In-order traversal of the test tree, printing each node when visiting it ..."); testTree.inorderTraverse(); } // end of main public static void createTree1(BinaryTree tree) { // To create a tree, build it up from the bottom: // create subtree for each leaf, then create subtrees linking them, // until we reach the root. System.out.println(" Creating a treee that looks like this: "); System.out.println(" A "); System.out.println(" / \\ "); // '\\' is the escape character for backslash System.out.println(" B C "); System.out.println(" / \\ / \\"); System.out.println("D E F G "); System.out.println();
// First the leaves BinaryTree dTree = new BinaryTree(); dTree.setTree("D"); // neater to use the constructor the initialisation ... BinaryTree eTree = new BinaryTree("E"); BinaryTree fTree = new BinaryTree("F"); BinaryTree gTree = new BinaryTree("G");
// Now the subtrees joining leaves: BinaryTree bTree = new BinaryTree("B", dTree, eTree); BinaryTree cTree = new BinaryTree("C", fTree, gTree);
// Now the root tree.setTree("A", bTree, cTree); } // end createTree1 public static void displayStats(BinaryTree tree) { if (tree.isEmpty()) System.out.println("The tree is empty"); else System.out.println("The tree is not empty"); System.out.println("Root of tree is " + tree.getRootData()); System.out.println("Height of tree is " + tree.getHeight()); System.out.println("No. of nodes in tree is " + tree.getNumberOfNodes()); } // end displayStats }
/** * An interface for the ADT binary tree. * * @author Frank M. Carrano * @version 2.0 */ public interface BinaryTreeInterface extends TreeInterface { /** Task: Sets an existing binary tree to a new one-node binary tree. * @param rootData an object that is the data in the new trees root */ public void setTree(T rootData); /** Task: Sets an existing binary tree to a new binary tree. * @param rootData an object that is the data in the new trees root * @param leftTree the left subtree of the new tree * @param rightTree the right subtree of the new tree */ public void setTree(T rootData, BinaryTreeInterface leftTree, BinaryTreeInterface rightTree); } // end BinaryTreeInterface
// 27.02 import java.util.Iterator; /** * An interface for a search tree. * * @author Frank M. Carrano * @version 2.0 */ public interface SearchTreeInterface> extends TreeInterface { /** Task: Searches for a specific entry in the tree. * @param entry an object to be found * @return true if the object was found in the tree */ public boolean contains(T entry); /** Task: Retrieves a specific entry in the tree. * @param entry an object to be found * @return either the object that was found in the tree or * null if no such object exists */ public T getEntry(T entry); /** Task: Adds a new entry to the tree. * If the entry matches an object that exists in the tree * already, replaces the object with the new entry. * @param newEntry an object to be added to the tree * @return either null if newEntry was not in the tree already, or * an existing entry that matched the parameter newEntry * and has been replaced in the tree */ public T add(T newEntry); /** Task: Removes a specific entry from the tree. * @param entry an object to be removed * @return either the object that was removed from the tree or * null if no such object exists */ public T remove(T entry); } // end SearchTreeInterface
/** * An interface for basic operations of a tree. * * @author Frank M. Carrano * @version 2.0 */ public interface TreeInterface { public T getRootData(); public int getHeight(); public int getNumberOfNodes(); public boolean isEmpty(); public void clear(); } // end TreeInterface
