Content #
插入20之后，从该叶子到树根路径上的所有节点，平衡因子都有可能改变，出现不平衡，有可能有多个节点的平衡因子的绝对值超过1。
从新插入的节点向上，找离新插入节点最近的不平衡节点，以该节点为根的子树被称为最小不平衡子树。只需将最小不平衡子树调整为平衡二叉树即可，其他节点不变。
平衡二叉树除了具有适度平衡性，还具有局部性：
- 在单次插入、删除后，至多有O(1)处出现不平衡；
- 总可以在O(logn)时间内，使这O(1)处不平衡重新调整为平衡。
最小不平衡子树
October 29, 2024