查找算法【平衡二叉树】 - 简介

查找算法【平衡二叉树】 - 简介

【1】树高与性能的关系

二叉查找树的查找、插入、删除的时间复杂度均为O (logn )，但这是在期望的情况下，在最好情况和最坏情况下差别较大。

• 在最好情况下，二叉查找树的形态和二分查找的判定树相似，如下图中的左图所示。每次查找都可以缩小一半的搜索范围，查找最多从根到叶子，比较次数为树的高度logn 。

• 在最坏情况下，二叉查找树的形态为单支树，即只有左子树或只有右子树，如下图中的右图所示。每次查找的搜索范围都缩小为n -1，退化为顺序查找，查找最多从根到叶子，比较次数为树的高度n

二叉查找树的查找、插入、删除的时间复杂度均线性正比于二叉查找树的高度，高度越小，效率越高。

也就是说，二叉查找树的性能主要取决于二叉查找树的高度。

【所以问题有了，如何降低树的高度？】

【2】理想平衡与适度平衡

在最好情况下，每次都一分为二，左右子树的节点数均为n /2，左右子树的高度也一样。也就是说，如果把左右子树放到天平上，则是平衡的，如下图所示。

在理想状态下，树的高度为logn ，左右子树的高度一样，称之为理想平衡。但是理想平衡需要大量时间调整平衡以维护其严格的平衡性，可以适度放松平衡的标准，调整为大致平衡就可以了，称之为适度平衡。