Question

Write a program that builds t BSTs by inserting N random keys into an initially empty tree, and then finds the tree height for N =100, 500 and 1000; and t =5, 10, 15. Find the average height of binary search trees for each pair of values of t and N. Decide what you will do with duplicates and explain what you did to handle duplicates.

Answer 1

/6 else terminated> BstDemo [Java Application CProgram FilesJavajdk1.8.0 73binavaw.exe (A For N-100 keys in 5 trees, Average height 13.4 For N-100 keys in 10 trees, Average height-13.4 For N-100 keys in 15 trees, Average height-13.066666666666666 For N-500 keys in 5 trees, Average height-20.0 For N-500 keys in 10 trees, Average height-19.6 For N 500 keys in 15 trees, Average height 18.933333333333334 For N-1000 keys in 5 trees, Average height-21.4 For N-1000 keys in 10 trees, Average height 22.2 For N-1000 keys in 15 trees, Average height-21.8 left.add(value); return; 78 79 80 81 82 83 public int getHeight) 84 85 86 87 // You may want to implement this 88 private int getHeight (BstNode entry) return getHeight (this); if (entrynull) ( 90 91 92 93 94 return ; return 1 Math. max(getHeight(entry.left), getHeight(entry.right); 96 class BstDemo 97 public static void main (String[] args) 98 int N]-100, 500, 1000); int t]-15, 10, 15); 101 102 103 104 185 106 for(int count: N) for(int numTrees: t) double totalHeight 0; for(int i-0; i<numTrees; itt) t Bst tree new Bst); for(int k-0; k<count; k++) [ 07 108 109 110 tree.add ((int) (Math.random) (count 10))); totalHeight + tree.height); double avgHeight - totalHeightnumTrees; 112 113 114 115 116 117) 118 System.out.println("For N-" count " keys in "numTrees " trees,

package jan18;

class Bst {
        private BstNode root;

        public void add(int value) {
                if (root == null) {
                        root = new BstNode(value);
                } else {
                        root.add(value);
                }
        }
        
        public int height() {
                if (root == null) {
                        return 0;
                } else {
                        return root.getHeight();
                }
        }
}

class BstNode {
        private int data;
        private BstNode left;
        private BstNode right;

        public BstNode(int dataToSet) {
                data = dataToSet;
                left = null;
                right = null;
        }

        public void setData(int dataToSet) {
                data = dataToSet;
        }

        public void setLeft(BstNode linkToSet) {
                left = linkToSet;
        }

        public void setRight(BstNode linkToSet) {
                right = linkToSet;
        }

        public int getData() {
                return data;
        }

        public BstNode getLeft() {
                return left;
        }

        public BstNode getRight() {
                return right;
        }

        public void add(int value) {
                if (value == data) {
                        return;
                }
                if (value > data) {
                        if (right == null) {
                                BstNode toAdd = new BstNode(value);
                                right = toAdd;
                                return;
                        } else {
                                right.add(value);
                                return;
                        }
                } else {
                        if (left == null) {
                                BstNode toAdd = new BstNode(value);
                                left = toAdd;
                                return;
                        } else {
                                left.add(value);
                                return;
                        }
                }
        }
        
        public int getHeight() {
                return getHeight(this);
        }

        // You may want to implement this
        private int getHeight(BstNode entry) {
                if (entry == null) {
                        return 0;
                }
                return 1 + Math.max(getHeight(entry.left), getHeight(entry.right));
        }
}

class BstDemo {
        public static void main(String[] args) {
                int N[] = {100, 500, 1000};
                int t[] = {5, 10, 15};
                
                for(int count: N) {
                        for(int numTrees: t) {

                                double totalHeight = 0;
                                for(int i=0; i<numTrees; i++) {
                                        Bst tree = new Bst();
                                        for(int k=0; k<count; k++) {
                                                tree.add((int) (Math.random() * (count * 10)));
                                        }
                                        totalHeight += tree.height();
                                }
                                double avgHeight = totalHeight / numTrees;
                                
                                System.out.println("For N=" + count + " keys in " + numTrees + " trees, Average height=" + avgHeight);
                        }
                }
        }
}

We have ignored duplicates, since BST do not support duplicates.