AVL树 今天药忘吃喽~ 2022-05-27 00:19 174阅读 0赞 一、AVL树继承自BinarySearchTree, 1,它是一棵平衡二叉树,他要求每个节点的左右子树的深度之差不能超过1。 2,每个节点都有一个平衡因子bf,取值为-1、0、1 。它的值等于右子树的深度减去左子树的深度。 3,有LL、RR、RL、LR四种旋转方式 import java.util.ArrayList; public class AVLTree<E extends Comparable<E>> extends BinarySearchTree<E>{ public AVLTree(){} public AVLTree(E[] objects){ super(objects); } public static class AVLTreeNode<E extends Comparable<E>> extends BinarySearchTree.TreeNode<E>{ protected int height = 0; public AVLTreeNode(E element) { super(element); } } @Override protected AVLTreeNode<E> createNewNode(E e) { return new AVLTreeNode<>(e); } @Override public boolean insert(E e) { boolean successful = super.insert(e); if(!successful) return false; else balancePath(e); return true; } private void updateHeight(AVLTreeNode<E> node){//更新节点的高度 if(node.leftNode==null && node.rightNode == null) node.height = 0; else if (node.leftNode == null) node.height = 1 + ((AVLTreeNode<E>)node.rightNode).height; // 注意括号 else if (node.rightNode == null) node.height = 1+ ((AVLTreeNode<E>)node.leftNode).height; else node.height = 1 + Math.max(((AVLTreeNode<E>)node.rightNode).height,((AVLTreeNode<E>)node.leftNode).height); } private void balancePath(E e){//将该节点一直到根节点路径上的所有节点平衡 ArrayList<TreeNode<E>> path = path(e); for(int i=0;i<path.size();i++){ AVLTreeNode<E> A = (AVLTreeNode<E>)path.get(i); updateHeight(A); AVLTreeNode<E> parent = A==root ? null : (AVLTreeNode<E>)path.get(i-1); switch (balanceFactor(A)){ case -2: if (balanceFactor((AVLTreeNode<E>) A.leftNode) <= 0) balanceLL(A,parent); else balbanceLR(A,parent); case +2: if (balanceFactor((AVLTreeNode<E>) A.rightNode) <= 0) balanceRL(A,parent); else balanceRR(A,parent); } } } private int balanceFactor(AVLTreeNode<E> node){//获取节点的平衡因子 if (node.leftNode == null) return +node.height; else if(node.rightNode == null) return -node.height; else return ((AVLTreeNode<E>)node.rightNode).height - ((AVLTreeNode<E>)node.leftNode).height; } private void balanceLL(AVLTreeNode<E> A, AVLTreeNode<E> parent){ AVLTreeNode<E> B = (AVLTreeNode<E>)A.leftNode; if (A == root) root = B; else { if(parent.leftNode == A) parent.leftNode = B; else parent.rightNode =B; } A.leftNode = B.rightNode; B.rightNode = A; updateHeight(A); updateHeight(B); } private void balanceRR(AVLTreeNode<E> A, AVLTreeNode<E> parent){ AVLTreeNode<E> B = (AVLTreeNode<E>)A.rightNode; if (A == root) root = B; else { if(parent.leftNode == A) parent.leftNode = B; else parent.rightNode =B; } A.rightNode = B.leftNode; B.leftNode = A; updateHeight(A); updateHeight(B); } private void balanceRL(AVLTreeNode<E> A, AVLTreeNode<E> parent){ AVLTreeNode<E> B = (AVLTreeNode<E>)A.rightNode; AVLTreeNode<E> C = (AVLTreeNode<E>)B.leftNode; if (A == root) root = C; else { if(parent.leftNode == A) parent.leftNode = C; else parent.rightNode =C; } A.rightNode = C.leftNode; B.leftNode = C.rightNode; C.leftNode = A; C.rightNode = B; updateHeight(A); updateHeight(B); updateHeight(C); } private void balbanceLR(AVLTreeNode<E> A, AVLTreeNode<E> parent){ AVLTreeNode<E> B = (AVLTreeNode<E>)A.leftNode; AVLTreeNode<E> C = (AVLTreeNode<E>)B.rightNode; if (A == root) root = C; else { if(parent.leftNode == A) parent.leftNode = C; else parent.rightNode =C; } A.leftNode = C.rightNode; B.rightNode = C.leftNode; C.leftNode = B; C.rightNode = A; updateHeight(A); updateHeight(B); updateHeight(C); } public boolean delete(E e){ if (root == null) // nothing in the tree return false; TreeNode<E> parent = null; TreeNode<E> current = root; while(current!=null){ if (e.compareTo(current.element)>0){ parent = current; current = current.rightNode; } else if (e.compareTo(current.element)<0){ parent = current; current = current.leftNode; } else break; } if (current == null) return false; //元素不在二叉树中 if (current.leftNode == null){ //没有左节点 if (parent == null) root = current.rightNode; else { if (e.compareTo(parent.element)>0) parent.rightNode = current.rightNode; else parent.leftNode = current.rightNode; balancePath(parent.element); } } else{ //有左节点 TreeNode<E> parentOfRightMost = current; TreeNode<E> rightMost = current.leftNode; while (rightMost.rightNode != null){ parentOfRightMost = rightMost; rightMost = rightMost.rightNode; } current.element = rightMost.element; if(parentOfRightMost.rightNode == rightMost) parentOfRightMost.rightNode = rightMost.leftNode; else parentOfRightMost.leftNode = rightMost.leftNode; balancePath(parentOfRightMost.element); } size--; return true; } }
相关 AVL树 以后在有面试官问你AVL树,你就把这篇文章扔给他。 作者:帅地 来源 |网络整理,版权归原作者所有,侵删。 背景 西天取经的路上,一样上演着编程... 川长思鸟来/ 2024年04月18日 22:41/ 0 赞/ 73 阅读
相关 AVL树 AVL树> 在之前我实现了二叉搜索树,但是二叉搜索树存在问题,就是当输入单调增或者单调减的结点数据后,二叉树就退化成类似链表的结构了,为了解决二叉搜索树的这种弊端就引入 朱雀/ 2022年07月14日 23:38/ 0 赞/ 165 阅读
相关 AVL树 1. 概述 AVL树是最早提出的自平衡二叉树,在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。AVL树得名于它的发明者G.M. Adelson-V ゝ一纸荒年。/ 2022年06月18日 12:27/ 0 赞/ 166 阅读
相关 AVL树 AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和 た 入场券/ 2022年06月15日 09:08/ 0 赞/ 184 阅读
相关 AVL树详解 下面讲解AVL树的C语言代码实现: 1.首先是定义: define LH 1 define EH 0 define LH -1 define 红太狼/ 2022年06月13日 11:21/ 0 赞/ 204 阅读
相关 AVL树详解 AVL树是最先发明的自平衡二叉查树,二叉查找树的性质如果不知道可以百度一下。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。其实性质还是比较简单的, 桃扇骨/ 2022年06月01日 00:51/ 0 赞/ 188 阅读
相关 AVL树 一、AVL树继承自BinarySearchTree, 1,它是一棵平衡二叉树,他要求每个节点的左右子树的深度之差不能超过1。 2,每个节点都有一个平衡因子bf,取值为 今天药忘吃喽~/ 2022年05月27日 00:19/ 0 赞/ 175 阅读
相关 AVL树 [2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 平衡二叉树,是一个方便查找的树,树的左子树深度与右子树的 谁借莪1个温暖的怀抱¢/ 2022年01月15日 01:39/ 0 赞/ 205 阅读
还没有评论,来说两句吧...