資料結構中的平衡二叉查詢樹

在此，我們將瞭解平衡二叉查詢樹是什麼。二叉查詢樹 (BST) 是二叉樹，其左子樹具有較小的元素，而右子樹具有較大的元素。

在 BST 中搜索元素的平均時間複雜度為 O(log n)。它取決於二叉查詢樹的高度。為了維護二叉查詢樹的屬性，有時樹會變得傾斜。因此，傾斜的樹將如下所示 −

這實際上是一棵樹，但看起來更像是一個連結串列。對於這種樹，搜尋時間將為 O(n)。這對於二叉樹來說是無效的。

為了克服這些問題，我們可以建立一棵高度平衡的樹。這樣，樹就不會傾斜。我們必須強行讓它們保持平衡。因此，每個節點的每一側都會儲存一顆子樹，其高度幾乎相同

有多種平衡技術。其中一些是 −

  • AVL 樹

  • 紅黑樹

上述示例的高度平衡形式將如下所示 −

更新於：10-8-2020

792 次檢視

開啟你的 職業生涯

完成課程獲得認證

開始
廣告