平衡二叉树
平衡二叉树简介
平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构。
平衡二叉树性质
平衡二叉树是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
平衡二叉树特性
非叶子节点最多拥有两个子节点。
非叶子节点的值大于左边子节点、小于右边子节点。
树的左右两边的层级数相差不会大于 1 。
没有值相等重复的节点。
平衡二叉树的层级结构
平衡二叉树查询性能和树的层级（高度）成反比，高度值越小查询越快。
为了保证树的结构左右两端数据大致平衡降低二叉树的查询难度一般会采用一种算法机制实现节点数据结构的平衡，实现了这种算法的有比如Treap、红黑树，使用平衡二叉树能保证数据的左右两边的节点层级相差不会大于 1 ，通过这样避免树形结构由于删除增加变成线性链表影响查询效率，保证数据平衡的情况下查找数据的速度近于二分法查找。