二分查找判定树的RHC构造法

RHC construction method for binary search decision tree

传统面向过程的二分查找判定树构造方法复杂且工作量大。通过分析二分查找判定树的特点,提出倾斜二叉树的定义和构造方法,并进行了相关性质的探究。利用逆向哈弗曼编码(Reversed Huffman Coding,RHC)和二分查找判定树的中序有序性,提出了一种面向计算的二分查找判定树构造法——RHC构造法。结合性能分析、对比,RHC构造法比传统面向过程的方法速度更快、效率更高。

The traditional process-oriented binary search decision tree construction method is complex and the workload is large. We analyze the features of the binary search decision tree,define the bias binary tree and put forward its construction method,as well as discuss the related properties. Based on the Reversed Huffman Coding RHC and the fact that the inorder traversal of binary search decision tree is ordered,this paper presents a computational-oriented method—RHC construction method—for constructing the binary search decision tree. Combined with performance analysis and comparison,RHC construction method is faster and more efficient than traditional process-oriented method.