はじめての C

「二分木 2」

木 - tree - は、木の それぞれの 要素を 必要としない どんな 操作でも、計算時間 - time complexity - が その木の高さ - height of tree - と 等しくなる という、もともとの 特性を もっています。

その結果、高さが 最適に 近ずくという 条件では、非常に 良好な 性能に なります。

二分木探索で、(あらかじめ) ソートされている データ、または 1, 5, 2, 4, 3 のように 交互に 組まれた データを 使って 構築すると、二分木の それぞれの ノードは、たった 1つだけ 通路 - path - を もつことに なります。

これだと、基本的には リンクリストですので、二分木の もつ どんな 利点も 吹き飛んでしまいます。

可能な 一番いい やり方として、上で 述べた 2つの ケースのような 形を、絶対 生じないように するのが 安全です。

多くの 場合 実行に 移すには、基本的な 二分木で 十分です。しかし、どのような 入力でも その高さが 適切なものに なる という 保証が 必要と される ことが あります。

そのときには、つりあい - balancing - の 複雑な 領域を 採り入れます。

つりあいに ついては、将来の tutorial に、短く まとめた トピックにして 補充することに しましょう。