申論題

三、在電腦網路中，透過IP位址以查詢對應的裝置是常見的動作。今某電腦網路有以下表格所示的IP位址以及對應裝置（假設每個IP位址有8個位元），當輸入某一IP位址以查詢對應的裝置時，最壞情況為此表格中的每個IP位址的每個位元皆需要搜尋一次，以確認此輸入的IP位址是否有對應的裝置。由於這樣的IP位址儲存方式，將造成查詢時的高複雜度（例如，若表內有m個IP時，查詢的複雜度為m*8），因此運用適當的資料結構以減低查詢複雜度，已成為電腦網路的重要課題。
試建立並驗證一個樹狀資料結構，不僅可以儲存以上表格方式的IP位址以及對應裝置資訊，並可使得查詢IP位址所對應的裝置的最壞情況複雜度維持在常數8（也就是IP位址位元數） 。（25分）