ホームページ  >  記事  >  バイナリーツリーはどのような用途に使われるのでしょうか?

バイナリーツリーはどのような用途に使われるのでしょうか?

藏色散人
藏色散人オリジナル
2020-06-29 10:00:0212528ブラウズ

バイナリ ツリーは、バイナリ検索ツリーとバイナリ ヒープの実装に使用できます。コンピュータ サイエンスでは、バイナリ ツリーは、ノードごとに最大 2 つのサブツリーを持つツリー構造です。通常、サブツリーは「左サブツリー」と呼ばれ、 「右サブツリー」は、1. 完全なバイナリ ツリー、2. 完全なバイナリ ツリー、3. さまざまな用途に応じたバランスのとれたバイナリ ツリーに分割できます。

バイナリーツリーはどのような用途に使われるのでしょうか?

バイナリ ツリーの役割

バイナリ ツリーは、二分探索ツリーとバイナリの実装によく使用されます。山盛り。

コンピュータ サイエンスでは、バイナリ ツリーは、ノードごとに最大 2 つのサブツリーを持つツリー構造です。通常、サブツリーは「左サブツリー」および「右サブツリー」と呼ばれます。

さまざまな用途に応じて、次のように分割できます:

1. 完全なバイナリ ツリー - バイナリ ツリーの高さが h の場合、h 番目の層を除き、他のすべての層(1~h-1) ノード数が最大数に達しました h 層にはリーフノードがあり、それが左から右に並んでいる完全な二分木です。

2. 完全なバイナリ ツリー - リーフ ノードを除くすべてのノードに左右のサブリーフがあり、リーフ ノードがすべて最下位にあるバイナリ ツリー。

3. バランス バイナリ ツリー - バランス バイナリ ツリーは、AVL ツリーとも呼ばれます (AVL アルゴリズムとは異なります)。これはバイナリ ソート ツリーであり、次の特性があります: 空のツリーまたはその左右のサブツリー間の高さの差の絶対値は 1 を超えず、左右のサブツリーは両方ともバランスのとれた二分木です。

バイナリーツリーはどのような用途に使われるのでしょうか?

拡張情報

深さ h のバイナリ ツリーには、最大 1 つのノード (h>=1) と少なくとも h のノードがあります。任意の二分木について、葉ノードの数が N0 で、次数 2 のノードの総数が N2 の場合、N0=N2 1 となります。

N 個のノードを持つ完全なバイナリ ツリーの各ノードが順番に格納される場合、ノード間の関係は次のようになります。 I がノード番号の場合、I>1 の場合、その親ノード数値はI/2です。 2*IN の場合、左の子は存在しません。 2*I 1

以上がバイナリーツリーはどのような用途に使われるのでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。