Adelson-Velskii和Landis树：带有平衡条件的二叉查找树。平衡条件要容易保持，而且它须保证树的深度是O(logN)。最简单的想法是左右子树具有相同的高度。还有一种是要求每个结点都必须要有相同高度的左子树和右子树。一颗AVL树是其每个节点的左子树喝右子树的高度最多差一的二叉查找树。
在插入以后，只有那些从插入点到根节点的路径上的节点的平衡可能发生改变，我们上行到根可以找到一个节点，它的新平衡破坏了AVL条件我们需要在这个点，重新定义AVL特性。这个节点叫a。不平衡条件可能出现以下四种情况：
对于1，4是发生在外边的情形(即左-左或右-右)，我们进行单旋转(single rotation)调整，对于2，3是发生在内部的情形(即左-右或右-左)，我们进行双旋转(double roration)调整。
用通俗的话来说就是找到破环平衡的那个点，然后把他高度大的儿子往上提一层，自己下降一层，就稳定了AVL的平衡性质
内部我们使用俩次相反的旋转，比如情况2，他是对a左-右的插入，我们就进行先左旋转一次，再右旋转一次，即可调整至平衡
本文地址：https://blog.csdn.net/xiguanlant/article/details/107310460
如对本文有疑问， 点击进行留言回复！！
MySQL-关系代数-并、交、差、等值连接、自然连接、左连接。。。
【MySQL牛客】10.获取所有非manager的员工emp_no
我要评论
网友评论