1311 views
ざっくり説明
Wikipedia先生曰く赤黒木は
「コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている」らしい。
...わかりにくい。
一回用語を調べてみた
| No | 用語 | 解説 |
|---|---|---|
| 1 | コンピューター科学 | 情報と計算の理論的基礎、及びそのコンピュータ上への実装と応用に関する研究分野である |
| 2 | データ構造 | データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のこと |
| 3 | 平衡二分木 | 二分探索木のうち木の高さ（根からの階層の数）を自動的にできるだけ小さく維持しようとするもの（平衡木）である。 |
| 4 | 連想配列 | 好きな名前を添え字にできる配列のこと |
つまるところ、なに？
コンピューター上で、データの集まりを扱う方法の一つ。
具体的には、二部探索木の高さをできるだけ小さく維持する仕組みのこと。
主に連想配列の実装時に使われる。
具体的に説明
赤黒木の定義
赤黒木を名乗るには以下の条件を満たす必要がある。
1. ノードは赤か黒である
2. 根は黒である
3. 全ての葉は黒である
4. 赤いノードの子は黒である
5. 全ての葉から根までのパスには、同じ個数の黒いノードがある
図にしてみると以下のようになる。
まとめ
理屈はわかったけど難しくね？
Page 2 of 5.
[添付ファイル]
お問い合わせ
プロフィール
owl
自己紹介
駆け出しエンジニア
だいたいweb系をかじってる
最近ちょとブロックチェーンに興味出てきた
