赤黒木
#Fleeting_Notes
赤黒木(red black tree)
二分探索木
のデータ構造の一つ
最近のVisual Studio Codeは
Piece Table
のパフォーマンスを改善するために
Piece Tree
(Piece Table + 赤黒木)を使っている
赤黒木のルール
1. 各ノードに「赤」、「黒」をつける
2. 根(root)は「黒」
3. すべてのレベルでNULLの場合は黒
4. すべての赤ノードの子は両方黒
5. すべての根から葉までの道(path)には同数の黒ノードが含まれる
Linuxカーネルでの赤黒木の実装
linux/lib/rbtree.c at master · torvalds/linux
確認用
Q. 赤黒木
メモ
from:
This seems revisionist/ignorant. The article attributes a "piece tree" data stru... | Hacker News
https://matt.might.net/papers/germane2014deletion.pdf
Red-black Trees (rbtree) in Linux — The Linux Kernel documentation
調査用
Google.icon
赤黒木(日)
Google.icon
Red black tree(英)
Wikipedia.icon
赤黒木 - Wikipedia(日)
赤黒木(検索) - Wikipedia(日)
Wikipedia.icon
Red black tree - Wikipedia(英)
Red black tree(検索) - Wikipedia(英)
#データ構造
#アルゴリズムとデータ構造