背景 在传统的平衡二叉查找树（Binary Search Tree）中，最坏的情况下树可能退化成链表，这时候查找效率大大降低，时间复杂度直接降到O(n); 此后，AVL树诞生了，它是一种严格的自平衡二叉查找树，它可以保证树在进行操作时保持O(logn)，但是它在插入和删除节点需要进行较多的旋转操作来维持平衡，使得维护成本较高； B树 --> …