CS 3343/3341
 Analysis of Algorithms 
Spring 2012
  Random Binary Search Trees   
Depth of Nodes

Random Binary Search Trees, Depth of Nodes
/* treed.c: tree of random doubles
   Create a binary search tree of random
   doubles.  Then record the depth of all
   nodes, and the depth of leaf nodes.
 */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define TABSIZE 70 // size of tables
#define SAMPLESIZE 10000000 // RNGs

struct tnode {
   double d; // data, random double
   int depth; // depth of this node
   struct tnode *left;
   struct tnode *right;
};
void addtree(struct tnode *, double );
struct tnode *newnode(double );
void treeprint(struct tnode *, int);
struct tnode *talloc(void);
void tabulate(struct tnode *,
      int [], int []);
double ran(void);
double seed = 11111.0; // for ran, RNG

main(){
   struct tnode *root;
   int leaves[TABSIZE]; // depth of leaves
   int all[TABSIZE]; // depth of all nodes
   double x;
   int i;
   root = NULL;
   for (i = 0; i < SAMPLESIZE; i++) {
      x = ran();
      if (root == NULL) root = newnode(x);
      else addtree(root, x);
   }
   treeprint(root, 0); // not printing
   printf("\n");
   
   for (i = 0; i < TABSIZE; i++) {
      leaves[i] = 0;
      all[i] = 0;
   }
   tabulate(root, leaves, all);
   printf  ("  i   leaves    all\n");
   for (i = 0; i < TABSIZE; i++) {
      printf("%7i%8i\n",
        leaves[i], all[i]);
   }
   return 0;
}

/* addtree: add a node, non-recursive */
void addtree(struct tnode *p, double x){
   for (;;) {
      if ((p -> d) == x) return;// ignore
      else if ((p -> d) > x) { //go left
         if ((p -> left) == NULL) {
            p -> left = newnode(x);
            return;
         }
         else p = p -> left;
      }
      else if ((p -> d) < x) { //go right
         if ((p -> right) == NULL) {
            p -> right = newnode(x);
            return;
         }
         else p = p -> right;
      }
   }
}

/* newnode: fix up a new node */
struct tnode *newnode(double x){
   struct tnode *p = talloc();
   p -> d = x;
   p -> left = p -> right = NULL;
   p -> depth = 0;
   return p;
}

/* treeprint: rec. inorder trav. of tree.
   Record depths */
void treeprint(struct tnode *p, int dep){
   if (p != NULL) {
      treeprint(p -> left, dep + 1);
      p -> depth = dep;
      treeprint(p -> right, dep + 1);
   }
}

/* tabulate: rec. inorder tabulation */
void tabulate(struct tnode *p,
              int leaves[], int all[]){
   if (p != NULL) {
      tabulate(p -> left, leaves, all);
      // here we are at a node
      all[p -> depth]++;
      if (p -> left == NULL &&
          p -> right == NULL)
           leaves[p -> depth]++;
      tabulate(p -> right, leaves, all);
   }
}

/* talloc: make a tnode */
struct tnode *talloc(void){
   return (struct tnode *)
        malloc(sizeof(struct tnode));
}

/* the random num generator */
double ran(){
   double a = 16807.0,
          m = 2147483647.0;
   double q;
   seed = a*seed;
   q = floor(seed/m);
   seed = seed - q*m;
   return(seed/m);
}

Below, each column shows the distribution of sizes of the depth of nodes in a random binary search tree. The red entries are located at 2.5 * log2(n), where the random tree has n nodes. Your book proves (2nd ed., 12.4) that the expected "height" (what we are calling here the "maximum depth") of a random binary tree is bounded above by 3 * log2(n). The data below supports this result experimentally. (In the columns below, once there is a zero entry in a row under "all nodes", there cannot be any non-zero entries further down.)

Count of depths of nodes, in each case (leaf nodes, all nodes)
Depth100100010000 100000 = 1051000000 = 106 10000000 = 107Depth
  0
  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

  0   1
  0   2
  0   4
  3   8
  1   6
  0   7
  1  12
  3  16
 10  20
  8  14
  5   7
  1   2
  1   1
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0

  0   1
  0   2
  0   4
  0   8
  1  15
  2  26
 14  40
 12  41
  9  49
 15  75
 23  96
 33 110
 34 119
 56 130
 44 102
 36  73
 21  51
 21  38
 16  18
  2   2
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0
  0   0

   0    1
   0    2
   0    4
   0    8
   0   16
   1   31
   3   59
  13   99
  26  154
  41  215
  56  296
  71  396
 110  526
 154  677
 223  847
 286  962
 327 1009
 384 1003
 338  887
 341  776
 252  616
 229  504
 173  371
 138  256
  87  150
  43   76
  30   41
   6   11
   3    5
   2    2
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0
   0    0

    0     1
    0     2
    0     4
    0     8
    0    16
    0    32
    0    64
    4   124
   17   225
   37   392
   74   635
  140   972
  222  1426
  358  2050
  542  2817
  819  3751
 1066  4800
 1408  6028
 1973  7288
 2458  8148
 2718  8665
 3101  8847
 3114  8424
 2976  7754
 2720  6808
 2463  5743
 1950  4542
 1687  3578
 1222  2519
  826  1697
  598  1142
  403   692
  196   365
  114   207
   65   116
   40    65
   21    32
    9    13
    3     4
    0     1
    0     1
    2     2
    0     0
    0     0
    0     0
    0     0
    0     0
    0     0
    0     0
    0     0
    0     0
    0     0
    0     0
    0     0
    0     0
    0     0
    0     0
    0     0
    0     0
    0     0
    0     0
    0     0

     0      1
     0      2
     0      4
     0      8
     0     16
     0     32
     0     64
     1    127
     4    248
    13    472
    33    875
   109   1583
   270   2705
   513   4321
   938   6674
  1580   9925
  2499  14247
  3751  19771
  5231  26601
  7686  35048
 10498  44387
 13644  53967
 17356  63365
 20788  71015
 24053  76425
 26063  78837
 27155  78128
 27313  74589
 25965  68518
 24158  60906
 21658  52008
 18171  42537
 15031  33681
 11762  25414
  8696  18407
  6451  12996
  4428   8654
  2977   5547
  1765   3302
  1092   1972
   648   1154
   355    660
   215    378
   121    206
    70    106
    21     43
    14     27
     7     17
     5     13
     8     11
     2      4
     2      2
     0      0
     0      0
     0      0
     0      0
     0      0
     0      0
     0      0
     0      0
     0      0
     0      0

      0       1
      0       2
      0       4
      0       8
      0      16
      0      32
      0      64
      0     128
      2     255
      5     503
     17     975
     47    1859
    141    3491
    399    6342
    828   11023
   1912   18516
   3568   29678
   6320   45838
  10611   68605
  16836   99146
  25399  139048
  37470  189934
  53220  251549
  73133  323293
  97809  402691
 125393  484445
 154177  562960
 184931  633159
 210745  685380
 231826  717399
 246097  725604
 249815  709648
 246265  673550
 235378  619304
 217136  550523
 193010  473725
 166292  394922
 138594  318711
 111360  248712
  86550  188052
  65101  138007
  47637   98110
  33625   67342
  22956   44701
  14916   28575
   9441   17871
   5878   10969
   3649    6600
   2095    3828
   1222    2211
    725    1260
    381     674
    221     374
    106     190
     61     103
     27      49
     17      26
      8      11
      2       3
      1       1
      0       0
      0       0

  0
  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
Max
Depth		12192941 5159
Max
Depth

Revision date: 2011-10-10. (Please use ISO 8601, the International Standard Date and Time Notation.)