データ構造とアルゴリズムの美学｜データ構造には何種類の「木」があるのか？データ構造にはいくつの「木」があるのか？

• [1\. ]
• [1.1 バイナリツリーの定義]
• [1.2 バイナリツリーの例]
• [1.3 完全二分木と完全二分木]。
• [1.3.1 完全二分木]
• [1.3.2 完全二分木]
• [1.4 二分木の性質]
• [2\. 二分探索木]
• [3\. バランス2進木]
• [3.1 AVLツリーのバランスド・ルックアップ・ツリー]
• [3.2 赤黒平衡二分木]。
• [4\. B ]
• [4.1 B木とは]
• [4.2 B木の性質]
• [5\. B+Tree]
• [5.1 Bとは+ ]
• [5.2 B+ ]
• [6\. B*tree]
• [7\. R ]
• [8\. Trie ]
• [8.1 トライツリーとは]
• [8.2 トライ木の3つの基本的性質].
• [8.3 Tireツリーの応用]

バイナリツリー

バイナリツリーの定義

• バイナリツリーのi番目のレベルは、最大2i-1個のノードを持ちます；
• 深さkの2進木は、最大2k-1個のノードを持ちます；
• 任意の2分木Tについて、終端ノードの数をn_0n0、次数2のノードの数をn_2n2とすると、n_0=n_2+1n0=n2+1。

バイナリツリーの例

完全二分木と完全二分木

完全二分木

1. ツリーは深さhと最大層数kを持ちます。深さは最大層数と同じで、k = hです。
2. 葉の数は2h-1;
3. 第k層のノード数は2k-1。
4. 要約点の数は2k-1であり、ノードの総数は奇数でなければなりません。

完全二分木

二分木の性質

1. 空でない2分木では、レベルiのノードの総数は2i-1以下、i>=1；
2. 深さ h のバイナリツリーは、最大 2h-1 個のノードと少なくとも h 個のノードを持ちます。
3. 任意の2分木について、その葉ノードの数をN0、次数2のノードの総数をN2とすると、N0=N2+1；
4. n個のノードを持つ完全な二分木の深さはlog_2 ⌊+1log_230n⌊⌋+1です。
5. N個のノードを持つ完全な2分木のノードは、それらが順次に格納されている場合、互いに次のように関連しています：

1. h(N)個の異なる2分木を形成できるN個のノードが与えられたとき、h(N)はカートランド数のN番目の項であり、h(n)=C(2＊n,n)/h(n)=C(2＊n,n)/。
2. i個の分岐点があり、Iはすべての分岐点の道の長さの合計、Jは葉の道の長さの合計J = I + 2iJ = I + 2i。

二分探索木

1. 左の部分木が空でない場合、左の部分木のすべてのノードの値は、そのルート・ノードの値より小さい；
2. 右のサブツリーが空でない場合、右のサブツリーのすべてのノードは、そのルート・ノードの値以上の値を持ちます；
3. 左と右のサブツリーもそれぞれバイナリソートされた木です；
4. キー値が等しいノードはありません。

1. 現在のバイナリ・ルックアップ・ツリーが空の場合、挿入される要素はルート・ノードになります。
2. 挿入された要素の値がルート・ノードの値より小さい場合、その要素は左のサブツリーに挿入されます。
3. 挿入された要素の値がルート・ノードの値より小さくない場合、その要素は右のサブツリーに挿入されます。

1. pがリーフ・ノードである場合、図aのように、そのノードを削除し、親ノードへのポインタを修正するのは簡単です。
2. pは単一枝ノード。図bのように、pを削除すれば十分です。
3. pの左部分木も右部分木も空ではありません。yは左サブツリーを持ってはならないので、yを削除してyの父ノードをyの右サブツリーの父ノードとし、pの値をyの値で置き換えることができます。図cのように

