简介

二叉搜索树会按顺序保存值：每个节点的左子树中保存较小的值，右子树中保存较大的值。这样的顺序可以让搜索变快，但前提是树大致保持平衡。如果按排序顺序向普通二叉搜索树中插入值，它就会退化成一条直线，让每次搜索都变成缓慢的线性扫描。

AVL 树会自动保持平衡，从而解决这个问题。每次插入或删除后，它都会检查是否有节点变得不平衡；如果有，就执行一种称为旋转的小型局部调整来恢复平衡。无论你如何构建它，AVL 树都不会退化成一条直线。

在本课程中，你将用自己喜欢的语言从头构建一棵 AVL 树：包含跟踪高度的节点、平衡检查、四种旋转情况，以及能够自动保持平衡的插入和删除操作。然后，你将使用完成的类来解决一组练习挑战。