数据结构与算法

骤：

1. 创建一个新的节点newNode，值等于当前根节点的值。
2. 把新节点的左子树设置成当前节点的左子树。
3. 把新节点的右子树设置成当前节点的右子树的左子树。
4. 把当前节点的值换为当前右子节点的值。
5. 把当前节点的右子树设置成右子树的右子树。
6. 把当前节点的左子树设置为新的节点。

平衡二叉树之右旋转

步骤：

1. 创建一个新的节点，值等于当前根的节点的值。
2. 把新节点的右子树设置成当前节点的右子树。
3. 把新节点的左子树设置成当前节点的左子树的右子树。
4. 把当前节点的值换位左子节点的值。
5. 把当前节点的左子树设置成左子树的左子树。
6. 把当前节点的右子树设置为新的节点。

平衡二叉树之双旋转

在某些情况下，单旋转不能完成完成平衡二叉树的转换，需要进行两次旋转。

1. 如果它的右子树的左子树的高度大于它的右子树的右子树的高度，需要先对右子树进行右旋转，再对当前节点进行左旋转。
2. 如果它的左子树的右子树高度大于它的左子树的左子树高度，
3. 需要对左子树先进行左旋转,再对当前节点进行右旋转。分析：
   1. 左子树全部为空，从形式上看，更像一个单链表;
   2. 插入速度没有影响;
   3. 查询速度明显降低(因为需要一次比较)，不能发挥BST的优势。因为每次还要比较左子树，其查询速度，比单链表还慢。
   4. 解决方案-平衡二叉树(ALV)

   基本介绍

   1. 平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree)，又称为AVL树，可以保证查询效率较高。
   2. 具有以下特点：它是一颗空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。平衡二叉树的常用实现方法有 红黑树、AVL、替罪羊树、Treap、伸展树等;
   3. 举例说明，下图前两个都是平衡二叉树，第一个左右子树的高度差绝对值是1，第二个左右子树高度差的绝对值是0，而第三个的左右子树高度差的绝对值是2，这样第三个就不是平衡二叉树;
   4. 

（编辑：南通站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!