作者want0417 (生活像只猫)
看板Grad-ProbAsk
标题[理工] [资结]-红黑树与2-3-4树问题
时间Fri Feb 12 21:18:24 2010
台北大学95年资结
有一题建置红黑树
树列为
7 9 13 5 11 4 3 2 1 10 17
小弟的步骤
9 9 9 9 5
/ \ / \ / \ / \ / \
7R 13R 7 13 5R 13 5R 13 3 9
/ / / \ / / \ / --> / \ / \
5R 11R 4 7 11R 3R 7 11R 2 4 7 13
/ \ / /
2 4 1R 11R
5 5
/ \ / \
3 9 3 11
/ \ / \ / \ / \
2 4 7 11 2 4 9 13
/ / \ / / \ \
1R 10R 13R 1R 7R 10R 17R
请问一下这样的步骤对吗?
比较有问题是转换那边 3和9 是R还是直接变成黑就好?
另外可以用2-3-4树来建立 这样出来的树应该不唯一吧?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 111.255.147.21
1F：→ ntust661:我还以为是红树林=..= 02/12 21:20
2F：推 taitin:3跟9都红色 02/12 21:25
3F：→ taitin:rotation的时候，两个子都是红色 02/12 21:25
4F：→ want0417:所以大大 我只要注意转的时候3和9都变成红色 02/12 21:32
5F：→ want0417:那这步骤就没错? 02/12 21:32
6F：→ taitin:最後一步好像有影响，插入17那个 02/12 21:34
7F：→ want0417:请问大大 最後是变成? 能用水球或是其他方式交一下吗? 02/12 21:40
8F：→ taitin:我回文喔，请稍候 02/12 21:44