[考題] 計概 AVL tree

看板Examination作者 (我是胖達不是胖呆喲^ ^)時間13年前 (2013/03/24 19:31), 編輯推噓2(2推 0噓 4→)
留言6則, 3人參與, 最新討論串1/1
26 下列那個樹狀結構不適合用於排序（sorting）？ (A) 最大堆積（max heap） (B) 最 小堆積（min heap） (C) 二元搜尋樹（binary search tree） (D) AVL tree ans:(D) 是因為插入刪除時 需要大量rotation的原因嗎@@ 感謝大大們解惑~~ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.195.194.244
→
03/24 20:07, , 1F
AVL只是平衡概念跟裡面的數值無關
03/24 20:07, 1F
推
03/24 20:41, , 2F
我覺得應該是要從時間複雜度的角度去思考
03/24 20:41, 2F
→
03/24 20:43, , 3F
AVL TREE也是一種BST 也可以利用中序追蹤來達到排序功能
03/24 20:43, 3F
推
03/25 11:22, , 4F
這題真奇怪 排序的時間複雜度都O(nlogn)呀
03/25 11:22, 4F
→
03/25 11:22, , 5F
轉去研所考題版問問
03/25 11:22, 5F
→
03/25 11:24, , 6F
建BST跟AVL都花O(nlogn) inorder=O(n), total=O(nlogn)
03/25 11:24, 6F
※ wsx02:轉錄至看板 Grad-ProbAsk 03/25 11:24
‣ 更多 panda555 的文章
文章代碼(AID): #1HJkGMcG (Examination)