『データ構造とアルゴリズム分析(c説明)』——第四章ノート

この章では主に木に関する知識を説明した.主に二叉樹、二叉捜素樹、AVL樹、伸展樹を分析し、ここで私は満二叉数、完全二叉樹を補充した.
一、二叉木
二叉樹は有限の結点の集合で、この集合はあるいは空集で、あるいは1つの根の結点と2本の互いに交差しない二叉樹から構成されて、その中の1株は根というのは左の子樹で、もう1本は根という右の子樹です.
ツリーの性質:

性質1:二叉木におけるi層目の結点数は最大2^(i-1)(i≧1)

である.

性質2:高さkの二叉木の接点総数は最大2^k-1(k≧1)

である

性質3:任意の非空二叉木Tに対して、葉結点の個数がn 0であり、その度が2の結点数がn 2である場合、n 0=n 2+1

二、二叉探索木
二叉探索ツリーは、二叉ツリーを学習した後、接触する最初の実用的なデータ構造である.特徴は、左サブツリーがすべてルートより小さく、右サブツリーがすべてルートより大きく、要素が重複しないことです.一般に対数レベルのインクリメンタルチェック操作はサポートされるが,ツリーが傾斜している場合,効率は線形に低下する.
二叉検索ツリーの挿入、削除、検索、遍歴(再帰、非再帰)の実装については、私の記事を参照してください.
[データ構造とアルゴリズム解析(c記述)]二叉探索ツリー実装
三、AVLツリー
AVLツリーは、共同発明アルゴリズムの3人の科学者の名前の頭文字に由来する高度なバランスの二叉探索ツリーである.
ここで「バランス」の定義は,任意のノードの左右のサブツリーの高さの差が1を超えないことである.
このバランスの性質により、AVLツリーの高さHが常にlog(N)に近づくため、様々な添削改変操作の複雑さが対数レベルで保証される.なしbad caseはAVLツリーと通常の二叉探索ツリーの最大の違いである.バランスのとれた性質を実現するために、各ノードの高さ(またはバランス係数)を記録してアンバランスを検出する必要があります.高さのアンバランスを修正するには、「回転」を使用します.の方法は、単回転と二回転に分けて、左右合わせて4種類の回転です.次の図解は、AVLツリーのキーアルゴリズムである回転の概略を示します.AVLツリーはとても簡単に見えますが、手で書くとAVLツリーを実現するのがどんなに面倒かがわかります.
四、満二叉木
フルツリー:深さkで2^k-1のノードを持つツリーをフルツリーと呼びます
五、完全二叉木
完全二叉木:深さkのn個の接点を有する二叉木であり、各接点が深さkの満二叉木のうち1からnの番号を持つ接点に1つずつ対応している場合にのみ、完全二叉木と呼ぶ.(最後のレイヤを除き、各レイヤのノード数は最大値に達し、最後のレイヤには右側のいくつかのノードしか欠けていません)

性質4:n個の接点を有する完全二叉木の深さはlog 2 n+1

である.
注意:

         ，         ，