11

二分木がバランスをとることが重要なのはなぜですか

4

5 に答える 5

10

次のような木を想像してみてください。

  A
   \
    B
     \
      C
       \
        D
         \
          E

これは有効な二分木ですが、現在、ほとんどの操作はO（lg n）ではなくO（n）です。

于 2012-07-16T04:05:27.073 に答える
7

二分木のバランスは、歪度と呼ばれるプロパティによって制御されます。ツリーがより歪んでいる場合、バイナリツリーの要素にアクセスするための時間計算量が増加します。木を言う

                1
               / \
              2   3
              \    \
               7    4
                     \
                      5
                       \
                        6

上記も二分木ですが、右に歪んでいます。7つの要素があるため、理想的な二分木にはO（log 7）=3回のルックアップが必要です。ただし、最悪の場合、もう1レベル深く=4回のルックアップを行う必要があります。したがって、ここでの歪度は一定です1。ただし、ツリーに数千のノードがあるかどうかを検討してください。その場合、歪度はさらに大きくなります。したがって、バイナリツリーのバランスを保つことが重要です。

しかし、ランダム二分木の確率分析では、 n個の要素を持つランダム二分木の平均深度が4.3 log nであることが示されているため、歪度が議論のトピックになっています。ですから、それは実際にはバランスと歪度の問題です。

もう1つの興味深い点は、コンピューター科学者が歪度に利点を見出し、歪度ヒープと呼ばれる歪度のあるデータ構造を提案したことです。

于 2012-07-16T12:15:45.240 に答える
4

log（n）の検索時間を確保するには、各ブランチでダウンレベルノードの総数を2で割る必要があります。たとえば、ルートからリーフノードに分岐しない線形ツリーがある場合、検索時間はリンクリストのように線形になります。

于 2012-07-16T04:05:34.713 に答える
1

非常に不均衡なツリー、たとえば、すべてのノードが左側にリンクされているツリーは、最後のノードを見つける前にすべてのノードを検索することを意味します。これは、ツリーのポイントではなく、リンクリストに勝る利点はありません。 。ツリーのバランスをとると、O（n）ではなくO（log（n））の検索時間が短縮されます。

于 2012-07-16T04:07:03.563 に答える
0

二分探索木の操作のほとんどは木の高さに比例することがわかっているので、高さを低く保つことが望ましいです。これにより、検索時間が複雑さのO（log（n））に厳密になります。

それよりも、利用可能なツリーバランシングテクニックのほとんどは、完全に満杯であるか、完全にバランスが取れていることに近いツリーに適用されます。

最後に、あなたはあなたのツリーをシンプルにする必要があり、赤黒木やavlのような最高の二分木を選びます

于 2020-02-02T01:33:39.820 に答える