扱っている題材自体は、アルゴリズムとデータ構造の入門書によくあるもので、 探索や整列、スタックやキュー、リストや木構造といった、基本的なラインナップです。 ただし、その解説内容は非常に詳細で、基礎から応用まで、相当に詳しく検討・解説がなされています。 入門用とするには 木構造を持つデータを探索するアルゴリズムに、木の巡回と呼ばれるものがあります。今回は3種類の木の巡回を取り上げ、それらを実装してみます。 木の巡回 木の巡回とは、ある木に属する全てのノードを順番に1回づつ訪問するアルゴリズムのことを指します。 2分探索木は、以下のような特徴を持つ木構造です（図1）。 2分木（各ノードは最大で2本の子を持つ）。 全ての要素が「左の子＜親≦右の子」（あるいは「左の子≦親＜右の子」）という大小関係を満たす。 2分探索木 2 木の用語 木： ノードの集合とエッジ (edge)の集合からなる エッジ： 2つのノードを結ぶもの ルート(root)： 最初のノード 親ノード(parent)： ノードの一個上にあるもの ルートノードには親ノードが ない 子ノード(child)： 一個下にあるもの 中間ノード：

データ構造とアルゴリズム avl木(平衡探索木) 岡本吉央 豊橋技術科学大学情報工学系 2005年10月3日 岡本吉央 avl 木