AVL树(自平衡二叉树)

发表于 分类于 阅读次数： 本文字数： 489 阅读时长 ≈ 2 分钟

特点

  • 二叉树
  • 同节点左右子树高度差不超过1

复杂度

  • 插入、查找、删除均为O(logN)

节点数

  • 最多(满二叉树) 2^h-1
  • 最少 2^(h-1)

规则

旋转：

  • 左旋：节点的左旋，节点的右孩子指针指向节点右孩子的左孩子，节点的右孩子的左孩子指针指向节点。
  • 右旋：节点的右旋，节点的左孩子指针指向节点左孩子的右孩子，节点的左孩子的右孩子指针指向节点。

平衡因子：

  • 平衡因子=左子树高度-右子树高度

导致AVL Tree不平衡的几种类型及调整方法:

插入：

  • LL：节点的左(L)子树的左(L)子树因为存在非空子节点，导致与节点的右子树高度差超过1 (右旋)
  • LR：节点的左(L)子树的右(R)子树因为存在非空子节点，导致与节点的右子树高度差超过1 (先左旋再右旋)
  • RL：节点的右(R)子树的左(L)子树因为存在非空子节点，导致与节点的左子树高度差超过1 (先右旋再左旋)
  • RR：节点的右(R)子树的右(R)子树因为存在非空子节点，导致与节点的左子树高度差超过1 (左旋)

删除：

  • 删除叶子结点，删除之后判断一下是否平衡
  • 删除只带有左子树或右子树的节点，直接把子树节点接上就行了
  • 删除带有左右子树的节点，找其左子树的最大节点或者是其右子树的最小节点交换值，然后删除被交换节点(规则跟删除叶子结点一样了)。选择左子树的最大节点还是右子树最小节点可以根据左右子树高度选择，优先选高的子树，这样更快趋于平衡。