java实现平衡二叉树核心代码,对称二叉树java
00-1010 AVL树基本概念介绍基本设计RR(左手)LL(右手)LR(左手再右手)RL(右手再左手)添加节点删除节点
00-1010搜索二叉树具有极高的搜索效率，但在搜索二叉树时会出现以下极端情况：
这种二叉树搜索效率甚至低于链表。在搜索二叉树的基础上出现的平衡二叉树(AVL树)解决了这个问题。当平衡二叉树(AVL树)中一个节点的左右子树的高度差的绝对值大于1时，它们之间的高度差会通过旋转减小。
目录
AVL树本质上是二叉查找树。其特点是：
首先，这是一个二叉查找树。每个节点的左右子树的高度差的绝对值(平衡因子)最多为1。也就是说，AVL树本质上是一个具有平衡功能的二叉查找树(二叉树，二叉查找树)。插入或删除节点时，某个节点的左右子树高度差的绝对值大于1。这时候二叉树需要通过左右手操作再次平衡。平衡因子
节点的左子树和右子树之间的高度差。AVL树中任意节点的BF只能是-1，0，1。
00-1010以下是AVL树所需的简单方法和属性：
公共类AVLTree扩展了ComparableE { class Node { E value节点向左；节点右移；int高度；公共节点(){}公共节点(E值){ this.value=value高度=1；left=null右=空；} public void display(){ system . out . print(this . value )；} }节点根；int大小；public int size(){ return size；} public int getHeight(Node Node){ if(Node==null)返回0；返回node.height}//获取平衡因子(左右子树高度差，大小1或0为平衡，大小大于1为不平衡)public int getbalancefactor(){ return getbalancefactor(root)；} public int getBalanceFactor(Node Node){ if(Node==null)返回0；返回get height(node . left)-get height(node . right)；}//判断一棵树是否是平衡二叉树public boolean is balance(node node){ if(node==null)返回trueint balance factor=math . ABS(getbalance factor(node . left)-getbalance factor(node . right))；if(balanceFactor 1)返回falsereturn is balance(node . left)is balance(node . right)；} public boolean is balance(){ return is balance(root)；}//中序遍历树private void inprevorder(节点根){ if(root==null)return；in pre order(root . left)；root . display()；inPrevOrder(root . right)；} public void inprevorder(){ system . out . print(中序遍历：)；inPrevOrder(root)；}}
00-1010在一棵树的右子树的右子树中插入一个节点，导致二叉树变得不平衡，如下图。将5插入平衡二叉树会导致
这个树变得不再平衡，此时需要左旋操作，如下：
代码如下：
//左旋,并且返回新的根节点 public Node leftRotate(Node node){ System.out.println("leftRotate"); Node cur = node.right; node.right = cur.left; cur.left = node; //跟新node和cur的高度 node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1; cur.height = Math.max(getHeight(cur.left),getHeight(cur.right)) + 1; return cur; }
LL(右旋)
往一个AVL树左子树的左子树上插入一个节点，导致二叉树变得不在平衡，如下图，往平衡二叉树中插入2，导致这个树变得不再平衡，此时需要左旋操作，如下：
代码如下：
//右旋，并且返回新的根节点 public Node rightRotate(Node node){ System.out.println("rightRotate"); Node cur = node.left; node.left = cur.right; cur.right = node; //跟新node和cur的高度 node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1; cur.height = Math.max(getHeight(cur.left),getHeight(cur.right)) + 1; return cur; }
LR(先左旋再右旋)
往AVL树左子树的右子树上插入一个节点，导致该树不再平衡，需要先对左子树进行左旋，再对整棵树右旋，如下图所示，插入节点为5.
RL(先右旋再左旋)
往AVL树右子树的左子树上插入一个节点，导致该树不再平衡，需要先对右子树进行右旋，再对整棵树左旋，如下图所示，插入节点为2.
添加节点
//添加元素 public void add(E e){ root = add(root,e); } public Node add(Node node, E value) { if (node == null) { size++; return new Node(value); } if (value.compareTo(node.value) > 0) { node.right = add(node.right, value); } else if (value.compareTo(node.value) < 0) { node.left = add(node.left, value); } //跟新节点高度 node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1; //获取当前节点的平衡因子 int balanceFactor = getBalanceFactor(node); //该子树不平衡且新插入节点(导致不平衡的节点)在左子树的左子树上，此时需要进行右旋 if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) { return rightRotate(node); } //该子树不平衡且新插入节点(导致不平衡的节点)在右子树子树的右子树上，此时需要进行左旋 else if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) { return leftRotate(node); } //该子树不平衡且新插入节点(导致不平衡的节点)在左子树的右子树上，此时需要先对左子树左旋，在整个树右旋 else if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) { node.left = leftRotate(node.left); return rightRotate(node); } //balanceFactor < -1 && getBalanceFactor(node.left) > 0 //该子树不平衡且新插入节点(导致不平衡的节点)在右子树的左子树上，此时需要先对右子树右旋，再整个树左旋 else if(balanceFactor < -1 && getBalanceFactor(node.right) > 0) { node.right = rightRotate(node.right); return leftRotate(node); } return node; }
删除节点
//删除节点 public E remove(E value){ root = remove(root,value); if(root == null){ return null; } return root.value; } public Node remove(Node node, E value){ Node retNode = null; if(node == null) return retNode; if(value.compareTo(node.value) > 0){ node.right = remove(node.right,value); retNode = node; } else if(value.compareTo(node.value) < 0){ node.left = remove(node.left,value); retNode = node; } //value.compareTo(node.value) = 0 else{ //左右节点都为空，或者左节点为空 if(node.left == null){ size--; retNode = node.right; } //右节点为空 else if(node.right == null){ size--; retNode = node.left; } //左右节点都不为空 else{ Node successor = new Node(); //寻找右子树最小的节点 Node cur = node.right; while(cur.left != null){ cur = cur.left; } successor.value = cur.value; successor.right = remove(node.right,value); successor.left = node.left; node.left = node.right = null; retNode = successor; } if(retNode == null) return null; //维护二叉树平衡 //跟新height retNode.height = Math.max(getHeight(retNode.left),getHeight(retNode.right)); } int balanceFactor = getBalanceFactor(retNode); //该子树不平衡且新插入节点(导致不平衡的节点)在左子树的左子树上，此时需要进行右旋 if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) { return rightRotate(retNode); } //该子树不平衡且新插入节点(导致不平衡的节点)在右子树子树的右子树上，此时需要进行左旋 else if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) { return leftRotate(retNode); } //该子树不平衡且新插入节点(导致不平衡的节点)在左子树的右子树上，此时需要先对左子树左旋，在整个树右旋 else if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) { retNode.left = leftRotate(retNode.left); return rightRotate(retNode); } //该子树不平衡且新插入节点(导致不平衡的节点)在右子树的左子树上，此时需要先对右子树右旋，再整个树左旋 else if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) { retNode.right = rightRotate(retNode.right); return leftRotate(retNode); } return retNode; }到此这篇关于Java深入分析了解平衡二叉树的文章就介绍到这了,更多相关Java平衡二叉树内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。