什么是 AVL 树？

AVL 树中的每个节点都会跟踪自己的高度：从该节点向下到叶节点的最长路径上的边数。叶节点的高度为 1，空子树的高度为 0。根据节点两个子节点的高度，你可以计算出它的平衡因子：height(left) - height(right)。

当节点的平衡因子为 -1、0 或 1 时，该节点是平衡的。AVL 树的规则很简单：每个节点都必须始终保持平衡。每当插入或删除操作使某个节点的平衡因子变为 2 或 -2 时，树就会执行旋转：局部调整几个指针，在常数时间内恢复平衡，同时不破坏二叉搜索树的顺序。

旋转有四种情况（左左、右右、左右、右左），但归根结底都由两个基本操作组成：单次左旋和单次右旋。接下来的几节课中，你将从头开始实现这两种操作。