平衡二叉树(AVL)
基本概念
平衡二叉树(Balanced Binary Tree)
又称AVL树.二叉排序树的查找算法性能取决于二叉树的结构,假如数据有序排列,则会出现斜树的情况,二叉排序树退化成线性,查找的时间复杂度为O(n),如果二叉排序树的左右两个子树之间的高度差越小，那么查找性能越好,为O(log2n)。
平衡二叉树具有以下性质
左子树和右子树的高度差不超过1
特征是递归的,即左子树和右子树也是平衡二叉树
平衡二叉树中引入了平衡因子(Balance Factor)的概念,即某个结点的左子树高度减去右子树高度差,平衡因子只能为-1、0、1,其绝对值不能大于1。
平衡二叉树的调整
对树插入一个新结点时,可能会出现破坏树平衡的情况,这时就需要调整树。
调整方法一共有四种(RR、LL、LR、RL)。
调整类型第一位代表插入点在失衡点的哪一侧,第二位为插入点在失衡点孩子的哪一侧。
RR调整
使中间结点成为父结点,左孩子为失衡点,如果它有左孩子的话,那么这个左孩子插到失衡点的右孩子上面。
LL调整
使中间结点成为父结点,右孩子为失衡点,如果它右孩子的话,那么这个右孩子插到是失衡点的左孩子上面。
LR调整
使插入点作为父结点,失衡点成为插入点的右孩子,左孩子为自身父结点.如果插入点有左、右孩子，原先的左孩子插到自身父结点的右孩子上，原先的右孩子插到失衡点的左孩子上。
RL调整
使插入点作为父节点,失衡点成为插入点的左孩子,右孩子为自身父结点.如果插入点有左、右孩子,原先的左孩子插到失衡点的右孩子上,原先的右孩子连接到自身父结点的左孩子上。
