-
平衡二叉查找樹
鎖定
平衡二叉搜索樹(英語:Balanced Binary Tree)是一種結構平衡的二叉搜索樹,即葉節點高度差的絕對值不超過1,並且左右兩個子樹都是一棵平衡二叉樹。
- 中文名
- 平衡二叉查找樹
- 外文名
- Balanced Binary Tree
平衡二叉查找樹簡介
平衡二叉搜索樹(英語:Balanced Binary Tree)是一種結構平衡的二叉搜索樹,即葉節點高度差的絕對值不超過1,並且左右兩個子樹都是一棵平衡二叉樹。它能在O(
)內完成插入、查找和刪除操作,最早被髮明的平衡二叉搜索樹為AVL樹。
常見的平衡二叉搜索樹有:
平衡二叉查找樹AVL樹
在計算機科學中,AVL樹是最早被髮明的自平衡二叉查找樹。在AVL樹中,任一節點對應的兩棵子樹的最大高度差為1,因此它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下的時間複雜度都是
。增加和刪除元素的操作則可能需要藉由一次或多次樹旋轉,以實現樹的重新平衡。AVL樹得名於它的發明者G. M. Adelson-Velsky和Evgenii Landis,他們在1962年的論文《An algorithm for the organization of information》中公開了這一數據結構。
節點的平衡因子是它的左子樹的高度減去它的右子樹的高度(有時相反)。帶有平衡因子1、0或 -1的節點被認為是平衡的。帶有平衡因子 -2或2的節點被認為是不平衡的,並需要重新平衡這個樹。平衡因子可以直接存儲在每個節點中,或從可能存儲在節點中的子樹高度計算出來。
[1]
平衡二叉查找樹紅黑樹
- 詞條統計
-
- 瀏覽次數:次
- 編輯次數:3次歷史版本
- 最近更新: 一世长安品清茗