資料結構中的二叉樹作為字典

當我們嘗試實現抽象資料型別字典時，節點將與值相關聯。字典基本上是一組鍵，該鍵必須是從全序集合中選出的元素。可能與每個鍵相關聯的其他資訊，但這不會導致任何概念理解。

如果使用樹實現字典，那麼每個節點將儲存唯一鍵。在這裡，對於樹中的每個節點 u，每個鍵 u.l 嚴格小於 u.k。並且 u.r 中的每個鍵嚴格大於 u.k。一棵樹根據這種被稱為二叉查詢樹的不變性進行組織。

這種不變性的一個主要優勢是，可以使用中序遍歷線上性時間內查詢已排序的鍵列表。這可以如下遞迴定義——一棵空樹，什麼也不做，否則首先在左子樹上遞迴，取根，並報告它。然後遞迴到右子樹。

我們可以對二叉查詢樹執行多項操作。搜尋可以基於樹的高度進行。搜尋是所有其他操作中更重要的操作。

更新於：2020 年 8 月 11 日

887 次瀏覽

職業生涯啟航

完成課程並獲得認證

開始
廣告