動いちゃうRed Black Tree

本日は「Red Black Tree」についての小ネタを。

以前も書きましたが、我々バックエンドチームでは毎週カーネルに関する勉強会をしています。ちょっと前にメモリマネジメントのネタを扱った際に、Red Black Tree（赤黒木）が出てきました。

Red Black Treeは平衡二分木の一種で、Linuxではノード管理に使用されています。
Red Black Treeは以下のような状態になっています。

1. A node is either red or black.
2. The root is black.
3. All leaves are black. (This includes the NIL children.)
4. Both children of every red node are black. (So every red node must have a black parent.)
5. Every simple path from a node to a descendant leaf contains the same number of black nodes.

書きたかったのは、以下のサイトで動的なサンプルが見られるということです。結構面白いです。

http://gauss.ececs.uc.edu/RedBlack/redblack.html

ただし、Javaが入ってないと見れません。

では、また。

 

Comments

[投稿： tshoji]

Linuxのアルゴリズムは毎回感心してしまいます。