建设网工程信息湖南企业竞价优化服务

本节主要看板书

概念

AVL树（Adelson-Velsky and Landis tree）是一种自平衡二叉查找树，用于在动态集合中进行高效的插入、删除和查找操作。它保持树的高度接近最小可能值，从而确保这些操作的时间复杂度始终保持在O(log n)。AVL树以其发明者们的名字命名，即Georgy Adelson-Velsky和Evgenii Landis。

平衡因子

默认右－左

平衡因子绝对值不超过1

插入新元素后，平衡因子更新策略

旋转

单旋转（parent->bf*cur->bf＞0）

双旋（parent->bf*cur->bf  ＜  0）

板书