13

ウィキペディアのAVLツリーに関する記事の3番目の段落には、「AVLツリーはより厳密にバランスが取れているため、ルックアップを多用するアプリケーションでは赤黒木よりも高速です」と書かれています。

したがって、TreeMapは、赤黒木ではなくAVLツリーを使用して実装する必要があります（ハッシュベースのデータ構造のアプリケーションがさらに検索されるため）。

4

3 に答える 3

24

赤黒木はより一般的な目的です。これらは、追加、削除、およびルックアップで比較的うまく機能しますが、AVLツリーは、追加/削除が遅くなる代わりに、ルックアップが速くなります。Javaの一般的なポリシーは、最高の汎用データ構造を提供することです。これは、JavaのデフォルトのArray.sort（Object [] a）実装が、クイックソートではなく、安定した、適応型の、反復的なマージソートであるのと同じ理由でもあります。

于 2013-02-17T16:43:18.923 に答える
2

歴史的に、回転数は非常に重要であると考えられていたため、赤黒木はランダムインサートでわずかに少ない回転を実行するため、AVLよりも赤黒木が選択されました-インサートあたりの平均回転数は.6対.7です。

後から考えると、AVL木がおそらくより良い選択だったでしょう。JavaでのAVLと赤黒木のパフォーマンス比較は、 https ：//refactoringlightly.wordpress.com/2017/10/29/performance-of-avl-red-black-trees-in-java/で確認できます。

ランダム挿入の場合、パフォーマンスは同様です。シーケンシャルデータを使用すると、AVLツリーのパフォーマンスが大幅に向上します（30％以上）。

于 2017-10-20T23:13:39.937 に答える
1

The Wikipedia article is wrong (or at least, there is no supporting citation to back up the claim). It is true that the worst-case height of an AVL tree (1.44 lg n) is better than the worst-case height of a red-black BST (2 lg n), but this is worst case and may not have much to do with real-world performance.

于 2013-02-17T19:12:15.360 に答える