Javaインタビュー-赤-黒ツリー

まず、図に示すように、赤黒ツリーの構造を見てみましょう:

(学習ビデオの共有: Java 教育ビデオ )

赤黒ツリーの構造的特徴:

(1) 各ノードは黒または赤です。
(2) ルート ノードは黒です。
(3) 各リーフ ノード (NIL) は黒です。 [注: ここでのリーフ ノードは、空 (NIL または NULL) のリーフ ノードを指します。 ]
(4) ノードが赤の場合、その子ノードは黒でなければなりません。
(5) ノードからそのノードの子孫ノードまでのすべてのパスには、同じ数の黒いノードが含まれます。

なぜ赤黒の木を使うのですか?

1. まず第一に、赤黒ツリーは AVL ツリー、つまり各ノードの左部分木の高さと右部分木の高さが最大でも異なる二分探索ツリーのバランス条件を満たしていません。 1.ただし、ノードに色を追加することが提案されています。赤黒ツリーは、ノードの追加または削除時に回転数を減らすために非厳密なバランスを使用します。不均衡は 3 回の回転以内に解決されますが、AVL は厳密にバランスの取れたツリーであるため、ノードの追加や削除の際、ノードに関しては場合によっては赤黒ツリーよりも回転数が多くなります。したがって、赤黒ツリーの挿入効率は高くなります。

(より関連するインタビューの質問に関する推奨事項:Java インタビューの質問と回答)

2. 赤黒ツリー検索、挿入、削除の操作に O( Log2 (n)) の時間計算量を実行できます。

3. 簡単に言えば、赤黒ツリーは二分探索ツリーの欠点を解決するものです。場合によっては、ツリーは線形構造に退化します。

赤黒ツリーとバランスツリーの比較と選択

1. バランスツリー構造はより直観的であり、読み取りパフォーマンスは赤黒ツリーよりも高くなります。バランスを回復するためのノードの追加と削除のパフォーマンスは、赤黒ツリーほど良くありません。黒ツリー
2. 赤黒ツリーの読み取りパフォーマンスは、バランスのとれたツリーほど良くありません。追加のパフォーマンスは、バランスを回復するためにノードを削除するのは、バランスのとれたツリーよりも悪いです。

赤黒ツリーの使用シナリオ:

ツリーマップ、JDK1.8 以降の TreeSet と HashMap はどちらも最下層で赤黒ツリーを使用します。 。

関連する推奨事項: Java 入門チュートリアル

以上がJavaインタビュー-赤-黒ツリーの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。