1. 序章

ツリーは、多くの望ましい特性を備えた基本的なデータ構造です。 順序付けられた配列のようにツリーをすばやく検索できます。また、リンクリストのようにすばやく挿入および削除することもできます。

この記事では、さまざまなタイプのツリー構造と、それらの間のいくつかの主な違いを確認します。

2. 木とは何ですか？

木について考えるとき、すぐに根、枝、葉について考えます。 さて、これはまさにコンピュータサイエンスで木の解剖学がどのように見えるかです。

ツリーは、ブランチ（エッジ）と呼ばれるものによって完全に接続された一連のノード（頂点）で構成されます。 これらのブランチには方向性がありません。

ブランチは、異なるノード間にサイクルを作成してはなりません。 構造内にサイクルが見つかった場合、ツリーを処理していません。

ツリーは階層構造に基づいて機能します。つまり、親ノードと子ノードがあります。 ツリーにはルートノードが1つだけあります。

各ノードは1つの親のみを持つことができますが、複数の子を持つことができます。 子のないノードはリーフと呼ばれます。 ノードはnullの子を持つこともできます。

ツリーのインスタンスを見つけることができる最も一般的な場所は、ファイルシステムのフォルダー構造です。

ツリーの他の重要な概念は次のとおりです。

  • パス：シーケンシャルエッジのグループ
  • 高さ：ノードとツリーの最も遠い葉の間のエッジの数。 ツリーの高さはルートノードの高さです
  • 深さ：ノードからルートまでのエッジの数

3. 二分木

二分木は、各ノードが2つ以下の子ノードを持つことができるタイプのツリーです。

二分木のすべてのノードは、値、右の子、左の子、および親を持っています。 左右の子ノードはnullになる可能性があります。

4. 二分探索木

二分探索木（BST）は、より具体的なタイプの二分木であり、主な特徴はそれがソートされていることです。

二分木は、次の場合にのみBSTです。 順序のないトラバーサル 二分木の結果はソートされたシーケンスになります。

BSTのどのサブツリーでも、親ノードの左側のノードはそれよりも小さく、親ノードの右側のノードはそれよりも大きくなります。

平均時間計算量：

  • 検索：O（log n）
  • 挿入：O（log n）
  • 削除：O（log n）

4.1. BSTへの挿入

二分探索木の挿入擬似コードを確認してみましょう。

4.2. 不均衡な二分探索木

データがツリーに沿って不均一に分散していると、ツリーのバランスが崩れてしまいます。 ツリーに要素を挿入するときに、ほとんど昇順または降順のシーケンスから挿入を行うと、ツリーのノードのほとんどがルートの片側にあり、もう一方の側にはほとんどありません。

実際、すでにソートされたリストからツリーに要素を挿入すると、最悪のシナリオに直面します。

データ=[8、12、29、43、65]

ご覧のとおり、ツリーのバランスが崩れていて、最悪のシナリオを処理すると、LinkedList。のようになります。

平均時間計算量：

  • 検索：O（n）
  • 挿入：O（n）
  • 削除：O（n）

4.3. 平衡二分探索木

BSTに要素をランダムに挿入すると、ツリーは多かれ少なかれバランスが取れたものになります。

バランスの取れたBSTを実現するにはさまざまな方法があります。 1つの方法は、元のデータセットを挿入する前にランダム化することです。

データ=[12、43、65、8、29]

平均時間計算量：

  • 検索：O（log n）
  • 挿入：O（log n）
  • 削除：O（log n）

次に、バランスの取れたツリーを維持するためのいくつかの方法を確認しましょう。

5. 赤黒木

赤黒木は、いくつかの自己バランス型ツリー構造の1つです。 赤黒木では、通常の二分木プロパティに加えて、各ノードに追加のプロパティ Colorが含まれています。 この色は赤または黒のいずれかであり、ツリーのバランスをとるために使用される赤黒ルールと呼ばれる一連のルールを追加するために使用されます。

  1. すべてのノードは赤または黒のいずれかです。
  2. ルートは常に黒です。
  3. ノードが赤の場合、その子は黒である必要があります。
  4. すべての葉は黒です。
  5. ルートからリーフまたはヌルの子へのすべてのパスには、同じ数の黒いノードが含まれている必要があります。

ノードからリーフへのパス上の黒いノードの数をノードの黒い高さと呼びます。 ルール4を言い換えると、黒の高さは、ルートからリーフまでのすべてのパスで同じである必要があるとも言えます。

平均時間計算量：

  • 検索：O（log n）
  • 挿入：O（log n）
  • 削除：O（log n）

6. AVL木

AVLツリーは、導入された最初の自己平衡ツリーでした。 それはその発明者にちなんでその名前を受け取りました：Andelson-VelskiiとLandis。

AVLツリーでは、ノードは追加のプロパティを保持します。これは、左右のサブツリー間の高さの差です。 これはバランシングファクターと呼ばれます。

AVLツリーのバランス係数はどのノードでも1より大きくすることはできません。

ノードの挿入または削除後、ツリーは潜在的に不均衡になります。 バランス係数の差が1を超える場合は、高さを正規化するために回転が必要です。

平均時間計算量：

  • 検索：O（log n）
  • 挿入：O（log n）
  • 削除：O（log n）

7. B木

Bツリーはマルチウェイツリーの一種です。 マルチウェイツリーには、3つ以上の子ノードを含めることができます。実際、数個から数千個の子ノードを含めることができます。

マルチウェイツリーの問題の1つは、各ノードがより多くのデータを含み、そのすべての子への参照を保持する必要があるため、各ノードがバイナリツリーよりも大きくなければならないことです。

Bツリーは赤黒木に似ていますが、外部ストレージのデータを整理するのに特に役立ちます。

Bツリーでは、各ノードにn個のキーが含まれ、n+1個の子があります。 したがって、その葉はすべて同じ深さにあります。

Bツリーの制限により、完全にバランスが取れています。 それらはまた、少なくとも半分がいっぱいで、いくつかのレベルが含まれています。

平均時間計算量：

  • 検索：O（log n）
  • 挿入：O（log n）
  • 削除：O（log n）

8. 結論

この記事では、さまざまな種類のツリー構造とそれぞれの特定の特性について説明しました。

実装の詳細にジャンプする準備ができたら、必ず記事Javaでのバイナリツリーの実装を確認してください。