平衡二进制搜索树（AVL）

从二叉搜索树BST可以看出，如果将数据存储在“深度”节点上，则搜索开销将非常大. 您可以调整树的结构以查询所有数据吗？时间几乎是平衡的.

平衡二叉树AVL解释: 这两个人的Adelson-Velsky和E.M. Landis的缩写在他们的文章“一种用于组织信息的算法”中提到了该算法.

平衡二叉树要求每个节点的左右子树的高度之差不能超过1，如果插入或删除节点以使高度之差大于1平衡二叉排序树，则必须旋转节点并转换二叉树保持平衡状态. 该解决方案解决了二叉搜索树退化为链表的问题，并在O（logN）处保持了最佳，最坏情况下插入，搜索和删除的时间复杂度. 但是频繁的轮换会使插入和删除操作牺牲O（logN）时间，但是与二叉树查询相比，时间要稳定得多.

！ [2012082016003157.jpg]（％7CimageView2 / 2 / w / 1240）

平衡二叉树的大多数过程与二叉搜索树的过程相同. 不同之处在于，插入和删除后，将写入轮换算法以保持平衡. 需要一个节点高度属性来保持平衡.

AVL树旋转法则

1. LL类型

将新节点插入平衡二叉树的一个节点的左子节点的左子树中，从而使该节点不再平衡. 此时，只需将树向右旋转一次，如图所示，原始A的左子树B成为父节点，A成为其右子树，原始B的右子树成为A Tree的左子树，请注意，旋转后，Brh是A的左子树: （浅红色的尾巴是添加子树的节点）

2. RR类型

将新节点插入平衡二叉树的某个节点的右子节点的右子树中，从而使该节点不再平衡. 此时平衡二叉排序树，您只需将树向左旋转一次，如图所示，原始A的右子树B成为父节点，A成为其左子树，原始B的左子树Blh将变为A右子树:

3. LR型

将新节点插入平衡二叉树的某个节点的左子节点的右子树中，从而使该节点不再平衡. 此时，需要进行两次旋转，并且只有一次旋转无法再次平衡二叉树. 如图所示，B节点根据RR类型向左旋转一次后，二叉树仍然无法保持A节点的平衡，此时需要再次向右旋转:

4. RL类型

将新节点插入平衡二叉树的某个节点的右子节点的左子树中，从而使该节点不再平衡. 同样，它此时需要旋转两次，旋转方向与LR类型完全相反:

Java实现:

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-197352-1.html