※ 引述《one1130 (小柔)》之銘言：
: 我想問一下各位大大
: 我現在要寫個具有英譯德及德譯英之雙向字典
: 以binary search tree建立以提升查詢速度,
: 然後
: 字典內容由一input file 叫hw2.in輸入
: 字典的功能: 新增.刪除.修改.翻譯查詢(德英互翻)
: 那請問我要怎麼寫這各程式
: 非常感恩
我要先裝熟一下，
我幾天前系上學弟也因為一模一樣的作業題目有問題來問我，
如果真的這麼巧的話，我會說有興趣的話可以來北極光切磋討論。XD
基本上我自己是覺得這個問題用BS比較好做啦，
不過他們助教認為BST比較方便，what ever 反正差異在資料的結構上。
你要寫的程式喔，把握一個重點，雙向的意思就是key跟value互換，
也就是排序的依序是不同的，我會建議你用兩個list維護。
如果BS的話基本上排序資料然後用BS找到插入點跟目標就好。
BST的話要實做樹狀結構(跟LinkedList有點像，去翻翻資結書)，
用root對資料作比對，依序對樹做travel。
我自己在觀摩這題時是有做語言跟語系的相關介面，
字典是採用"主要語言"的方式來區隔德英跟英德，
這樣比較方便擴展三種以上的單字查詢，這是題外話就是了。
---
話說我本來是明天要跟學弟去跟助教聊一下這個問題，順便也在這裡聊一聊好了。
寫樹狀結構的實做成本不計(假設結構都已經做好了)，
以Binary Search應用在排序的List上，新增應該是O(log2N)，刪除也是O(log2N)。
查詢跟刪除是一樣的嘛，也是O(log2n)
BST 根據我的認知要在best case(每一顆樹剛好二分左右子樹總數)
才是 log2n (也就是 Ω(log2n))
worst case 是 O(n) (剛好是形成一個完全傾斜的樹)
不管怎麼看，BS好像都比BST好做吧，
因為助教是說BST在新增刪除方面比較容易使用，
所以我在想是不是有甚麼成本我沒算到。
是有想到，
是差在插入跟刪除還有指到特定目標的成本嗎(在LinkedList時指定元素要一一循覽)
ArrayList則是刪除時後面跟著往前移動，以及新增時跟著往後挪。
我在想是不是因為這兩個因素，如果有人對這個結構比較熟的可以討論一下，
很多成本都很容易讓人遺忘啊Q_Q
--
▄▅▆▇███▇▆▅▄▃ ╰┼╯─╮ ╮
◥███████████◣ ╰┼╯＝│=│
◥██████───────◣ ＊． ╯ ╯ ╯ の 物 語 ．＊
◥███████──────◣ ～ ◢◣ ◢◣
◥██████───────◤ ◥◤＊ 空白的世界．翼 ＊◥◤
◥██▁▂▃▄▅▆▇███▆▅▄▃▂▂～telnet://tony1223.no-ip.info
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.132.59.247