有关BST搜索树转换为AVL高度平衡树的旋转问题

最近在复习数据结构,看到BST的时候遇到了问题,就是当删除或增加树中节点时,要求保证树的高度平衡行,也就是使BST成为AVL。


后来看了很多资料,说会,RR, LR, RL啥的,没看懂。之后经过和同学研究发现了一个特性,就是冒犯节点与其回溯路径上的最近的两个点有大小关系。

有关BST搜索树转换为AVL高度平衡树的旋转问题“> <br/> </p> <p>如上图,一个空BST树,插入16到树中,由于是空树,那么16就作为根节点。之后再输入3.3比16小,放在16的左边作为左子节点,再输入7,7比16小,走左子树一边,然后7再和3相比较,7比3大,走3的右子树。但是如上图所示,这不是一棵AVL树,因为16的左子树高度为2,右子树高度为0,左右高度差的绝对值为2,超过了AVL的条件:左右高度绝对差& lt; 2。那么就需要“旋转子树”以保证其AVL特性。</p> <p> <br/> </p> <p>看了很多书,都说什么左旋转啊右旋转啊,像上图这种情况还比较复杂,需要先左旋转后右旋转。</p> <p> <br/> </p> <p>其实,经过这些天的研究发现,以上图为例,当节7点进入树之后,打破了平衡,那么就从节7点开始回溯找到的节点,也就是节点16。然后选择冒犯节点与回溯路径上的距离节16点的最近的两个节点,也就是节点3和7。这三个点选取之后,对三个点进行大小比较,找出最小,最大和中间节点,比如16日3、7三个节点的按大小排序后的顺序是3,7日16。然后中间的节点(节点7)作为新树的根,其左节点是最小节点,右节点是最大节点,然后将新树接回原来的树上。</p><h2 class=有关BST搜索树转换为AVL高度平衡树的旋转问题