数据结构之平衡二叉树
数据结构之平衡二叉树
对于数据集查找，分为两种情况：
- 无序的顺序查找，查找效率慢，插入、删除时不用考虑其它，效率较高；
- 有序的查找，优化查找很多，但插入、删除时效率低；
二叉排序树
所以提出了二叉排序树的数据结构来高效的完成插入、删除和查找。
二叉排序树的定义：
二叉排序树的总结
对于左右两边平衡的二叉树，其查找效率最高，极端的单线二叉树效果最差。
平衡二叉树（AVL树）
平衡二叉树是为了解决上述问题的二叉树。
定义
平衡二叉树也是一种二叉排序树，其每个结点的左右子树高度差至多等于。
平衡因子BF：节点的左子树深度减去右子树深度的。
平衡二叉树每个节点的BF只能取（-1，0，1）。
当最小平衡子树的根节点BF>1时，子树右旋，当BF<-1时，子树左旋；
当最小平衡子树与它的子树BF不同符号时，先对结点进行旋转使其符号一致后，再反向旋转。