binary search tree, AVL, and red-black tree

鉴于红黑树在实际应用中的普遍性，相关树结构在面试过程中极有可能被频繁涉及，此处先对相关内容进行简要归纳，如后续有补充需求可另行添加。

1. 二叉查找树

无话可言。

2. 平衡二叉树（AVL树）

定义

为防止二叉搜索树的高度增长过快，在进行节点插入与删除操作时，需确保每个节点的左右子树高度差控制在1以内，满足这一条件的二叉搜索树被称为平衡二叉搜索树。这类结构具备自动调整平衡能力的二叉搜索树特性，通常也称为AVL树，其名称来源于两位发明者G.M. Adelson-Velsky与E.M. Landis。

插入操作

对概念的理解并不困难，关键在于插入或删除操作过程中，如何借助旋转机制维持树结构的平衡性？具体可分为三个步骤进行：

• 首先按照二叉搜索树的插入规则将节点添加至合适位置
• 然后判断该操作是否破坏了AVL树的平衡特性，若存在失衡现象，则需在插入节点的父节点中定位首个出现不平衡状态的节点A
• 最后对以节点A为根的子树进行结构调整，使其恢复平衡状态，至此问题便得以解决。（该子树被称作最小不平衡子树，其含义应当较为直观）

可以明确地告知你，此时整棵树已恢复平衡状态，若存疑不妨亲自模拟各类情形加以验证。其中最具挑战性的部分在于调整操作的具体实施方式，值得庆幸的是前人已将其归纳为以下四种典型情形