Top-down Algorithms for Constructing Nearly Optimal Binary Search Trees

スポンサーリンク

概要

• 論文の詳細を見る

• A binary search tree is an important technique for organizing large files. There are several conventional methods for constructing an optimal (or a nearly optimal) binary search tree. But these methods are time-consuming or space consuming and so not applicable to practical problems involving several hundreds of keys. In this paper, we present some methods for constructing a nearly-optimal binary search tree. Our algorithms consist of heuristic top-down methods and Knuth's "Algorithm K" (dynamic programming method) and take time proportional to N^<3/2> (N is the number of keys) and storage proportional to N. Experimental results show good performances of our methods. The nearly-optimal trees can be expected to suppress the increase of average search length within 0.1% of that of optimal tree.

• 一般社団法人情報処理学会の論文

著者

• Fukumura Teruo

  Faculty Of Engineering Nagoya University

• YOSHIDA Yuuji

  Computation Center, Nagoya University

• NISHIKAWA Yasuyuki

  TOYOTA MOTOR Co., Ltd.

• Yoshida Yuuji

  Computation Center Nagoya University

• Nishikawa Yasuyuki

  Toyota Motor Co. Ltd.

関連論文

• Algorithms for Formula Manipulation Based upon Hashing Technique and their Applications to Pseudo-Boolean Programming
• Top-down Algorithms for Constructing Nearly Optimal Binary Search Trees
• Virtua1 Computer VC/S for String Manipulation and the Implementation of SNOBOL 3 on It

スポンサーリンク