(一)AVL 树 AVL 树是平衡二叉查找树,增加和删除节点后通过旋转重新达到平衡,旋转包括左旋和右旋。左旋是以某节点为中心,将它沉入当前左子节点的位置,而让当前的右子节点作为新树的根节点,称为逆时针旋转,右旋同理。 (二)红黑树 每个节点上有一个颜色属性,是红色或黑色。红黑树通过重新着色和左右旋转,高效地实现了平衡调整。 红黑树本质上是二叉查找树,额外引入了 5 个约束条件:① 节点只能是红色或黑色。② 根节点必须是黑色。③ 所有 NIL 节点都是黑色的。④ 一条路径上不能出现相邻的红色节点。⑤ 在任何递归子树中,根节点到叶子节点的所有路径上包含相同数目的黑色节点。这五...