3.3 平衡二叉树（AVL树、红黑树）

文档摘要

3.3 平衡二叉树（AVL树、红黑树） 3.3 平衡二叉树 (AVL树、红黑树) 二叉搜索树（BST）虽然提供了高效的查找、插入和删除操作，但在最坏情况下，其时间复杂度会退化为 O(n)（例如，当所有节点都插入到树的一侧时，形成一个链表）。为了解决这个问题，平衡二叉树应运而生。平衡二叉树通过维持树的平衡，确保在任何情况下，查找、插入和删除操作的时间复杂度都能保持在 O(log n)。本节将深入探讨两种常见的平衡二叉树：AVL 树和红黑树。 3.3.1 AVL 树 3.3.1.1 定义与性质 AVL 树（Adelson-Velsky and Landis Tree）是一种自平衡二叉搜索树。它得名于其发明者 G. M. Adelson-Velsky 和 E. M. Landis。