Java中怎么實現 二叉樹平衡

Java中怎么實現 二叉樹平衡，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。

　　二叉樹平衡的基本思想是通過旋轉使得平衡因子的絕對值小于1。
　　如圖所示：

輸入：失衡的結點z
輸出：平衡后子樹的根結點

private BinTreeNode rotate(BinTreeNode z){
    BinTreeNode y = higherSubT(z); //取y 為z 更高的孩子BinTreeNode x = higherSubT(y); //取x 為y 更高的孩子boolean isLeft = z.isLChild(); //記錄：z 是否左孩子BinTreeNode p = z.getParent(); //p 為z 的父親BinTreeNode a, b, c; //自左向右，三個節點BinTreeNode t0, t1, t2, t3; //自左向右，四棵子樹// 以下分四種情況重命名if (y.isLChild()) { //若y 是左孩子，則c = z; t3 = z.getRChild();if (x.isLChild()) { //若x 是左孩子(左左失衡)b = y; t2 = y.getRChild();
            a = x; t1 = x.getRChild(); t0 = x.getLChild();
        } else { //若x 是右孩子(左右失衡)a = y; t0 = y.getLChild();
            b = x; t1 = x.getLChild(); t2 = x.getRChild();
        }
    } else { //若y 是右孩子，則a = z; t0 = z.getLChild();if (x.isRChild()) { //若x 是右孩子(右右失衡)b = y; t1 = y.getLChild();
            c = x; t2 = x.getLChild(); t3 = x.getRChild();
        } else { //若x 是左孩子(右左失衡)c = y; t3 = y.getRChild();
            b = x; t1 = x.getLChild(); t2 = x.getRChild();
        }
    }//摘下三個節點z.sever();
    y.sever();
    x.sever();//摘下四棵子樹if (t0!=null) t0.sever();if (t1!=null) t1.sever();if (t2!=null) t2.sever();if (t3!=null) t3.sever();//重新鏈接a.setLChild(t0); a.setRChild(t1);
    c.setLChild(t2); c.setRChild(t3);
    b.setLChild(a); b.setRChild(c);//子樹重新接入原樹if (p!=null)if (isLeft) p.setLChild(b);else p.setRChild(b);return b;//返回新的子樹根}//返回結點v 較高的子樹private BinTreeNode higherSubT(BinTreeNode v){if (v==null) return null;int lH = (v.hasLChild()) ? v.getLChild().getHeight():-1;int rH = (v.hasRChild()) ? v.getRChild().getHeight():-1;if (lH>rH) return v.getLChild();if (lH<rH) return v.getRChild();if (v.isLChild()) return v.getLChild();else return v.getRChild();
}

輸入：待插元素ele
輸出：在AVL 樹中插入ele
代碼：

public void insert(Object ele){super.insert(ele);
    root = reBalance(startBN);
}//從v 開始重新平衡AVL 樹private BinTreeNode reBalance(BinTreeNode v){if (v==null) return root;
    BinTreeNode c = v;while (v!=null) { //從v 開始，向上逐一檢查z 的祖先if (!isBalance(v)) v = rotate(v); //若v 失衡，則旋轉使之重新平衡c = v;
        v = v.getParent(); //繼續檢查其父親}//whilereturn c;
}//判斷一個結點是否失衡private boolean isBalance(BinTreeNode v){if (v==null) return true;int lH = (v.hasLChild()) ? v.getLChild().getHeight():-1;int rH = (v.hasRChild()) ? v.getRChild().getHeight():-1;return (Math.abs(lH - rH)<=1);
}

輸入：待刪元素ele
輸出：在AVL 樹中刪除ele
代碼：

public Object remove(Object ele){
    Object obj = super.remove(ele);
    root = reBalance(startBN);return obj;
}

看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。