如何实现【数据结构与算法】中的手撕平衡二叉树？

本文共计2330个文字，预计阅读时间需要10分钟。

平衡二叉树定义：二叉树中任意节点的左右子树高度差不超过1。

操作实践：二叉查找树的查找操作复杂度由树的高度决定，因此希望控制树的高度，使左右子树尽可能平衡。

平衡二叉树（AVL树）：称一棵二叉查找树为高度平衡树，当且仅当它满足以下性质：任意节点的左右子树高度差不超过1。

平衡二叉树 定义

• 动机：二叉查找树的操作实践复杂度由树高度决定，所以希望控制树高，左右子树尽可能平衡。

• 平衡二叉树（AVL树）：称一棵二叉查找树为高度平衡树，当且仅当或由单一外结点组成，或由两个子树形 Ta 和 Tb 组成，并且满足：

  • |h(Ta) - h(Tb)| <= 1，其中 h(T) 表示树 T 的高度
  • Ta 和 Tb 都是高度平衡树

即：每个结点的左子树和右子树的高度最多差 1 的 二叉查找树。