struct node
{
 int val;
 pnode lchild;
 pnode rchild;
};
pnode BT = NULL;
//ノードを挿入する再帰的方法
pnode insert(pnode root, int x)
{
 if(root == NULL){
 	pnode p = (pnode)malloc(LEN);
 	p->val = x;
 	p->lchild = NULL;
 	p->rchild = NULL;
 root = p; 
 } 
 else if(x < root->val){
 root->lchild = insert(root->lchild, x); 
 }
 else{
 root->rchild = insert(root->rchild, x); 
 }
 return root;
}
//ノードを挿入するための非再帰的方法
void insert_BST(pnode q, int x)
{
 pnode p = (pnode)malloc(LEN);
 p->val = x;
 p->lchild = NULL;
 p->rchild = NULL;
 if(q == NULL){
 BT = p;
 return ; 
 } 
 while(q->lchild != p && q->rchild != p){
 if(x < q->val){
 if(q->lchild){
 q = q->lchild; 
 } 
 else{
 q->lchild = p;
 } 
 } 
 else{
 if(q->rchild){
 q = q->rchild; 
 } 
 else{
 q->rchild = p; 
 }
 }
 }
 return;
}

bool delete_BST(pnode p, int x) //削除された要素が見つかったかどうかを示すフラグを返す
{
 bool find = false;
 pnode q;
 p = BT;
 while(p && !find){ //削除された要素を見つける
 if(x == p->val){ //削除された要素を見つける
 find = true; 
 } 
 else if(x < p->val){ //左部分木に沿って探す
 q = p;
 p = p->lchild; 
 }
 else{ //正しい部分木に沿って探す
 q = p;
 p = p->rchild; 
 }
 }
 if(p == NULL){ //見つからない。
 cout << "見つからない "<< x << endl; 
 }
 if(p->lchild == NULL && p->rchild == NULL){ //pリーフノードの場合
 if(p == BT){ //pルート・ノード
 BT = NULL; 
 }
 else if(q->lchild == p){ 
 q->lchild = NULL;
 } 
 else{
 q->rchild = NULL; 
 }
 free(p); //ノードpを解放する
 }
 else if(p->lchild == NULL || p->rchild == NULL){ //p単一枝部分木の場合
 if(p == BT){ //pルート・ノード
 if(p->lchild == NULL){
 BT = p->rchild; 
 } 
 else{
 BT = p->lchild; 
 }
 } 
 else{
 if(q->lchild == p && p->lchild){ //pはqの左部分木であり、pは左部分木を持つ
 q->lchild = p->lchild; //pの左部分木をqの左ポインタにリンクする
 } 
 else if(q->lchild == p && p->rchild){
 q->lchild = p->rchild; 
 }
 else if(q->rchild == p && p->lchild){
 q->rchild = p->lchild; 
 }
 else{
 q->rchild = p->rchild;
 }
 }
 free(p);
 }
 else{ //pの左の部分木も右の部分木も、どちらも
 pnode t = p;
 pnode s = p->lchild; //pの左の子ノードから始める
 while(s->rchild){ //pの前任者、すなわちpの左部分木の中で最大の値を持つノードを見つける
 t = s; 
 s = s->rchild; 
 }
 p->val = s->val; //ノードsの値をpに代入する
 if(t == p){
 p->lchild = s->lchild; 
 } 
 else{
 t->rchild = s->lchild; 
 }
 free(s); 
 }
 return find;
}

pnode search_BST(pnode p, int x)
{
 bool solve = false;
 while(p && !solve){
 if(x == p->val){
 solve = true; 
 } 
 else if(x < p->val){
 p = p->lchild; 
 }
 else{
 p = p->rchild; 
 }
 }
 if(p == NULL){
 cout << "見つからない "<< x << endl; 
 } 
 return p;
}

バランス2進木

AVLツリーのバランスド・ルックアップ・ツリー

