什么是平衡二叉树（怎么判断一个二叉树是平衡二叉树）

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。常用算法有红黑树、AVL、Treap、伸展树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O（log2n），大大降低了操作的时间复杂度。