あるノードの左右の子の高さが 2 違うのは何が問題なのですか?
これは AVL ツリーとの初めての出会いであり、なぜそれが必須なのか理解できないようです。
本当に、子供たちが2つ違うのは何が問題なのですか?
よろしく
2 に答える
3
それが AVL ツリーの概念です。左と右の子の高さの差は最大で 1 であってはなりません。
ウィキペディアより
AVL ツリーでは、任意のノードの 2 つの子サブツリーの高さの差は最大で 1 です。
バランスがとれているため、検索は 0(logn) になり、すべての要素が左側にあり、0(n) になるバランスの取れていない二分木よりも高速です。
于 2012-05-28T22:51:30.517 に答える
3
定義上、バランスのとれた二分木は 1 だけ異なる場合があります。AVL ツリーで動作するアルゴリズムを見ると、このプロパティが常に維持されていることがわかります。
高さが最大で +-2 だけ異なるある種のデータ構造を作成することは可能ですが、そうしても実際の利点はありません。+- 1 のままにしておくと、より単純で自己バランスのとれたデータ構造が作成されます。
于 2012-05-28T22:51:50.807 に答える