1. 6ノードの左サブツリー3ノードの高さは右サブツリー7ノードより2大きく、左サブツリー3ノードの左サブツリー1ノードの高さは右サブツリー4ノードより大きいので、この場合は左レフトになります。
2. 6ノードの左サブツリー2ノードの高さは右サブツリー7ノードの高さより2大きく、左サブツリー2ノードの左サブツリー1ノードの高さは右サブツリー4ノードの高さより小さく、この状態が左右になります。
3. 右のサブツリー5ノードの左のサブツリー3ノードの高さが右のサブツリー6ノードより大きいので、このケースは右左になります。
4. 右のサブツリー4ノードの左のサブツリー3ノードの高さは右のサブツリー6ノードより小さく、このケースは右-右となります。

赤黒平衡二分木

• Property 1. ノードは赤または黒。
• \. 根が黒い
• 自然。 葉はすべて黒。
• プロパティ 4。 各赤ノードには2つの黒子ノードが必要です。
• 特性5。 任意のノードからその葉の各々へのすべての単純パスは、同じ数の黒ノードを含みます。

• プロパティ1と3は常に維持されています。
• プロパティ4が脅かされるのは、赤いノードを追加したり、黒いノードを赤に再描画したり、回転させたりするときだけです。
• プロパティ5は、黒いノードを追加するとき、赤いノードを黒に再描画するとき、または回転を行うときにのみ脅かされます。

• シナリオ 1: ツリーが空で、ルート・ノードの位置を直接挿入し、プロパティ 1 に違反し、ノードの色を赤から黒に変更するだけ。
• シナリオ2：親Pが黒であるノードNの挿入は、どのプロパティにも違反せず、修正の必要もありません。このシナリオでは、ツリーはまだ有効です。新しいノードNが2つの黒い葉の子を持つとしても、特性5も脅かされません。しかし、新しいノードNは赤なので、それぞれの子を通るパスは、それが置き換わる黒い葉を通るパスと同じ数の黒いノードを持ち、特性はまだ満たされます。

注：シナリオ1は非常にシンプルで、シナリオ2ではPが黒ですべてがうまくいきますが、Pが赤の場合はそうではありません。

• シナリオ3：親ノードPと叔父ノードUが両方とも赤の場合、両方を黒に再描画し、祖父ノードGを赤に再描画します。親ノードPまたは叔父ノードUを通るパスは必ず祖父ノードGを通るので、これらのパス上の黒ノードの数は変わりません。しかし、赤の祖父ノードGが赤の親ノードを持つ可能性があり、これは性質4に違反します。この問題を解決するために、上記のシナリオのプロセス全体を祖父ノードGに対して再帰的に実行します。例えば、Gがルート・ノードであれば、Gを黒にするのは簡単です。Gがルート・ノードでなく、その親が黒であれば、すべての特性が満たされており、挿入するのは簡単です。Gがルート・ノードでなく、その親が赤であれば、再帰的に上記の処理を行います。

• シナリオ4：親ノードPが赤で、おじノードUが黒、または欠けていて、新しいノードNがその親の左の子で、親ノードPがその親Gの左の子。この場合、祖父ノード G に対して右回転が 1 回実行されます。回転によって生成されるツリーでは、前の親ノード P が新しいノード N と前の祖父ノード G の親になります。前の祖父ノードGは黒であり、そうでなければ親ノードPは赤にはなりません。以前の親ノードPと祖父ノードGの色を入れ替えると、結果のツリーは特性4を満たします。以前は祖父ノードGを通過していた3つのノードのいずれかを通るすべてのパスは、現在は以前の親ノードPを通過するので、特性5も満たされたままです。

• シナリオ5：親ノードPが赤で、祖父母ノードUが黒または欠損で、新しいノードNが親ノードPの右の子で、その親の左の子である場合。この場合、左回転が実行され、新しいノードとその親の役割が入れ替わります。次に、以前の親ノードPがケース4と同様に扱われ、プロパティ4が解決されますが、これはまだ失敗します。

Bツリー

B木とは