Tag Archives: rbtree

用 C Macro 實作的紅黑樹...

用 C Macro 實作的紅黑樹 (Red-black tree) 很經典,不過每次都忘記怎麼用... XD 紅黑樹是平衡二元搜尋樹的一種,除了二元搜尋樹有的結構外,節點的資訊多了顏色。然後利用顏色達到平衡的特性。 先定義單一節點的資料結構: struct element { char *key; int value1; char *value2; RB_ENTRY(element) meta; }; 紅黑樹的每個節點都需要紀錄母、左、右節點的指標,以及顏色,其中 RB_ENTRY() 所代表的資料結構會負責紀錄這些值。 再來是定義母節點的資料結構,這樣之後就可以使用 struct tree tree1;、struct tree tree2;、struct tree tree3; 產生許多 tree 了: RB_HEAD(tree, element); 這樣就會產生 struct … Continue reading

Posted in Computer, Murmuring, Programming | Tagged , , , , , | Leave a comment