Topic 18 Binary Search TreesThe Problem with Linked ListsBinary Search TreesAttendance Question 1Implementation of Binary NodeSample InsertionWorst Case PerformanceMore on ImplementationAdd an Element, RecursiveAdd an Element, IterativeAttendance Question 2Performance of Binary TreesRemove an ElementProperties of a BSTUsing PolymorphismBST InterfaceEmptyBSTNon Empty BST – Part 1Non Empty BST – Part 2CS 307 Fundamentals of Computer Science1Topic 18 Binary Search Trees"Yes. Shrubberies are my trade. I am a shrubber. My name is 'Roger the Shrubber'. I arrange, design, and sell shrubberies."-Monty Python and The Holy GrailCS 307 Fundamentals of Computer Science2The Problem with Linked ListsAccessing a item from a linked list takes O(N) time for an arbitrary elementBinary trees can improve upon this and reduce access to O( log N ) time for the average caseExpands on the binary search technique and allows insertions and deletionsWorst case degenerates to O(N) but this can be avoided by using balanced trees (AVL, Red-Black)CS 307 Fundamentals of Computer Science3Binary Search TreesA binary tree is a tree where each node has at most two children, referred to as the left and right childA binary search tree is a binary tree in which every node's left subtree holds values less than the node's value, and every right subtree holds values greater than the node's value. A new node is added as a leaf. parentleft childright childroot1711 19< >Attendance Question 1After adding N distinct elements in random order to a Binary Search Tree what is the expected height of the tree?A. O(N1/2)B. O(logN)C. O(N)D. O(NlogN)E. O(N2)CS 307 Fundamentals of Computer Science4CS 307 Fundamentals of Computer Science5Implementation of Binary Nodepublic class BSTNode{ private Comparable myData;private BSTNode myLeft;private BSTNode myRightC;public BinaryNode(Comparable item){ myData = item; }public Object getValue(){ return myData; }public BinaryNode getLeft(){ return myLeft; }public BinaryNode getRight(){ return myRight; }public void setLeft(BSTNode b){ myLeft = b; }// setRight not shown}CS 307 Fundamentals of Computer Science6Sample Insertion100, 164, 130, 189, 244, 42, 141, 231, 20, 153(from HotBits: www.fourmilab.ch/hotbits/)If you insert 1000 random numbers into a BST usingthe naïve algorithm what is the expected height of thetree? (Number of links from root to deepest leaf.)CS 307 Fundamentals of Computer Science7Worst Case PerformanceIn the worst case a BST can degenerate into a singly linked list. Performance goes to O(N)2 3 5 7 11 13 17CS 307 Fundamentals of Computer Science8More on ImplementationMany ways to implement BSTsUsing nodes is just one and even then many options and choicespublic class BinarySearchTree{ private TreeNode root;private int size;public BinarySearchTree(){ root = null;size = 0;}CS 307 Fundamentals of Computer Science9Add an Element, RecursiveCS 307 Fundamentals of Computer Science10Add an Element, IterativeAttendance Question 2What is the best case and worst case Big O to add N elements to a binary search tree?Best WorstA. O(N) O(N)B. O(NlogN) O(NlogN)C. O(N) O(NlogN)D. O(NlogN) O(N2)E. O(N2) O(N2)CS 307 Fundamentals of Computer Science11CS 307 Fundamentals of Computer Science12Performance of Binary TreesFor the three core operations (add, access, remove) a binary search tree (BST) has an average case performance of O(log N)Even when using the naïve insertion / removal algorithmsno checks to maintain balancebalance achieved based on the randomness of the data insertedCS 307 Fundamentals of Computer Science13Remove an ElementThree cases–node is a leaf, 0 children (easy)–node has 1 child (easy)–node has 2 children (interesting)CS 307 Fundamentals of Computer Science14Properties of a BSTThe minimum value is in the left most nodeThe maximum value is in the right most node–useful when removing an element from the BSTAn inorder traversal of a BST provides the elements of the BST in ascending orderCS 307 Fundamentals of Computer Science15Using PolymorphismExamples of dynamic data structures have relied on null terminated ends.–Use null to show end of list, no childrenAlternative form–use structural recursion and polymorphismCS 307 Fundamentals of Computer Science16BST Interfacepublic interface BST { public int size(); public boolean contains(Comparable obj); public boolean add(Comparable obj);}CS 307 Fundamentals of Computer Science17EmptyBSTpublic class EmptyBST implements BST { private static EmptyBST theOne = new EmptyBST(); private EmptyBST(){} public static EmptyBST getEmptyBST(){ return theOne; } public NEBST add(Comparable obj) { return new NEBST(obj); } public boolean contains(Comparable obj) { return false; } public int size() { return 0; }}CS 307 Fundamentals of Computer Science18Non Empty BST – Part 1public class NEBST implements BST { p rivate Comparable data; p rivate BST left; p rivate BST right; p ublic NEBST(Comparable d){ data = d; right = EmptyBST.getEmptyBST(); left = EmptyBST.getEmptyBST(); } p ublic BST add(Comparable obj) { int val = obj.compareTo( data ); if( val < 0 ) left = left.add( obj ); else if( val > 0 ) right = right.add( obj ); return this; }CS 307 Fundamentals of Computer Science19Non Empty BST – Part 2public boolean contains(Comparable obj){ int val = obj.compareTo(data); if( val == 0 ) return true; else if (val < 0) return left.contains(obj); else return right.contains(obj); } p ublic int size() { return 1 + left.size() + right.size();
View Full Document
Unlocking...