平衡二叉树四种旋转 什么是平衡二叉树？

什么是平衡二叉树？

为空树或左右子树高差绝对值不大于1，左右子树均为平衡二叉树。常用的算法有红黑树、AVL、swap、伸缩树等。在平衡二叉搜索树中，我们可以看到它的高度一般保持在O（log2n），这大大降低了操作的时间复杂度。

在平衡二叉树中,插入一个节点后引起不平衡,设离插入节点最近的不平衡点是A，并且已知A的左右孩子的平衡节点？

由于节点a右子树的平衡因子为0，只能是插入左子树的节点，即节点a左子树加高。如果平衡因子的定义是左子树的高度右子树的高度，则节点a的平衡因子必须为零如果平衡因子的定义是右子树的高度左子树的高度，则a的平衡因子必须为-2，并且需要向右旋转，即，RR旋转

两者的重点不同

！平衡二叉树就是追求绝对平衡。我们无法知道每次插入节点后的旋转次数。这样，实现条件更加严格，复杂度非常高。恰恰相反，红黑树只追求一般的平衡。在与平衡二叉树的时间复杂度相同的情况下，插入3到4次就可以达到平衡，相对简单。

平衡二叉树四种旋转 构造平衡二叉树例题 二叉排序树的平衡旋转

版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。