Deja Vu

推薦一個網站

是用Java Applet去做的

不只可以跑紅黑樹

還有其他Tree可以跑

http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm

介紹一下紅黑樹好了

A red-black tree is a type of self-balancing binary search tree, a data structure used in computer science, typically used to implement associative arrays

[from wiki]

是用來平衡高度用的

1. 只有一個root時 root必為黑

2.每次新插入點為紅

3.如果 parent node & parent node的兄弟節點 為一黑一紅

   則做rotation 動作

4.如果 parent node & parent node的兄弟節點 為二紅

   則 parent node & parent node的兄弟節點 變為二黑

    parent node的parent node (曾祖父節點) 變為紅

p.s.空節點算黑色節點

紅黑樹需符合兩種性質:

1.紅色性質: parent node & child node 不可同時為紅

2.黑色性質: 每條path上的黑色節點數目相同

紅黑樹的最長路徑 <= 2倍的最短路徑

刪除就比較複雜了

可以去wiki看看就會比較明白