在按照二叉查找树(二叉查找树(BST:Binary Search Tree) )的方式插入元素构建一个平衡二叉树(平衡二叉树 )时,可能会出现不平衡的现象。可以根据新插入节点与最低不平衡节点之间的位置关系进行相应的调整。
我们先把需要调整的类型分为四种情况:LL型、RR型、LR型、RL型。使用图形示例与实际代码结合的方式对不平衡二叉树进行旋转。
定义一个树节点:
LL型调整
由于在y_6的左孩子(L)的左子树(L)上插入新结点2,使原来平衡二叉树变得不平衡,此时y_6的平衡因子由1增至2。显然,按照大小关系,结点x_3应作为新的根结点,1和y_6两个节点分别作为左右孩子节点才能平衡,y_6结点就好像是绕结点x_3顺时针旋转一样。
总结一下LL型调整的一般步骤:
RR型调整
由于在y_2的右孩子(R)的右子树(L)上插入新结点5,使原来平衡二叉树变得不平衡,此时y_2的平衡因子由1增至2。显然,按照大小关系,结点x_4应作为新的根结点,y_2和6两个节点分别作为左右孩子节点才能平衡,y_2结点就好像是绕结点x_4逆时针旋转一样。
总结一下RR型调整的一般步骤:
LR型调整
由于在6的左孩子(L)的右子树(R)上插入新结点3,使原来平衡二叉树变得不平衡,此时6的平衡因子由1增至2。显然,按照大小关系,结点x_4应作为新的根结点,y_2和6两个节点分别作为左右孩子节点才能平衡。
总结一下LR型调整的一般步骤:
RL型调整
由于在2的右孩子(R)的左子树(L)上插入新结点4,使原来平衡二叉树变得不平衡,此时2的平衡因子由1增至2。显然,按照大小关系,结点3应作为新的根结点,2和5两个节点分别作为左右孩子节点才能平衡。
总结一下RL型调整的一般步骤:
理解好平衡二叉树的旋转,对后边学习红黑树有非常大的帮助。下一篇文章学习,如何在构建和删除平衡二叉树的过程中维持二叉树一直平衡。
平衡二叉树
如何优雅地画好二叉树
二叉树遍历的思维导图
二叉树的层序遍历及应用
二叉查找树(BST:Binary Search Tree)
本文由梁桂钊于2023-09-05发表在梁桂钊的博客,如有疑问,请联系我们。
本文链接:https://720ui.com/11800.html