1CS211, Lecture 19 Binary Search TreesI think that I shall never scan A tree as lovely asa man. . . . . A tree depicts divinest plan, ButGod himself lives in a man. Joyce KilmerI like trees because they seem more resigned tothe way they have to live than other things do.Author: Willa Sibert CatherReadings: Weiss,chapter 19,sections 19.1--19.2.2Binary search treesYou know that searching is faster in a sorted array than ina nonsorted array. If the data set has size n:On the average: O(n) for a nonsorted array.Always: O(log n) for a sorted arrayOn the average, O(n) for a binary tree.We now see how to restrict trees so that they can besearched in average time O(log n).547 823Binary search treeBinary search tree: a binary treein which, for each node n,• All the values in subtree n.leftare <= the value in node n• All the values in subtreen.right are >= the value in noden.54247698binary search tree54267698not a binary search tree:the 6 is > 5.4Binary treeBinary tree: tree in which each node can have atmost two children.Redefinition of binary tree to allow empty treeA binary tree is either(1) Ø (the empty binary tree)or(2) a root node (with a value), a left binary tree, a right binary treeBinary treetree with root 4 has an empty right binary treetree with root 2 has an empty left binary treetree with root 7 has two empty children.547 825Class for binary search tree nodes/** An instance is a nonempty binary search tree */public class BSTNode { / ** class invariant: the left and right subtrees satisfy the binary search tree property */ private Object datum; private BSTNode left; private BSTNode right; /** Constructor: a one-node tree with root value ob */ public BSTNode(Object ob) { datum= ob; } **getter and setter methods for all three fields**}6Method toString/** An instance is a nonempty binary search tree */public class BSTNode { /** = nodes of tree, separated by , */ public String toString() { String result= “”; if (left != null) { result= result + left.toString() + ", "; } result= result + datum; if (right != null) { result= result + ", " + right.toString(); } return result; }}7Searching a binary search tree for a value/** = a node of tree t that contains value x (null if none) */public BSTNode elementAt (Comparable x, BSTNode t) { BSTNode t1= t; // invariant: x is in t iff x is in tree t1 while (t1 != null) {if (x.compareTo(t1.datum) == 0) return t1;if (x.compareTo(t1.datum) < 0) t1= t1.left;else t1= t1.right; } return null;}t0left datum right54247698t8Searching a binary search tree for a value(using recursion)/** = a node of tree t that contains value x (null if none) */public BSTNode elementAt (Comparable x, BSTNode t) { if (t == null) return null; if (x.compareTo(t.datum) == 0) return t; if (x.compareTo(t.datum) < 0)return elementAt(x, t.left); return elementAt(x, t.right);}t0left datum right542476989/** Insert item x into tree t and return the new root */public BSTNode insert (Comparable x, BSTNode t) { if (t == null) { t= new BSTNode(x); return t; } if (x.compareTo(t.datum) <= 0) {t.left= insert(x, t.left);return t; } // x belongs in right subtree t.right= insert(x, t.right); return t;}t0left datum right5324769857698Duplicates are allowed. They arearbitrarily put in the left subtree. Ifduplicates not allowed, have methodthrow an exception if x already in t10 /** = a tree with Integer values given by array b */ public static BSTNode newTree(int[] b) { BSTNode root= null; for (int k= 0; k != b.length; k= k+1) { root= insert(new Integer(b[k]), root); } return root;}t0left datum right53247698A method to create binary trees easily11Searching a binary search tree for the minimum/** = a node that contains the minimum value in tree t. Throw IllegalArgumentException if t == null) */public BSTNode findMin (BSTNode t) { if (t == null){ throw new IllegalArgumentException(); } BSTNode t1= t; // inv: the min of tree t is the min of tree t1 while (t1.left != null) {t1= t1.left; } return t1;}t0left datum right54247698You write findMax(BTNode)12/** Remove the min node from tree t and return the root of the new tree. Throw IllegalArgumentException if t == null */public BSTNode removeMin (BSTNode t) { if (t == null){ throw new IllegalArgumentException(); } if (t.left == null){ return t.right; } t.left= removeMin(t.left); return t;}t0left datum right54247698You write removeMax(BTNode)5769813/** Remove node with item x from t; return root of new tree. Throw IllegalArgumentException if x is not in t */public BSTNode remove (Comparable x, BSTNode t) { if (t == null){ throw new IllegalArgumentException(x.toString()); } if (x.compareTo(x, t.datum) < 0) { t.left= remove(x, t.left); return t; } if (x.compareTo(t.datum) > 0) { t.right= remove(t.right); return t; } // { x is the value in root t } if (t.right != null) { t.datum= findMin(t.right).datum; t.right= removeMin(t.right); return t; } // { t.right is null } return t.left;}t0left datum right532476985769814Order statisticsA binary search tree can be viewed as an ordered list.Suppose we want to find the kth smallest element.2 3 4 6 7 8 9 10first third seventh eighthIf we know the size of each tree, we can findthe kth smallest element quite quickly.63248710934821Extend class to have a field that gives the size.15public class BSTNodeSize extends BSTNode { private int size; // Number of nodes in tree // Constructor: a one-node tree with value ob public BSTNodeSize(Object ob) { super(ob); size= 1; }}BSTNode with size6324871093482111116/** = rank k node of tree t. k < 0 or k > size of tree, throw exception */public BSTNodeSize findKth (int k, BSTNodeSize t) { if (t == null) throw new IllegalArgumentException(); int lsize= 0; // size of left subtree if (t.left != null) lsize= ((BSTNodeSize)(t.left)).size; if (k = lsize + 1) return t; if (k <= lsize) return findKth(k, (BSTNodeSize)t.left);return findKth(k – lsize – 1, (BSTNodeSize)t.right);}Find kth smallest value6324871093482111117/** Remove the min node from tree t and return the root of the new tree. Throw IllegalArgumentException if t == null */public BSTNodeSize removeMin (BSTNodeSize
View Full Document
Unlocking...