
3.12 以紅黑樹實作有序關聯查表
|
125
這個功能讓遊歷演算法不一定要輸出所有節點。例如,除了
Sow
指令之外,你可以傳入
某函數將節點值寫入檔案,或如下列方式篩選節點的輸出。
延伸資訊
樹狀結構及其遊歷方式詳見資料結構專書,或網頁:
http://bit.ly/7xP6jQ
。
3.12 以紅黑樹實作有序關聯查表
問題點
你需要比線性搜尋更具效率的查表與儲存方法以增進程式效能,你也希望這些元素具有
一定的順序。
解決方案
紅黑樹在關聯性資料結構中是很受歡迎的樹狀結構演算法。想在 Mathematica 中實作紅
黑樹,需建立樹狀結構表示法及建立(creating)、讀取(reading)、修改(updating)及
刪除(deleting)元素的指令集(CRUD)。本範例以
rbTree
作為標頭,其內部包含樹狀
結構及順序關係。紅黑樹模型為空串列或四個元素的串列,包含顏色(紅或黑)、左子
樹、節點元素與右子樹。以下範例以
小於
Less
作為預設順序關係。將順序關係儲存於
模型中,可允許紅黑樹改變元素的內容。[Page-126]
以預設順序函數建立空結構
以自訂順序函數建立空結構
以指定根元素與自訂順序函數建立空結構
ch03.indd 125 2014/4/2 上午 05:19:20