CS1103 Exercise Unit 3 - A binary sort tree created by inserting items in a random order is approximately balanced

Posted on | In | Views
CS1103 Exercise Unit 3.

Questions

If the binary sort tree is created by inserting items in a random order, there is a high probability that the tree is approximately balanced. Please do an experiment to test whether it is true.

1. Codes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
/**
 * This program is to test the conclusion:
 * if the binary sort tree is created by inserting items in a random order,
 * there is a high probability that the tree is approximately balanced.
 */
public class ApproximatelyBalancedBinaryTree {
    /**
     * Pointer to the root node in a binary tree.
     */
    private static TreeNode root;

    /**
     * An object of type TreeNode represents one node in a binary tree of strings.
     */
    private static class TreeNode {
        double item;      // The data in this node.
        TreeNode left;    // Pointer to left subtree.
        TreeNode right;   // Pointer to right subtree.

        TreeNode(double num) {
            // Make a node containing the specified real number.
            // Note that left and right pointers are initially null.
            item = num;
        }
    }

    /**
     * Count the leaves in the tree
     */
    private static int countLeaves(TreeNode node) {
        if (node == null) {
            return 0; // The tree is empty, so it contains no leaves
        } else if (node.left == null && node.right == null) {
            return 1; // The tree contains only one node, which is a leaf.
        } else {
            return countLeaves(node.left) + countLeaves(node.right);
        }
    }


    /**
     * Find the sum of the depths of all the leaves
     */
    private static int sumOfDepth(TreeNode node, int depth) {
        if (node == null) {
            return 0; // The tree is empty, so the sum of the depth is 0.
        } else if (node.left == null && node.right == null) {
            return depth; // the node is a leaf, just return its depth
        } else {
            return sumOfDepth(node.left, depth + 1) + sumOfDepth(node.right, depth + 1);
        }
    }


    /**
     * find the maximum depth of the leaves
     */
    private static int maxDepth(TreeNode node, int depth) {
        if (node == null) {
            return 0; // The tree is empty, the depth is 0
        } else if (node.left == null && node.right == null) {
            return depth; // the node is a leaf, so just return the depth
        } else {
            int leftMaxDepth = maxDepth(node.left, depth + 1);
            int rightMaxDepth = maxDepth(node.right, depth + 1);
            return Math.max(leftMaxDepth, rightMaxDepth);
        }
    }


    /**
     * Add the item to the binary sort tree to which the global variable "root" refers.
     */
    private static void treeInsert(double newItem) {
        if (root == null) {
            // The tree is empty.  Set root to point to a new node containing
            // the new item.  This becomes the only node in the tree.
            root = new TreeNode(newItem);
            return;
        }
        TreeNode runner;  // Runs down the tree to find a place for newItem.
        runner = root;   // Start at the root.
        while (true) {
            if (newItem < runner.item) {
                // Since the new item is less than the item in runner,
                // it belongs in the left subtree of runner.  If there
                // is an open space at runner.left, add a new node there.
                // Otherwise, advance runner down one level to the left.
                if (runner.left == null) {
                    runner.left = new TreeNode(newItem);
                    return;  // New item has been added to the tree.
                } else {
                    runner = runner.left;
                }
            } else {
                // Since the new item is greater than or equal to the item in
                // runner it belongs in the right subtree of runner.  If there
                // is an open space at runner.right, add a new node there.
                // Otherwise, advance runner down one level to the right.
                if (runner.right == null) {
                    runner.right = new TreeNode(newItem);
                    return;  // New item has been added to the tree.
                } else {
                    runner = runner.right;
                }
            }
        } // end while
    }  // end treeInsert()


    /**
     * Return true if item is one of the items in the binary
     * sort tree to which root points.  Return false if not.
     */
    static boolean treeContains(TreeNode root, double item) {
        if (root == null) {
            // Tree is empty, so it certainly doesn't contain item.
            return false;
        } else if (item == root.item) {
            // Yes, the item has been found in the root node.
            return true;
        } else if (item < root.item) {
            // If the item occurs, it must be in the left subtree.
            return treeContains(root.left, item);
        } else {
            // If the item occurs, it must be in the right subtree.
            return treeContains(root.right, item);
        }
    }  // end treeContains()


    /**
     * Count the nodes in the binary tree.
     *
     * @param node A pointer to the root of the tree.  A null value indicates
     *             an empty tree.
     * @return the number of nodes in the tree to which node points.  For an
     * empty tree, the value is zero.
     */
    private static int countNodes(TreeNode node) {
        if (node == null) {
            // Tree is empty, so it contains no nodes.
            return 0;
        } else {
            // Add up the root node and the nodes in its two subtrees.
            int leftCount = countNodes(node.left);
            int rightCount = countNodes(node.right);
            return 1 + leftCount + rightCount;
        }
    } // end countNodes()


    public static void main(String[] args) {
        int count = 0; // count the nodes in the tree
        int numOfNodes = 1023; // the total number of nodes in the tree

        // add 1023 distinct real numbers to the tree
        while (true) {
            double realNumber = Math.random(); // generate a real number
            if (count >= numOfNodes) {
                break;
            } else if (!treeContains(root, realNumber)) {
                treeInsert(realNumber);  // Add a real number to the tree.
                count++;
            }
        }

        // the nodes in the tree
        System.out.println("The nodes in the tree: " + countNodes(root));

        // the leaves in the tree
        int leaves = countLeaves(root);
        System.out.println("the leaves in the tree: " + leaves);

        // the maximum depth of all the leaves
        int maxDepth = maxDepth(root, 0);
        System.out.println("the max depth: " + maxDepth);

        // the average depth of all the leaves in the tree
        int sumOfDepth = sumOfDepth(root, 0);
        double averageDepth = (double) sumOfDepth / leaves;
        System.out.println("the average depth: " + averageDepth);
    }

} // end class ApproximatelyBalancedBinaryTree

2. Outputs

1
2
3
4
5
6
The nodes in the tree: 1023
the leaves in the tree: 340
the max depth: 19
the average depth: 11.702941176470588

Process finished with exit code 0

​

This is the ending, thanks for reading.