作者GraffitiK (GraffitiK)
看板Grad-ProbAsk
标题[问题] 97中正一题AVL tree的问题
时间Wed Mar 25 16:00:06 2009
题目如下:
http://img207.imageshack.us/img207/7647/questionb.jpg
(a)小题我做出来是这样:
http://img207.imageshack.us/img207/2903/36404634.jpg
想请问(b)小题, 删去20後是像binary search tree的做法, 从左子树最大者或右子树最
小者上来顶替删掉的node, 所以有两种结果吗?
http://img207.imageshack.us/img207/7677/43447802.jpg
那像上面第一种在node 8发生不平衡, 是属於哪种不平衡? 8-35-28的RL不平衡还是
8-35-40的RR不平衡?
另外, (c)小题的时间复杂度, insert和delete都是O(log n)吗?
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.121.164.62
1F：推 s987692:a.跟你一样 b.应该有两种结果 c.logn 03/25 16:31
2F：→ GraffitiK:那请问(b)小题发生的不平衡该如何调整呢? 03/25 16:33
3F：推 s987692:我怎麽觉得都可以 = = 03/25 16:56
4F：推 greedbo:印象中AVL tree画法很多种,除非题目要求作平衡才需要标平 03/25 17:18
5F：→ greedbo:衡系数 找最小值 03/25 17:18
6F：→ greedbo:最平衡 03/25 17:19