与二叉搜索树不同之处是结点结構里多了平衡因子

要么是二叉搜索树要么是空树
左右子树的高度差不超过一
左右子树都是平衡二叉树

树的高度等于左子树高度与右子树高喥的最大值

平衡二叉树插入结点后可能会导致失衡

此时就要调整离插入结点最近的失衡的树 , 失衡的四种情况有不同的应对方式

• 左单旋 : 失衡嘚树的左子树的左子树比较高
  左子树的右子树变成根结点的左子树
  根结点变成左子树的右子树
  然后更新新的根结点的平衡因子后返回
  

• 右单旋 : 失衡的树的右子树的右子树比较高
  然后和左单旋一样 , 只是操作对象反过来了
  

• 左-右双旋 : 失衡的树左子树的右子树比较高 , 左子树的右子树先祐单旋一次 , 左子树再左单旋一次
• 右-左双旋 : 失衡的树右子树的左子树比较高 , 右子树的左子树先左单旋一次 , 右子树再右单旋一次