package com.tomsnail.data.tree;/** * AVL二叉平衡樹 * @author tomsnail * @date 2015年3月30日 下午4:35:50 */public class AVLTree { /** * 根節(jié)點(diǎn) * @author tomsnail * @date 2015年3月30日 下午4:36:54 */ PRivate AVLNode rootNode; private String bulidType = ""; /** * 增加一個(gè)節(jié)點(diǎn) * @author tomsnail * @date 2015年3月30日 下午4:36:08 */ public void add(int value){ AVLNode subNode = null; if(rootNode==null){ subNode = new AVLNode(value); rootNode = subNode; }else{ subNode = addNode(rootNode,value); } reBuild(subNode); } private AVLNode addNode(AVLNode node,int value){ AVLNode subNode = null; if(node.getValue()>value){ if(node.getLeftNode()==null){ subNode = new AVLNode(value); node.setLeftNode(subNode); }else{ subNode = addNode(node.getLeftNode(), value); } } if(node.getValue()<value){ if(node.getRightNode()==null){ subNode = new AVLNode(value); node.setRightNode(subNode); }else{ subNode = addNode(node.getRightNode(),value); } } return subNode; } /** * 重平衡樹 * @author tomsnail * @date 2015年3月30日 下午5:42:00 */ private void reBuild(AVLNode node){ if(node!=null){ AVLNode tempRootNode = findTempRootNode(node); if(tempRootNode!=null){ if(bulidType.equals("ll")){ Lrotate(node,tempRootNode); }else if(bulidType.equals("rr")){ Rrotate(node,tempRootNode); }else if(bulidType.equals("lr")){ Rrotate(node,tempRootNode.getLeftNode()); Lrotate(node,tempRootNode); }else if(bulidType.equals("rl")){ Lrotate(node,tempRootNode.getRightNode()); Rrotate(node,tempRootNode); } reBuild(tempRootNode); } } } /** * 右旋 * @author tomsnail * @date 2015年3月30日 下午9:23:28 */ private void Rrotate(AVLNode node,AVLNode tempRootNode){ AVLNode rotateNode = tempRootNode.getRightNode();//旋轉(zhuǎn)節(jié)點(diǎn) AVLNode rootNode = tempRootNode.getRootNode();//主根節(jié)點(diǎn) String type = ""; if(rootNode!=null){ if(rootNode.getLeftNode()==tempRootNode){ type="l"; }else{ type="r"; } } AVLNode adjustNode = rotateNode.getLeftNode();//調(diào)整節(jié)點(diǎn) rotateNode.setLeftNode(tempRootNode); tempRootNode.setRightNode(null); if(adjustNode!=null){ tempRootNode.setRightNode(adjustNode); } if(rootNode==null){ rotateNode.setRootNode(null); this.rootNode = rotateNode; } if(type.equals("r")){ rootNode.setRightNode(rotateNode); }else if(type.equals("l")){ rootNode.setLeftNode(rotateNode); } } /** * 左旋 * @author tomsnail * @date 2015年3月30日 下午9:23:28 */ private void Lrotate(AVLNode node,AVLNode tempRootNode){ AVLNode rotateNode = tempRootNode.getLeftNode();//旋轉(zhuǎn)節(jié)點(diǎn) AVLNode rootNode = tempRootNode.getRootNode();//主根節(jié)點(diǎn) String type = ""; if(rootNode!=null){//子樹類型 if(rootNode.getLeftNode()==tempRootNode){ type="l"; }else{ type="r"; } } AVLNode adjustNode = rotateNode.getRightNode();//調(diào)整節(jié)點(diǎn) rotateNode.setRightNode(tempRootNode); tempRootNode.setLeftNode(null); if(adjustNode!=null){ tempRootNode.setLeftNode(adjustNode); } if(rootNode==null){ rotateNode.setRootNode(null); this.rootNode = rotateNode; } if(type.equals("r")){ rootNode.setRightNode(rotateNode); }else if(type.equals("l")){ rootNode.setLeftNode(rotateNode); } } /** * 查找最小不平衡的根節(jié)點(diǎn) * @author tomsnail * @date 2015年3月30日 下午5:40:55 */ private AVLNode findTempRootNode(AVLNode node){ AVLNode noB = getNoBalance(node); if(noB==null){ return null; } if(isTypeLL(noB)){ bulidType = "ll"; }else if(isTypeRR(noB)){ bulidType = "rr"; }else if(isTypeLR(noB)){ bulidType = "lr"; }else if(isTypeRL(noB)){ bulidType = "rl"; } return noB; } //左左類型 private boolean isTypeLL(AVLNode noB){ try { if(noB.getRightNode()==null&&noB.getLeftNode().getRightNode()==null&&!noB.getLeftNode().getLeftNode().hasSubNode()){ return true; } if(noB.getRightNode()!=null&&noB.getLeftNode().getRightNode()!=null&&noB.getLeftNode().getLeftNode().hasSubNode()){ return true; } } catch (Exception e) { } return false; } //右右類型 private boolean isTypeRR(AVLNode noB){ try { if(noB.getLeftNode()==null&&noB.getRightNode().getLeftNode()==null&&!noB.getRightNode().getRightNode().hasSubNode()){ return true; } if(noB.getLeftNode()!=null&&noB.getRightNode().getLeftNode()!=null&&noB.getRightNode().getRightNode().hasSubNode()){ return true; } } catch (Exception e) { } return false; } //左右類型 private boolean isTypeLR(AVLNode noB){ try { if(noB.getRightNode()==null&&noB.getLeftNode().getLeftNode()==null&&!noB.getLeftNode().getRightNode().hasSubNode()){ return true; } if(noB.getRightNode()!=null&&noB.getLeftNode().getLeftNode()!=null&&noB.getLeftNode().getRightNode().hasSubNode()){ return true; } } catch (Exception e) { } return false; } //右左類型 private boolean isTypeRL(AVLNode noB){ try { if(noB.getLeftNode()==null&&noB.getRightNode().getRightNode()==null&&!noB.getRightNode().getLeftNode().hasSubNode()){ return true; } if(noB.getLeftNode()!=null&&noB.getRightNode().getRightNode()!=null&&noB.getRightNode().getLeftNode().hasSubNode()){ return true; } } catch (Exception e) { } return false; } //獲取不平衡的根節(jié)點(diǎn) private AVLNode getNoBalance(AVLNode node){ if(node.getRootNode()==null){ return null; }else{ if(!isBalance(node.getRootNode())){ return node.getRootNode(); }else{ return getNoBalance(node.getRootNode()); } } } /** * 刪除一個(gè)節(jié)點(diǎn) * @author tomsnail * @date 2015年3月30日 下午4:36:20 */ public void delete(int value){ AVLNode wantDeleteNode = find(value); if(wantDeleteNode==null){ return; }else{ if(wantDeleteNode.getLeftNode()==null&&wantDeleteNode.getRightNode()==null){//刪除節(jié)點(diǎn)沒有左右子樹 AVLNode rootNode = wantDeleteNode.getRootNode(); if(rootNode!=null){ if(rootNode.getLeftNode()==wantDeleteNode){ rootNode.setLeftNode(null); }else{ rootNode.setRightNode(null); } reBuild(rootNode); } }else if(wantDeleteNode.getRightNode()==null){//刪除節(jié)點(diǎn)只有左子樹 AVLNode rootNode = wantDeleteNode.getRootNode(); if(rootNode!=null){ if(rootNode.getLeftNode()==wantDeleteNode){ rootNode.setLeftNode(wantDeleteNode.getLeftNode()); }else{ rootNode.setRightNode(wantDeleteNode.getLeftNode()); } wantDeleteNode.setLeftNode(null); reBuild(rootNode); } }else if(wantDeleteNode.getLeftNode()==null){//刪除節(jié)點(diǎn)只有右子樹 AVLNode rootNode = wantDeleteNode.getRootNode(); if(rootNode!=null){ if(rootNode.getRightNode()==wantDeleteNode){ rootNode.setLeftNode(wantDeleteNode.getRightNode()); }else{ rootNode.setRightNode(wantDeleteNode.getRightNode()); } wantDeleteNode.setRightNode(null); reBuild(rootNode); } }else {//刪除節(jié)點(diǎn)有左右子樹 AVLNode maxNode = getLeftMaxValueNode(wantDeleteNode.getLeftNode());//找到節(jié)點(diǎn)左子樹最大值的節(jié)點(diǎn) AVLNode rootMaxNode = maxNode.getRootNode();//獲得該節(jié)點(diǎn)的父節(jié)點(diǎn) if(maxNode.getLeftNode()!=null){//如果最大值節(jié)點(diǎn)有左子樹，則將最大值節(jié)點(diǎn)的父節(jié)點(diǎn)的右子樹設(shè)為它 rootMaxNode.setRightNode(maxNode.getLeftNode()); maxNode.setLeftNode(null); }else{//否則置空 rootMaxNode.setRightNode(null); } wantDeleteNode.setValue(maxNode.getValue());//把要?jiǎng)h除節(jié)點(diǎn)的值用最大值節(jié)點(diǎn)的值替換 maxNode=null;//引用置空 reBuild(rootMaxNode); } } } //得到左子樹最大值節(jié)點(diǎn) private AVLNode getLeftMaxValueNode(AVLNode node){ if(node!=null&&node.getRightNode()!=null){ return getLeftMaxValueNode(node.getRightNode()); }else{ return node; } } /** * 查找一個(gè)節(jié)點(diǎn) * @author tomsnail * @date 2015年3月30日 下午4:36:35 */ public AVLNode find(int value){ return findWith2(rootNode,value); } private AVLNode findWith2(AVLNode node,int value){ if(node==null){ return null; } System.out.println(node.getValue()); if(node.getValue()>value){ return findWith2(node.getLeftNode(),value); }else if(node.getValue()<value){ return findWith2(node.getRightNode(),value); }else{ return node; } } /** * 中序遍歷 * @author tomsnail * @date 2015年3月31日 下午6:23:05 */ public void midScan(AVLNode node){ if(node==null){ return; } midScan(node.getLeftNode()); System.out.println(node.getValue()); midScan(node.getRightNode()); } public AVLNode getRootNode() { return rootNode; } public static void main(String[] args) { int[] is = new int[]{10,11,23,3,5,44,32,4,6,18,19,7,8,70,50,60,40,55,65,53,80};//10,11,23,3,5,44,32,4,6,18,19,7,8,70,50,60,40,55,65,53,80 AVLTree tree = new AVLTree(); for(int i=0;i<is.length;i++){ tree.add(is[i]); } System.out.println(tree.getRootNode().getValue()); System.out.println("----------------------------"); tree.midScan(tree.getRootNode()); tree.delete(4); System.out.println(isBalance(tree.getRootNode())); System.out.println(); //tree.find(40); } public static int depth(AVLNode node){ if(node==null){ return 0; }else{ int ld = depth(node.getLeftNode()); int rd = depth(node.getRightNode()); return 1 + (ld >rd ? ld : rd); } } public static boolean isBalance(AVLNode node){ if (node==null) return true; int dis = depth(node.getLeftNode()) - depth(node.getRightNode()); if (dis>1 || dis<-1 ) return false; else return isBalance(node.getLeftNode()) && isBalance(node.getRightNode()); }}class AVLNode{ private int value; private AVLNode leftNode; private AVLNode rightNode; private AVLNode rootNode; public int getValue() { return value; } public void setValue(int value) { this.value = value; } public AVLNode getLeftNode() { return leftNode; } public void setLeftNode(AVLNode leftNode) { this.leftNode = leftNode; if(leftNode!=null){ leftNode.setRootNode(this); } } public AVLNode getRightNode() { return rightNode; } public void setRightNode(AVLNode rightNode) { this.rightNode = rightNode; if(rightNode!=null){ rightNode.setRootNode(this); } } public AVLNode getRootNode() { return rootNode; } public void setRootNode(AVLNode rootNode) { this.rootNode = rootNode; } public boolean hasSubNode(){ if(this.leftNode!=null||this.rightNode!=null){ return true; }else{ return false; } } public AVLNode(){ } public AVLNode(int value){ this.value = value; }}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
