著者

大西建輔 星 守

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2001, no.93, pp.67-74, 2001-09-25

---

確率分布を与えた場合に路長の期待値を最適とする二分探索木 最適木と呼ぶ が二分木の内点数の二乗で計算できることは Kunthによりすでに証明がなされている. 前回の発表では、確率分布のパラメタ空間をそれぞれの最適木に対応する領域に分割する手法について述べた.本稿では、どのような二分探索木でも 最適木となるりうるのか?これらの領域がどのような場合に接するのか?という問題に対して 二分探索木の回転操作を用いた条件を与える.For a given probabilistic distribution, a binary search tree with optimal path length among all trees is called optimal tree. Knuth showed that such a tree is computed in the time of square of the number of nodes of binary search tree. In our previous paper, we showed algorithms that the parametric space of discrete probabilistic distribution is divided into regions corresponding with binary search tree. In this paper, we investigate that any binary search tree can become optimal tree and which two optimal regions are adjacent. Some conditions related with single rotation is showed.