[科普中國]-平衡二叉查找樹

平衡二叉搜索樹（英語：Balanced Binary Tree）是一種結構平衡的二叉搜索樹，即葉節(jié)點高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。

簡介平衡二叉搜索樹（英語：Balanced Binary Tree）是一種結構平衡的二叉搜索樹，即葉節(jié)點高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。它能在O()內(nèi)完成插入、查找和刪除操作，最早被發(fā)明的平衡二叉搜索樹為AVL樹。

常見的平衡二叉搜索樹有：

AVL樹

紅黑樹

Treap

節(jié)點大小平衡樹1

AVL樹在計算機科學中，AVL樹是最早被發(fā)明的自平衡二叉查找樹。在AVL樹中，任一節(jié)點對應的兩棵子樹的最大高度差為1，因此它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下的時間復雜度都是。增加和刪除元素的操作則可能需要借由一次或多次樹旋轉(zhuǎn)，以實現(xiàn)樹的重新平衡。AVL樹得名于它的發(fā)明者G. M. Adelson-Velsky和Evgenii Landis，他們在1962年的論文《An algorithm for the organization of information》中公開了這一數(shù)據(jù)結構。

節(jié)點的平衡因子是它的左子樹的高度減去它的右子樹的高度（有時相反）。帶有平衡因子1、0或 -1的節(jié)點被認為是平衡的。帶有平衡因子 -2或2的節(jié)點被認為是不平衡的，并需要重新平衡這個樹。平衡因子可以直接存儲在每個節(jié)點中，或從可能存儲在節(jié)點中的子樹高度計算出來。1

紅黑樹紅黑樹（英語：Red–black tree）是一種自平衡二叉查找樹，是在計算機科學中用到的一種數(shù)據(jù)結構，典型的用途是實現(xiàn)關聯(lián)數(shù)組。它是在1972年由魯?shù)婪颉へ悹柊l(fā)明的，他稱之為"對稱二叉B樹"，它現(xiàn)代的名字是在Leo J. Guibas和Robert Sedgewick于1978年寫的一篇論文中獲得的。1

本詞條內(nèi)容貢獻者為:

李嘉騫 - 博士 - 同濟大學