第1个回答 2022-06-27
平衡二叉搜索树是一种结构平衡的二叉搜索树，即叶节点高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。能在 内完成插入、查找和删除操作，最早被发明的平衡二叉搜索树为AVL树。
节点的平衡因子是它的左子树的高度减去它的右子树的高度。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
距离插入点最近的，且平衡因子的绝对值大于1的结点为根的子树，我们称为最小不平衡子树。
在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因为插入而破坏了树的不平衡性，若是，则找到最小不平衡子树。在保持二叉排序特性的前提下，调整最小不平衡子树各结点之间的链接关系。进行相应的旋转,使其成为新的平衡子树。
若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。