試建立並驗證一個樹狀資料結構，不僅可以儲存以上表格方式的IP位址以及對應裝置資訊，並可使得查詢IP位址所對應的裝置的最壞情況複雜度維持在常數8（也就是IP位址位元數） 。（25分）
此題重點為：最壞情況複雜度維持在IP位址位元數
其中搜尋樹Trie（俗稱字典樹）剛好符合最壞情況 O(k) 的要求（k為字符長度）
畫法如下（以A、B為例）
点点赞赏，手留余香
给TA打赏
三、在電腦網路中，透過IP位址以查詢對應的裝置是常見的動作。今某電腦網路有以下表格所示的IP位址以及對應裝置（假設每個IP位址有8個位元），當輸入某一IP位址以查詢對應的裝置時，最壞情況為此表格中的每個IP位址的每個位元皆需要搜尋一次，以確認此輸入的IP位址是否有對應的裝置。由於這樣的IP位址儲存方式，將造成查詢時的高複雜度（例如，若表內有m個IP時，查詢的複雜度為m*8），因此運用適當的資料結構以減低查詢複雜度，已成為電腦網路的重要課題。
内容查看
評論0