作者assassin88 (AI)
看板Grad-ProbAsk
标题[理工] [DS]-93交大-电机控制所
时间Fri Jan 15 00:22:25 2010
《资料结构》 洪逸 P.9-109
给定以下key值，请造出red-black tree：
15 57 27 45 30 40 33 39 36 37
最右下角那两个图，是不是画错？
27
/\
15 *45
/ \
*33 57
/ \
30 40
插入39後↓
27
/\
15 *45
/ \
*33 57
/ \
30 40
/
39
应该是45这个node先不平衡，所以调成↓
27
/ \
15 40
/ \
33 45
/ \ \
30 39 57
再来是27不平衡，所以调成↓
33
/ \
27 40
/ \ / \
15 30 39 45
\
57
这样才对吧？有错麻烦指证一下....
另外想请问红黑树在旋转时，就是发生LR或者RL情况，
旋转後尚未调整平衡前，node的颜色不变吗？
调整後再改变~是这样吗？
请指导~感谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.57.78.8
1F：→ ieric:我是看法是1开始你不能插入39 因为图形得先做旋转 01/15 00:39
2F：推 polomoss:答案没有错...这只能体会~~" 01/15 01:22
3F：→ assassin88:我会错意~XD 01/15 12:02
4F：→ supergud:45不会不平衡阿 01/15 12:17
5F：推 taitin:第一步要先rotation，才可插入 01/15 23:25
6F：→ assassin88:其实我发现我看错图..其实第二排开始就错了(不平衡) 01/15 23:35
7F：→ assassin88:↑指书上 01/15 23:36