在計(jì)算機(jī)科學(xué)中，AVL樹是最早被發(fā)明的自平衡二叉查找樹。

在AVL樹中，任一節(jié)點(diǎn)對應(yīng)的兩棵子樹的最大高度差為1，因此它也被稱為高度平衡樹。增加和刪除元素的操作則可能需要借由一次或多次樹旋轉(zhuǎn)，以實(shí)現(xiàn)樹的重新平衡。

AVL樹得名于它的發(fā)明者G. M. Adelson-Velsky 和Evgenii Landis，他們在1962年的論文《Analgorithm for the organization of information》中公開了這一數(shù)據(jù)結(jié)構(gòu)。

（引用自wiki）

二叉搜索樹一定程度上可以提高搜索效率，二叉搜索樹的查找效率取決于樹的高度，因此保持樹的高度最小，即可保證樹的查找效率。故而當(dāng)節(jié)點(diǎn)數(shù)目一定，保持樹的左右兩端保持平衡，樹的查找效率最高。這種樹就是平衡二叉樹。

平衡二叉樹，是一種二叉排序樹，其中每一個(gè)結(jié)點(diǎn)的左子樹和右子樹的高度差至多等于1。

從平衡二叉樹（Self-BalancingBinary Search Tree 或Height-Balancing BinarySearch Tree）的英文名字來看，它是一種自動(dòng)平衡或高度平衡的二叉搜索樹。

自平衡是指，在對平衡二叉樹執(zhí)行插入或刪除節(jié)點(diǎn)操作后，可能會(huì)導(dǎo)致樹中某個(gè)節(jié)點(diǎn)的平衡因子絕對值超過1，即平衡二叉樹變得“不平衡”，為了保持該節(jié)點(diǎn)左右子樹的平衡，需要做一些必要的操作。

那什么叫做高度平衡呢?

意思是說，要么它是一棵空樹，要么它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的高度之差的絕對值不超過1。我們將二叉樹上結(jié)點(diǎn)的左子樹高度減去右子樹高度的值稱為平衡因子BF(BalanceFactor)，那么平衡二叉樹上所有結(jié)點(diǎn)的平衡因乎只可能是-1、0和1。只要二叉樹上有一個(gè)結(jié)點(diǎn)的平衡因子的絕對值大于1 ，則該二叉樹就是不平衡的。

①如下圖，為什么圖1是平衡二叉樹，而圖2不是？

這里就是考查我們對平衡二叉樹的定義的理解，它的前提首先是一顆二叉排序樹，圖2中結(jié)點(diǎn)45比結(jié)點(diǎn)40大，卻是結(jié)點(diǎn)40的左子樹，這不符合二叉排序樹的定義，更不能是平衡二叉樹。

②如下圖，為什么圖4是平衡二叉樹，而圖3不是？

首先圖3、圖4都是二叉排序樹，但圖3中結(jié)點(diǎn)40的左子樹高度為3，而右子樹為空，二者差大于了絕對值1，因此它是不平衡的。而進(jìn)行適當(dāng)?shù)恼{(diào)整后圖4，它就符合了定義，因此圖4是平衡二叉樹。

距離插入結(jié)點(diǎn)最近，且平衡因子的絕對值大于1的結(jié)點(diǎn)為根的子樹，我們稱為最小不平衡子樹。如下圖中，當(dāng)新插入結(jié)點(diǎn)21時(shí)，距離它最近的平衡因子絕對值超過1的結(jié)點(diǎn)是40（即結(jié)點(diǎn)40的左子樹高度3減去右子樹高度1的結(jié)果大于1），所以從結(jié)點(diǎn)40開始以下的子樹為最小不平衡子樹。

今天帶大家初步認(rèn)識了什么是平衡二叉樹，之后會(huì)帶大家了解平衡二叉樹實(shí)現(xiàn)原理。

西安盛圖科技

高端IT培訓(xùn)第一品牌