北京网站托管的公司,网站建设技术课程设计,如何删除wordpress底部,深圳住房和建设局网站办事大厅在二叉平衡树中#xff0c;我们进行插入和删除操作时都需要遍历树#xff0c;可见树的结构是很影响操作效率的。在最坏的情况下#xff0c;树成了一个单支树#xff0c;查找的时间复杂度成了O(N)#xff0c;建树跟没建树一样。那么是不是有什么办法可以建一个树避免这种情…在二叉平衡树中我们进行插入和删除操作时都需要遍历树可见树的结构是很影响操作效率的。在最坏的情况下树成了一个单支树查找的时间复杂度成了O(N)建树跟没建树一样。那么是不是有什么办法可以建一个树避免这种情况
一.概念
AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis其又叫高度平衡树。进行插入和删除操作后对树进行一次或多次旋转保证每个结点的左右子树高度之差的绝对值不超过1以达到高度平衡的目的。
1.AVL树本质上还是二叉平衡树这是必须保证的一点
2.AVL树在二叉平衡树的基础上加入了一个平衡的条件即每个结点的左右子树高度之差的绝对值不超过1。
二叉平衡树Java Map和Set-CSDN博客
二.定义节点
节点与二叉平衡树的节点差不多多了一个平衡因子一个父节点。
static class TreeNode {public int val;public int bf;//平衡因子public TreeNode left;public TreeNode right;public TreeNode parent;public TreeNode(int val) {this.val val;}
}
三.插入操作
因为AVL树也是二叉平衡树所以插入操作是一样的只需在后面加一个调整平衡因子的操作。
//找到要插入的位置
TreeNode node new TreeNode(val);
if(root null) {root node;return true;
}TreeNode parent null;
TreeNode cur root;
while (cur ! null) {if(cur.val val) {parent cur;cur cur.right;}else if(cur.val val) {return false;}else {parent cur;cur cur.left;}
}//插入节点
node.parent parent;
cur node;
if(parent.val val) {parent.right node;
}else {parent.left node;
}
上述代码就是插入节点的操作。插入完后我们要对平衡因子进行调整。
1.调整平衡因子
平衡因子可分为三种情况、、。
1.1 等于说明该节点的左右子树高度相同高度相同也就意味着该节点平衡了也就是说新插入的节点没有使树的高度发生变化那么整个树都是平衡的。
1.2 等于说明该节点的左右子树高度相差1如果左子树高那么就是-1如果右子树高那么就是1。如果是这种情况还要继续往上找因为这说明我们插入的节点影响了树的高度这是要看一下是不是不平衡了。
1.3 等于说明该节点左右子树高度相差2不平衡了要进行调整。这里又要分情况讨论了。
当平衡因子等于 2 时说明右子树高。这里又要分为两种情况 为什么要分为这两种呢这与加下来的旋转操作有关。
前面说了AVL树就是靠旋转来进行调整以达到平衡。如左图右子树高我们可以通过左旋来降低右子树的高度。这里大家可以去下面看一下左旋的具体操作。
但对于右图来说左旋就不好用了转了之后还是不平衡的。对于右图我们要用先右旋在左旋的操作。
为什么会这样左旋转的本质就是将bf为的左子树接到parent节点的右子树如果说其这个左子树本身就是更深的子树那么接上就和原来没有什么区别。
当平衡因子等于 -2 时也是一样都是一个原理这里不过多赘述直接上代码。
public boolean insert(int val) {//找到要插入的位置TreeNode node new TreeNode(val);if(root null) {root node;return true;}TreeNode parent null;TreeNode cur root;while (cur ! null) {if(cur.val val) {parent cur;cur cur.right;}else if(cur.val val) {return false;}else {parent cur;cur cur.left;}}//插入节点node.parent parent;cur node;if(parent.val val) {parent.right node;}else {parent.left node;}//调整平衡因子while (parent ! null) {//更新平衡因子if(cur parent.right) {parent.bf;}else {parent.bf--;}if(parent.bf 1 || parent.bf -1){//继续循环cur parent;parent cur.parent;}else if(parent.bf 2){if(cur.bf 1) {rotateLeft(parent);}else {rotateRL(parent);}break;}else if(parent.bf -2){if(cur.bf -1) {rotateRight(parent);}else {rotateLR(parent);}break;}else{//已经平衡了break;}}return true;
}
2.左旋
将子树向左旋转 上图左图是没有旋转时的状态右图时左旋后的状态我们可以通过节点变化来得到整个过程的变化12的左子树连接到了10上10变成了12的左子树。
可以拆成这么几步
1.将bf1的节点的左子树接到parent的右子树上
2.将bf1的节点连接到parent的parent
3.将parent连接到bf1的左子树上。
private void rotateLeft(TreeNode parent) {TreeNode subR parent.right;TreeNode subRL subR.left;//将bf1的节点的左子树接到parent的右子树上parent.right subRL;if(subRL ! null) {subRL.parent parent;}//将bf1的节点连接到parent的parentTreeNode pParent parent.parent;if(root parent) {root subR;root.parent null;}else {if(pParent.left parent) {pParent.left subR;}else {pParent.right subR;}subR.parent pParent;}//将parent连接到bf1的左子树上subR.left parent;parent.parent subR;//调整平衡因子subR.bf parent.bf 0;}
3.右旋
将子树向右旋 思路跟向左旋一样这里是将8的右子树连在10的左子树上将10连在8的右子树上。
具体步骤
1.将bf-1的节点的右子树连在parent的左子树上
2.将bf-1的节点与parent的parent连接
3.将parent连接到bf-1节点的右子树上。
private void rotateRight(TreeNode parent) {TreeNode subL parent.left;TreeNode subLR subL.right;//将bf-1的节点的右子树连在parent的左子树上parent.left subLR;if(subLR ! null) {subLR.parent parent;}//将bf-1的节点与parent的parent连接TreeNode pParent parent.parent;if(parent root) {root subL;root.parent null;}else {if(pParent.left parent) {pParent.left subL;}else {pParent.right subL;}subL.parent pParent;}//将parent连接到bf-1的节点上subL.right parent;parent.parent subL;//调整平衡因子subL.bf 0;parent.bf 0;
}
4.先右旋后左旋
先旋转以bf-1为父节点的树再旋转parent的树 表现在这张图里的是先旋转13节点的树旋转完后再旋转10节点的树。
这里要特别说明以下平衡因子的调整 上面两张图相当清晰表示出了平衡因子的变化。
private void rotateRL(TreeNode parent) {TreeNode subR parent.right;TreeNode subRL subR.left;int bf subRL.bf;rotateRight(parent.right);rotateLeft(parent);if(bf 1) {parent.bf -1;subR.bf 0;subRL.bf 0;}if(bf -1){parent.bf 0;subR.bf 1;subRL.bf 0;}
}
5.先左旋后右旋
这个跟先右旋再左旋相似都很像。 代码
private void rotateLR(TreeNode parent) {TreeNode subL parent.left;TreeNode subLR subL.right;int bf subLR.bf;rotateLeft(parent.left);rotateRight(parent);if(bf -1) {subL.bf 0;subLR.bf 0;parent.bf 1;}if(bf 1){subL.bf -1;subLR.bf 0;parent.bf 0;}
}
四.判断是不是AVL树
判断什么是不是什么这种问题一般是从性质出发。
判断是不是AVL树首先这棵树是一颗二叉平衡树其次这棵树的高度也要平衡。
public boolean isBalanced(TreeNode root) {if(root null){return true;}int leftH height(root.left);int rightH height(root.right);if(rightH-leftH ! root.bf) {return false;}return Math.abs(leftH-rightH) 1 isBalanced(root.left) isBalanced(root.right);
}
五.总结
AVL树改善了原来二叉平衡树查找的问题但也有新的问题。我们要在AVL树上插入或删除时要不断的转转转这个转转转也要时间的。所以说如果我们要存储一个要频发插入删除的树不适合用这个。
