Javascriptのバイナリツリー

バイナリツリーは、データストレージの目的で使用される特別なデータ構造です。二分木には、各ノードが最大2つの子を持つことができるという特別な条件があります。バイナリツリーには、検索が並べ替えられた配列と同じくらい高速であり、挿入または削除操作がリンクリストと同じくらい高速であるため、順序付き配列とリンクリストの両方の利点があります。

これは、以下で説明するいくつかの用語を含む二分木の図です-

重要な用語

以下は、ツリーに関する重要な用語です。

• パス −パスとは、ツリーのエッジに沿ったノードのシーケンスを指します。

• ルート −ツリーの最上部にあるノードはルートと呼ばれます。ツリーごとに1つのルートと、ルートノードから任意のノードへのパスが1つだけあります。

• 親 −ルートノードを除くすべてのノードには、親と呼ばれるノードに対して1つのエッジがあります。

• 子供 −エッジが下向きに接続されている特定のノードの下のノードは、子ノードと呼ばれます。

• 葉 −子ノードを持たないノードはリーフノードと呼ばれます。

• サブツリー −サブツリーはノードの子孫を表します。

• 訪問 −訪問とは、制御がノード上にあるときにノードの値をチェックすることを指します。

• トラバース −トラバースとは、特定の順序でノードを通過することを意味します。

• レベル −ノードのレベルは、ノードの生成を表します。ルートノードがレベル0の場合、次の子ノードはレベル1にあり、孫はレベル2にあり、以下同様に続きます。

• キー −キーは、ノードに対して検索操作が実行される基準となるノードの値を表します。