平衡二叉树（Balanced Binary Tree）

平衡二叉树（Balanced Binary Tree）的简介

平衡二叉树（Balanced Binary Tree）是二叉树（Binary Tree）中最重要的一种树结构。在前面的二叉搜索树中，我们提到，二叉搜索树（Binary Search Tree, BST）的搜索效率取决于树的形状。

在最坏的情况下，所有的元素都以增加key的方式（通常一个节点的key对应了一个值，搜索树就是与节点的key比较）来插入节点，会使得二叉搜索树像一个线性表（这时候它就是一个单枝树），它的搜索时间就是$O(n)$。

之前的博客也提到过，二叉搜索树的搜索、插入和删除时间都与二叉搜索树的高度有关，而其高度范围是：$\log_2(n) < h \leq n$。为了使得二叉查找树的查询效率好，我们希望树的高度越小越好。因此，就有了平衡二叉树（Balanced Binary Tree）。

两种平衡二叉树

平衡二叉树的定义有两种，一种是权重平衡树（Weight-Balancedness Tree, WBT），一种是高度平衡树（Height-Balancedness Tree, HBT）：