JAVA小项目之平衡二叉树的实现
借鉴的博客：
平衡二叉树（AVL树）深入解读：https://blog.csdn.net/qpzkobe/article/details/81611486
一.为什么需要平衡二叉树
我们知道，对于二叉查找树，树的层数越少，查找数据的平均查找时间就会越少。但是二叉排序树在很多情况下都不能保证树的高度是最优的，例如在极端情况，如果插入排序树的数据是有序数据，那么二叉树就会退化成为单链，
这时查找的时间复杂度也退化成O(n)的了。为了解决这个问题，我们希望二叉树是尽量平衡的，也就是说对于树中的任意一个结点，都能使其左子树上结点的个数和右子树上结点的个数相差不太多，这时我们就需要平衡二叉树。
平衡二叉树的目的是对二叉查找树进行平衡化，以保证树的高度比较优化，从而保证了对树进行操作的时间复杂度不会退化。 在二叉搜索树的插入和删除运算中，采用平衡二叉树
优点：对二叉查找树进行平衡化，以保证树的高度比较优化，从而提高查找运算的速度。
缺点：使得插入和删除运算变得复杂化，从而降低了他们的运算速度，另外二叉搜索树删除节点而引起的不平衡性进行的操作比插入节点的情况要复杂。 二.什么是平衡二叉树
平衡二叉树也叫AVL树。它的发明者是G.M.Adelson-Velsky和E.M.Landis，他们在1962年的论文"Analgorithm for the organization of information"中发表了AVL树。
平衡二叉树是具有以下性质的二叉查找树：对于树中的任意一个结点，都有该结点的左子树的高度与右子树的高度之差的绝对值小于2。与普通的BST相比，AVL树多定义了旋转操作，使得当左右子树的高度差的绝对值大于或者等于2时，平衡树可以自动地进行树形调整，以重新满足上述性质。
相关名词：
平衡因子：每个结点的平衡因子就是该结点的左子树的高度减去右子树的高度，平衡二叉树的每个结点的平衡因子的绝对值不会超过2。 最小不平衡子树：指离插入节点最近、且平衡因子绝对值大于1的节点做根的子树。
遇到的知识点：
泛型的好处：
• 能够在编译时检查类型安全
• 所有的强制转换都是自动和隐式的，取出代码后，不用再进行强制类型转换
• 能够在编译时检查类型安全
• 所有的强制转换都是自动和隐式的，取出代码后，不用再进行强制类型转换
-----End
投递美团等公司10个岗位 >