ホームページ  >  記事  >  バランスの取れた二分木の特徴は何ですか?

バランスの取れた二分木の特徴は何ですか?

烟雨青岚
烟雨青岚オリジナル
2020-06-29 10:18:019657ブラウズ

平衡二分木の特性は次のとおりです: 1. 非リーフ ノードには最大 2 つの子ノードがあります; 2. 非リーフ ノードの値は、左側の子ノードより大きく、左側の子ノードより小さいです。右側の子ノード; 3. ツリーの左側と右側のレベルの数は同じです。1 より大きくなります; 4. 値が等しい重複ノードはありません。

バランスの取れた二分木の特徴は何ですか?

バランス型バイナリ ツリーの特徴:

(1) 非リーフ ノードには最大 2 つの子ノードがあります。

(2) 非リーフ ノードの値が左の子ノードより大きく、右の子ノードより小さい;

(3) 左と右のレベル数の差ツリーの右側は 1 より大きくなりません;

#(4) 等しい値を持つ重複ノードはありません;

#バランスの取れたバイナリ ツリーの概念

バランス バイナリ ツリーは、データ検索の速度を向上させるための二分法戦略に基づくバイナリ ツリー データ構造です。

特徴:

バランス バイナリTree は、二分法的思考を使用してルールに従ってデータをツリー構造に組み立て、このツリー構造データを使用して無関係なデータの検索を削減します。データ検索の速度が大幅に向上します。バランスの取れた二分木のデータ構造の組み立てプロセスは次のとおりです。ルール:

(1) 非リーフ ノードでは、最大 2 つの子ノードのみが存在できます。

(2) 各非リーフ ノードのデータ分散ルールは、左側の子ノードが現在のノードの値より小さく、右側の子ノードが現在のノードの値より大きいということです。現在のノード (ここでの値は独自のアルゴリズム ルール、たとえばハッシュ値に基づいています);

バランスの取れたツリーの階層構造: バランスの取れたバイナリ ツリーのクエリ パフォーマンスは、ツリーのレベル (h 高さ)、h の値が小さいほどクエリは高速になります ツリー構造の左端と右端のデータを確保するために 二分木のクエリの難易度を大まかにバランスさせて軽減するために、アルゴリズム メカニズムは通常、ノード データ構造のバランスを実現するために使用されます。そのようなアルゴリズムの例には、Treap や赤黒ツリーなどがあります。バランスのとれたバイナリ ツリーを使用すると、データの左側と右側のノード レベルが変わらないことが保証されます。 . 1 より大きい。これにより、クエリの効率に影響を与える削除の増加によってツリー構造が線形リンク リストになるのを防ぎ、データのバランスが取れているときのデータ検索の速度がバイナリ検索の速度に近づくことが保証されます。

関連情報の詳細については、

PHP 中国語 Web サイト

をご覧ください。 !

以上がバランスの取れた二分木の特徴は何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

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