查找二叉平衡樹與查找二叉樹有什么區別呢？當要進行大規模刪除操作時（先不考慮懶惰刪除），會出現某種情況，高度會逐漸的變大，是因為我們總是把右邊最小的葉子節點變為刪除的點，再去刪除右邊最大的點，這就導致了高度變大，查找數據時間變長，顯然這是要優化的。
我們需要在Node(內部節點類)中加入一個高度height的一個變量思想：當插入的時候左節點和右節點的高度度相差深度超過1的時候，必須要旋轉相應的節點來保持高度的平衡。分為4種情況 對于平衡二叉樹有4中情況 * 1.對&的左兒子的左子樹進行一次插入 * 2.對&的左兒子的右子樹進行一次插入 * 3.對&的右兒子的左子樹進行一次插入 * 4.對&的右兒子的右子樹進行一次插入package tree;/* 平衡查找二叉樹 * 對于平衡二叉樹有4中情況 * 1.對&的左兒子的左子樹進行一次插入 * 2.對&的左兒子的右子樹進行一次插入 * 3.對&的右兒子的左子樹進行一次插入 * 4.對&的右兒子的右子樹進行一次插入 */public class AVLTree<AnyType extends Comparable<? super AnyType>>{ /* * 節點內部類 */ PRivate static class AvlNode<AnyType>{ AnyType element; //數據（data） AvlNode<AnyType> left; //左節點（Left child） AvlNode<AnyType> right; //右節點（right child） int height; //高度(height) public AvlNode(AnyType x){ this(x, null, null); } public AvlNode(AnyType theElement, AvlNode<AnyType> lt, AvlNode<AnyType> rt){ element = theElement; left = lt; right = rt; } } private AvlNode<AnyType> root; //根節點 //初始化操作 public AVLTree(){ root = null; } //判斷是否為空樹 public boolean isEmpty(){ return root == null; } //直接清空樹 public void makeEmpty(){ root = null; } /* * 添加節點 */ public void insert(AnyType x){ root = insert(x, root); } /* * 前面的插入和ADT樹沒多大的區別，最大的區別就在于當插入數據的時候要先檢查插入的數據相對的高度差 * 如果差值大于1，那么就要對應的進行旋轉 */ private AvlNode<AnyType> insert(AnyType x, AvlNode<AnyType> t){ if(t == null) return new AvlNode(x ,null, null); int compareResult = x.compareTo(t.element); //比較當前節點的大小 if(compareResult > 0) t.right = insert(x, t.right); else if(compareResult < 0) t.left = insert(x, t.left); else ; return balanced(t); } private static final int ALLOWED_IMBALANCE = 1; private AvlNode<AnyType> balanced(AvlNode<AnyType> t){ if(t == null) return t; if(height(t.left) - height(t.right) > ALLOWED_IMBALANCE) if(height(t.left.left) >= height(t.left.right)) t = rotateWithLeftChild(t); else t = doubleWithLeftChild(t); else if(height(t.right) - height(t.left) > ALLOWED_IMBALANCE) if(height(t.right.right) > height(t.right.left)) t = rotateWithRightChild(t); else t = doubleWithRightChild(t); t.height = Math.max(height(t.left), height(t.right)) + 1; return t; } /* * 每個節點的高度情況 只有三種情況 0 1 -1 */ private int height(AvlNode<AnyType> t){ return t == null ? -1 : t.height; } /* * 第一種情況：對&的左兒子的左子樹進行一次插入（單旋轉） k2 k1 k1 z ---> x k2 x y y z */ private AvlNode<AnyType> rotateWithLeftChild(AvlNode<AnyType> k2){ AvlNode<AnyType> k1 = k2.left; k2.left = k1.right; //k2的左子樹等于k1的右子樹 k1.right = k2; k2.height = Math.max(height(k2.left), height(k2.right)) + 1; k1.height = Math.max(height(k1.left), k2.height) + 1; return k1; } /* * 第二種情況：對&的左兒子的右子樹進行一次插入(雙旋轉) * k3 k2 * k1 d ---> k1 k3 * a k2 a b c d * b c */ private AvlNode<AnyType> doubleWithLeftChild(AvlNode<AnyType> k3){ k3.left = rotateWithLeftChild(k3.left); return rotateWithLeftChild(k3); } /* * 第三種情況：對&的右兒子的左子樹進行一次插入（單旋轉） k2 k1 z k1 ---> k2 y x y z x */ private AvlNode<AnyType> rotateWithRightChild(AvlNode<AnyType> k2){ AvlNode<AnyType> k1 = k2.right; k2.right = k1.left; //k2的左子樹等于k1的右子樹 k1.left = k2; k2.height = Math.max(height(k2.left), height(k2.right)) + 1; k1.height = Math.max(height(k1.right), k2.height) + 1; return k1; } /* * 第四種情況：對&的右兒子的右子樹進行一次插入（雙旋轉） */ private AvlNode<AnyType> doubleWithRightChild(AvlNode<AnyType> k3){ k3.right = rotateWithRightChild(k3.right); return rotateWithRightChild(k3); } /* * 同樣，刪除操作是最麻煩的操作，當刪除一個節點的時候，也有可能會造成樹的不平衡， * 所以也要調用balanced方法 */ public void remove(AnyType x){ remove(x, root); } private AvlNode<AnyType> remove(AnyType x, AvlNode<AnyType> t){ if(t == null) return t; int compareResult = x.compareTo(t.element); if(compareResult < 0) t.left = remove(x, t.left); else if(compareResult > 0) t.right = remove(x, t.right); else if (t.left != null && t.right != null){ t.element = findMin(t.right).element; t.right = remove(t.element, t.right); }else t = (t.left != null) ? t.left : t.right; return balanced(t); } /* * 取樹中的最小值(一直找左子樹就ok) */ public AnyType findMin(){ if(isEmpty()) throw new NullPointerException(); return findMin(root).element; } private AvlNode<AnyType> findMin(AvlNode<AnyType> t){ if(t == null) return null; else if(t.left == null) return t; return findMin(t.left); } /* * 去樹中的最大值（一直找右子樹） */ public AnyType findMax(){ if(isEmpty()) throw new NullPointerException(); return findMax(root).element; } private AvlNode<AnyType> findMax(AvlNode<AnyType> t){ if(t == null) return null; else if(t.right == null) return t; return findMax(t.right); } public void printTree(){ if(isEmpty()) System.out.println("空樹"); else printTree(root); } private void printTree(AvlNode<AnyType> t){ if(t != null){ System.out.println("值：" + t.element+" " + ",高度：" + t.height); printTree(t.left); printTree(t.right); } } public static void main(String[] args){ AVLTree<Integer> bst = new AVLTree<>(); bst.insert(1); bst.insert(2); bst.insert(3); bst.insert(4); bst.insert(5); bst.insert(6); bst.printTree(); System.out.println("最小值：" + bst.findMin()); }}新聞熱點
疑難解答
