20150506 Created By BaoXinjian

一,介绍

图片 1一、摘要

对于二叉排序树来说,其有关操作与树的可观相关。设树中有N个节点,


就算各种操作的平均时间复杂度为O(logN),但当输入的行列有序时,构造出来的树是一个单分支的树,其入骨为O(N)

计算信息只怕会设有多少个版本,所以相比计算新闻之间的出入也是三个相比①般的须要

故对贰叉排序树的依次操作(如,find马克斯、contains、findMin…)的时日复杂度也落后成O(N)

  1. 能够通过脚本:
    comparing_object_statistics.sql

  2. 能够通过dbms_stats包

 

(1).
dbms_stats.diff_table_stats_in_stattab:
当前的计算音信相比备份表的总括消息

 2:实现思路

dbms_stats.diff_table_stats_in_stattab
(
    ownname => user,
    tabname => 'T',
    stattab1 => 'MYSTATS',
    statid1 => 'SET1',
    stattab1own => user,
    pctthreshold => 10
)

如今分析给定二个输入类别,根据该输入系列构造1棵二叉排序树,计算二叉排序树的平均中度。

(2).
dbms_stats.diff_table_stats_in_history:
当前的总结新闻比较历史计算音信

 

dbms_stats.diff_table_stats_in_history
(
    ownname => user,
    tabname => 'T',
    time1 => systimestamp -1,
    time2 =>null,
    pctthreshold => 10
)

有贰个随意生成一组范围为 [1,N]
的专擅数生成算法,该算法参考:

(3).
dbms_stats.diff_table_stats_in_history:当前的总括音讯相比待定的总计新闻

下一场,以下面生成的一组连串作为树的结点,插入到树中。

dbms_stats.diff_table_stats_in_history
(
  ownname => user,
  tabname => 'T',
  time_stamp => null,
  pctthreshold => 10
)

插入完毕后,总括该树的树高。

 

二叉排序树高的平分值 = 各棵树的可观之和 /
tree_numbers。比如,30棵贰叉排序树,每棵有三11个节点,树中度的平均值为
八.66666666666666六

图片 2二、解析

 


三,总结结果

运行comparing_object_statistics.sql相比三个表在分化的小运段,总结音信的距离

树的多少,               每棵树中节点的多寡,     
二叉排序树高的平分值                   完全2叉树的冲天(根的冲天为0)

Step1.
运转脚本comparing_object_statistics.sql

tree_numbers         node_numbers             averHeight

Step2. 查六柱预测比较结实

30                         31                              
8.666666666666666                   4 

 

30                         63                            
  10.833333333333334                 5

Thanks and Regards

30                        127                            
 13.366666666666667                 6

图片 3

 

45                        31                           
    8.422222222222222                   4          

45                        63                               
10.822222222222223                 5

45                       127                              
13.466666666666667                 6

 

15                       31                                 8.2        
                                   4

15                       63                                
11.266666666666667                 5

15                       127                              
12.666666666666666                 6

 

15                       99                                
11.8                                          6

30                       99                                
12.3                                          6  

45                       99                                
12.488888888888889                 6   

(11.8+12.3+12.49)/3 = 12.19666666

 

从下边能够看到,对于一样数量节点的二叉排序树和到位2叉树,前者的冲天要比后者高一倍。

 

肆,具体贯彻代码

 1 import c2.C2_2_8;
 2 
 3 public class BinarySearchTree<T extends Comparable<? super T>> {
 4 
 5     private static class BinaryNode<T> {
 6         T element;
 7         BinaryNode<T> left;
 8         BinaryNode<T> right;
 9 
10         public BinaryNode(T element) {
11             this(element, null, null);
12         }
13 
14         public BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {
15             this.element = element;
16             this.left = left;
17             this.right = right;
18         }
19 
20         public String toString() {
21             return element.toString();
22         }
23     }
24 
25     private BinaryNode<T> root;
26 
27     public BinarySearchTree() {
28         root = null;
29     }
30 
31     public void insert(T ele) {
32         root = insert(ele, root);// 每次插入操作都会'更新'根节点.
33     }
34 
35     private BinaryNode<T> insert(T ele, BinaryNode<T> root) {
36         if (root == null)
37             return new BinaryNode<T>(ele);
38         int compareResult = ele.compareTo(root.element);
39         if (compareResult > 0)
40             root.right = insert(ele, root.right);
41         else if (compareResult < 0)
42             root.left = insert(ele, root.left);
43         else
44             ;
45         return root;
46     }
47 
48     public int height() {
49         return height(root);
50     }
51 
52     private int height(BinaryNode<T> root) {
53         if (root == null)
54             return -1;// 叶子节点的高度为0,空树的高度为-1
55 
56         return 1 + (int) Math.max(height(root.left), height(root.right));
57     }
58 
59     public static void main(String[] args) {
60         BinarySearchTree<Integer> intTree = new BinarySearchTree<>();
61                 //统计每棵树有63个节点,共30棵树的平均高度
62         double averHeight = intTree.averageHeigth(30, 63, intTree);
63         System.out.println("averageheight = " + averHeight);
64     }
65 
66     public double averageHeigth(int tree_numbers, int node_numbers, BinarySearchTree<Integer> tree) {
67         int tree_height, totalHeight = 0;
68         for(int i = 1; i <= tree_numbers; i++){
69             int[] randomNumbers = C2_2_8.algorithm3(node_numbers);//每棵树随机生成一组序列,该序列作为节点的值
70             //build tree
71             for(int j = 0; j < node_numbers; j++)//将一组节点插入到树中
72             {
73                 tree.insert(randomNumbers[j]);
74                 System.out.print(randomNumbers[j] + " ");
75             }
76             System.out.println();
77             tree_height = tree.height();
78             System.out.println("height:" + tree_height);
79     
80             totalHeight += tree_height;//统计树高之和
81             tree.root = null;//for building next tree, 参考insert()实现
82         }
83     return (double)totalHeight / tree_numbers;
84     }
85 }
86