一点PHP分享介绍关于数据结构中二叉树以及平衡二叉树两种算法的区别。二叉树（binary）是一种最基本的树形数据结构，用来方便存储基本数据并且能有很高的查询效率，很多其他树形数据结构算法都是参考二叉树慢慢优化演变而来。其中包括平衡二叉树（AVL），平衡二叉树和二叉树的主要区别就是在于如何保持结构的平衡，如何更高效率的获取出数据。
二叉树（binary）
二叉树具有以下性质：左子树的键值小于根的键值，右子树的键值大于根的键值。
叶子根（root）节点为6，左边依次是3、2全部小于根（root）节点。右边依次是7、8全部大于根节点，完全符合上述对二叉树的描述，而左侧叶子节点3处又开叉左右两个分支，依旧符合规则左小右大2<3<5。
通过描述可以很容易理解出二叉树在数据查询中的优势高效率，不同的深度查询的IO次数将不一样，我们取平均值 (1+2+2+3+3+3) / 6 = 2.3次，效率非常高。
下面这个也符合二叉树的规则，所以也是二叉树，但是...
这棵二叉树的效果很明显会低很多，有的查询甚至需要5次io，平均计算也要（1+2+3+4+5+5）/6 = 3.3。虽然看着只是多一点点，如果数据量增大那效果将是非常明显的，并且就算多一次的IO操作也会对性能效率降低很多，所以这时候就需要引出平衡二叉树的概念。
平衡二叉树（AVL）
平衡二叉树（AVL树）在符合二叉查找树的条件下，它的任何节点的两个子树的高度最大差必须为1。下面的两张图片，左边是AVL树，它的任何节点的两个子树的高度差<=1；右边的不是AVL树，其根节点的左子树高度为3，而右子树高度为1
有些情况我们会对这种树进行插入或者删除，这个时候就会出现不平衡的情况，这时候就需要使用旋转的方式来让它继续保持平衡，而不同的结构旋转的方法也不同例如下面：
LL的旋转。LL失去平衡的情况下，可以通过一次旋转让AVL树恢复平衡。步骤如下：
- 将根节点的左孩子作为新根节点。
- 将新根节点的右孩子作为原根节点的左孩子。
- 将原根节点作为新根节点的右孩子。
RR的旋转：RR失去平衡的情况下，旋转方法与LL旋转对称，步骤如下：
- 将根节点的右孩子作为新根节点。
- 将新根节点的左孩子作为原根节点的右孩子。
- 将原根节点作为新根节点的左孩子。
RL的旋转：RL失去平衡的情况下也需要进行两次旋转，旋转方法与LR旋转对称，步骤如下：
- 围绕根节点的右孩子进行LL旋转。
- 围绕根节点进行RR旋转。
LR的旋转：LR失去平衡的情况下，需要进行两次旋转，步骤如下：
- 围绕根节点的左孩子进行RR旋转。
- 围绕根节点进行LL旋转。
一点PHP，每天一点技术分享。
