[TOC] ## 概述 二叉查找樹的樹高度影響了查找的效率，需要盡量減小樹的高度，AVL樹正是這樣的樹。 AVL樹是一棵嚴格自平衡的二叉查找樹,這是較早發明的平衡二叉樹。 為了維持AVL樹的特征，每次添加和刪除元素都需要一次或多次旋轉來調整樹的平衡。調整的依據來自于二叉樹節點的平衡因子：節點的左子樹與右子樹的高度差稱為該節點的平衡因子，約束范圍為`[-1，0，1]`。 ## AVL樹添加元素 1. 在右子樹上插上右兒子導致失衡，左旋，轉一次。 2. 在左子樹上插上左兒子導致失衡，右旋，轉一次。 3. 在左子樹上插上右兒子導致失衡，先左后右旋，轉兩次。 4. 在右子樹上插上左兒子導致失衡，先右后左旋，轉兩次。