二叉排序树（Binary Sort Tree）或是一个空树，或是一棵具有如下性质的二叉树：

  • 若它的左子树不为空，则左子树上的所有节点的值均小于它根节点的值。
  • 若它的右子树不为空，则右子树上的所有节点的值均大于它根节点的值。
  • 它的左子树和右子树也分别为二叉排序树

二叉排序树又称二叉查找树，根据上述定义的结构特点可见，它的查找过程如下，即当二叉排序树不空时，首先将给定值和根结点的关键字比较，若相等，则查我成功，否则将依据给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上继续进行查找。

二叉排序树具有快速查找的能力，通常在理想情况下，查找、插入和删除操作的时间复杂度为 O(log n)。但是，如果树不平衡，最坏情况下会退化成链表，导致时间复杂度会降为 O(n)

一、平衡二叉树

平衡二叉树（Balanced Binary Tree）是一种二叉搜索树，它通过在每个节点上保持左右子树高度的平衡来保证树的高度尽可能小，以提高查找、插入和删除操作的效率。

在普通的二叉搜索树中，树的高度不受限制，可能出现极端情况下树变得非常不平衡，例如退化成链表，这时查找、插入和删除的时间复杂度下降为 O(n)，而平衡二叉树通过保持一定的平衡性来避免这种情况。

在平衡二叉树中，任何节点的左右子树的高度差不能超过一定的限度（例如 1），以此来避免树在某些情况下退化成链表，导致操作效率下降。

常见的平衡二叉树包括以下几种类型：

  • AVL 树，是一种保持严格平衡的二叉搜索树，要求任意节点的左右子树高度差不超过 1，AVL 树中每个节点都有一个平衡因此（左右子树高度差的绝对值），当插入或删除节点导致某个节点的平衡因子不再满足平衡条件（平衡因子大于1）时，通过旋转操作（单旋转或双旋转）对树的结构进行调整。
  • 红黑树，是一种弱平衡的二叉树，相比AVL树，红黑树允许一定程度的不平衡。它通过为每个节点增加颜色属性（红或黑），并定义了一系列颜色规则来保证树的平衡。红黑树的高度最多为 2 log⁡ n，因此查找、插入和删除的时间复杂度始终保持在 O(log⁡n)
  • B 树 和 B+ 树

二、旋转操作

二叉排序树的旋转操作主要用于平衡二叉树，例如在红黑树和 AVL树中。旋转操作通过调整节点的相对位置来减少树的高度，从而提高查找、插入、删除等操作的效率。

1、左旋

触发条件：当插入或删除操作导致某个节点的右子树比左子树高 2，并且插入的节点位于失衡节点的右子树的右子节点上（右-右失衡）

操作：将失衡节点的右子节点上移成为根节点，原根节点成为其右子节点（新根节点）的左子节点

上图中的示例，按照插入的先后顺序，依次插入了节点 20、23、25，在插入节点 25 之后根节点 20 的右子树的高度比左子树高度大 2，并且 25 为 23 节点的右子节点，因此需要进行左旋。

2、右旋

触发条件：当插入或删除操作导致某个节点的左子树比右子树高 2，并且插入的节点位于失衡节点的左子树的左子节点上（左-左失衡）。

操作：将失衡节点的左子节点上移成为根节点，原根节点成为其左子节点（新根节点）的右节点

上图中的示例，按照插入的先后顺序，依次插入了节点 25、23、20，在插入节点 20 之后根节点 25 的左子树高度比右子树高度大 2，并且 20 为 23 节点的左子节点，因此需要进行右旋。

3、先左旋后右旋

触发条件：当插入或删除操作导致某个节点的左子树比右子树高 2，并且插入的节点位于失衡节点的左子树的右子节点上（左-右失衡）

操作：先对失衡节点的左子树进行一次左旋，然后对失衡节点进行一次右旋

上图中的示例，按照插入的先后顺序，依次插入节点 20、15、18，在插入节点 18 之后根节点 20 的左子树高度比右子树高度大 2，并且 18 为 15 节点的右子节点，所以要先对失衡节点 20 的左子树进行左旋，即节点 15 和节点 18 进行一次左旋，左旋结束后再对失衡节点 20 进行一次右旋。

4、先右旋后左旋

触发条件：当插入或删除操作导致某个节点的右子树比左子树高 2，并且插入的节点位于失衡节点的右子树的左子节点上（右-左失衡）

操作：先对失衡节点的右子树进行一次右旋，然后对失衡节点进行一次左旋

上图中的示例，按照插入的先后顺序，依次插入节点 20、25、23，在插入节点 23 之后根节点 20 的右子树高度比左子树高度大 2，并且 23 为 25 节点的左子节点，所以要现对失衡节点 20 的右子树进行一次右旋，即节点 25 和节点 23 进行一次右旋，右旋结束后再对失衡节点 20 进行一次左旋。

5、总结

  • 左旋：适用于右-右失衡，即新节点插入到右子树的右子树时。
  • 右旋：适用于左-左失衡，即新节点插入到左子树的左子树时。
  • 先左后右旋：适用于左-右失衡，即新节点插入到左子树的右子树时。
  • 先右后左旋：适用于右-左失衡，即新节点插入到右子树的左子树时。

相关链接

OB tags

#数据结构 #二叉树