【データ構造とアルゴリズム】面接での赤と黒の木
3564 ワード
赤黒い木
1.データ構造の定義は、二叉でツリーのバランスを調べた場合、最悪の検索時間がlgN であることを保証することができる.ですが、2-3ツリーは2つのタイプの異なるノードを維持するために、追加のオーバーヘッドが大きすぎる です.マホガニーツリー:赤リンクは3ノードの代わりに2つのノードを使用する.黒いリンクとは、2−3ツリーのうちの2−3ツリーの等価変換を行う赤いツリー である.
2.性質性質1.ノードは赤または黒 である.性質2.根は黒 です.性質3.すべての葉は黒 です.性質4.各赤いノードの2つのサブノードは黒である(各リーフからルートまでのすべての経路で2つの連続した赤いノードがない). 性質5.完璧な黒のバランス:任意のノードからその各リーフまでのすべての簡単なパスは、同じ数の黒いノード を含む.
3.時間の複雑さ
赤と黒の木の検索に関する実現は、標準の二叉の検索ツリーと完全に一致しています.挿入、削除は複雑です.しかし、検索関連の操作は挿入、削除より使用頻度が高いです.すべての操作時間は対数レベルです.
4.二叉を比較して木BSTを検索し、自己バランス二叉で木AVLを検索する.
赤黒い木は厳格な高平衡を犠牲にした優れた条件を代価として、部分的に平衡の要求だけを達成して、回転に対する要求を下げて、性能を向上させました.マゼンタは、O(log 2 n)の時間的複雑度で検索、挿入、削除操作を行うことができます.また、その設計のために、どのアンバランスも三回回転して解決します.もちろん、もっといいのがありますが、より複雑なデータ構造を実現すれば、一歩回転してもバランスが取れるようになります.
BSTに比べて、ツリーの最長経路が2倍以下の最短経路の長さを確保できるので、その検索効果は最低保証されていることがわかる.最悪の場合もO(logN)を保証することができます.これは二叉で木を探すより良いです.二叉検索ツリーが最悪の場合はO(N)まで検索できるからです.
赤と黒の木のアルゴリズムの複雑さはAVLと同じですが、統計性能はAVLの木より高いです.だから、挿入と削除の中で行われた後期メンテナンスの操作はきっと赤と黒の木より時間がかかります.しかし、彼らの検索効率はOです.したがって、赤と黒の木のアプリケーションは、AVLの木よりも高いです.実際には、AVLの木と赤と黒の木を挿入する速度は、データに依存します.データの分布が良いなら、AVLの木を採用しやすいです.ただし、乱雑な状況を処理したいなら、赤と黒の木は比較的速いです.
5.ハッシュ表を比較する
4つの要因をトレードオフします.検索速度、データ量、メモリ使用、拡張可能性.全体的に、hash検索速度はmapより速くなり、検索速度は基本的にデータ量とは関係なく、定数レベルに属します.mapの検索速度はlog(n)レベルです.必ずしも定数がlog(n)より小さいとは限りません.hashやhash関数の時間がかかります.分かりましたよね.効率を考えるなら、特に元素が一定の数量に達した時、hashを考えます.しかし、メモリの使用が非常に厳しい場合は、プログラムを最小限にしたいと思いますが、hashはあなたを困らせる可能性があります.特に、hashのオブジェクトが多い時には、コントロールできなくなります.そして、hashの構造速度が遅くなります.マホガニーはすべてのアプリケーションツリーの領域に適応していません.データが基本的に静的であれば、それらを挿入できるようにし、バランスに影響を与えないところでより良い性能を持っています.データが完全に静的である場合、例えば、ハッシュ・テーブルを作ると、性能はより良いかもしれない.
実際のシステムでは、例えば、動的規則を使用するファイアウォールシステムが必要であり、レッド・ツリーを使用して、ハッシュ・テーブルではなく、より良い伸縮性があることが実証されている.Linuxカーネルは管理しています.アーアアウstructの時は赤い黒い木を使ってメモリブロックを維持します.赤黒いツリーは、ノード領域を拡張することによって、時間の複雑さを変えずに、接合点のランクを得ることができる.
剣指×ゲーム(六)-面接中の赤・黒の問題を簡単に解決します.
1.データ構造の定義
public class RedBlackBST<Key extends Comparable<Key>, Value>{
private Node root; //
private static final boolean RED = true;
private static final boolean BLACK = false;
//private
private class Node{
Key key;
Value value;
Node left,right;
int N; //
boolean color;
}
//
}2.性質
3.時間の複雑さ
赤と黒の木の検索に関する実現は、標準の二叉の検索ツリーと完全に一致しています.挿入、削除は複雑です.しかし、検索関連の操作は挿入、削除より使用頻度が高いです.すべての操作時間は対数レベルです.
4.二叉を比較して木BSTを検索し、自己バランス二叉で木AVLを検索する.
赤黒い木は厳格な高平衡を犠牲にした優れた条件を代価として、部分的に平衡の要求だけを達成して、回転に対する要求を下げて、性能を向上させました.マゼンタは、O(log 2 n)の時間的複雑度で検索、挿入、削除操作を行うことができます.また、その設計のために、どのアンバランスも三回回転して解決します.もちろん、もっといいのがありますが、より複雑なデータ構造を実現すれば、一歩回転してもバランスが取れるようになります.
BSTに比べて、ツリーの最長経路が2倍以下の最短経路の長さを確保できるので、その検索効果は最低保証されていることがわかる.最悪の場合もO(logN)を保証することができます.これは二叉で木を探すより良いです.二叉検索ツリーが最悪の場合はO(N)まで検索できるからです.
赤と黒の木のアルゴリズムの複雑さはAVLと同じですが、統計性能はAVLの木より高いです.だから、挿入と削除の中で行われた後期メンテナンスの操作はきっと赤と黒の木より時間がかかります.しかし、彼らの検索効率はOです.したがって、赤と黒の木のアプリケーションは、AVLの木よりも高いです.実際には、AVLの木と赤と黒の木を挿入する速度は、データに依存します.データの分布が良いなら、AVLの木を採用しやすいです.ただし、乱雑な状況を処理したいなら、赤と黒の木は比較的速いです.
5.ハッシュ表を比較する
4つの要因をトレードオフします.検索速度、データ量、メモリ使用、拡張可能性.全体的に、hash検索速度はmapより速くなり、検索速度は基本的にデータ量とは関係なく、定数レベルに属します.mapの検索速度はlog(n)レベルです.必ずしも定数がlog(n)より小さいとは限りません.hashやhash関数の時間がかかります.分かりましたよね.効率を考えるなら、特に元素が一定の数量に達した時、hashを考えます.しかし、メモリの使用が非常に厳しい場合は、プログラムを最小限にしたいと思いますが、hashはあなたを困らせる可能性があります.特に、hashのオブジェクトが多い時には、コントロールできなくなります.そして、hashの構造速度が遅くなります.マホガニーはすべてのアプリケーションツリーの領域に適応していません.データが基本的に静的であれば、それらを挿入できるようにし、バランスに影響を与えないところでより良い性能を持っています.データが完全に静的である場合、例えば、ハッシュ・テーブルを作ると、性能はより良いかもしれない.
実際のシステムでは、例えば、動的規則を使用するファイアウォールシステムが必要であり、レッド・ツリーを使用して、ハッシュ・テーブルではなく、より良い伸縮性があることが実証されている.Linuxカーネルは管理しています.アーアアウstructの時は赤い黒い木を使ってメモリブロックを維持します.赤黒いツリーは、ノード領域を拡張することによって、時間の複雑さを変えずに、接合点のランクを得ることができる.
剣指×ゲーム(六)-面接中の赤・黒の問題を簡単に解決します.