平衡二叉树 调整的复杂度

Question

关于平衡二叉树插入或删除节点后的调整, 会有一种最坏状况.

比如插入点在最左端, 但唯一的空支在最右端, 如下图所示, 62个节点, 只有右下角一个空支, :

如果我要在这个平衡二叉树插入一个 "-1", 经过比较他首先成为 "0" 的左支, 就会导致不平衡, 为了重建平衡, 所有元素都会向右串, 直到最右端的空支被填补.

这个复杂度有多大? 还是说有更简单的方法? 我查了很多文章, 都是拿两三层的平衡二叉树来讲解左旋右旋, 为什么没有用大量数据举例的呢.

Answer 1

左子树与右子树的高度之差的绝对值小于等于1。
②左子树和右子树也是平衡二叉排序树。
引入平衡二叉排序树的目的，为了提高查找效率，其平均查找长度为O(log2n).
结点的平衡因子（ Balance Factor）定义为:结点的左子树深度与右子树深度之差。显然，对一棵平衡二叉排序树而言，其所有结点的平衡因子只能是-1、0或1.当在一个平衡二叉排序树上插入一个结点时，有可能导致失衡，即出现绝对值大于1的平衡因子。