平衡二叉樹AVLTree

public class AvlTreeNode {

    int value;
    int bf;
    AvlTreeNode leftChild;
    AvlTreeNode rightChild;

    public AvlTreeNode(int value) {
        this.value =https://www.cnblogs.com/newcooler/p/ value;
        bf = 0;
    }

    /**
     * 添加子節點
     * @param subNode
     */
    public void addNode(AvlTreeNode subNode) {

        if(subNode.value <= this.value) {
            // 在左子樹上添加新節點
            if(leftChild == null) {
                leftChild = subNode;
            } else {
                leftChild.addNode(subNode);
            }
        } else {
            // 在右子樹上添加新節點
            if(rightChild == null) {
                rightChild = subNode;
            } else {
                rightChild.addNode(subNode);
            }
        }

        // 平衡因子 > 1 則觸發旋轉
        if(Math.abs(calBf()) > 1) {
            rotate();
        }
    }

    /**
     * 計算節點平衡因子(右子樹高 - 左子樹高)
     * @return
     */
    public int calBf() {
        int leftDeep = 0;
        int rightDeep = 0;
        if(null != leftChild) {
            leftDeep = leftChild.getSubDeep();
        }

        if(null != rightChild) {
            rightDeep = rightChild.getSubDeep();
        }
        this.bf = rightDeep - leftDeep;
        return this.bf;
    }

    public void rotate() {
        if (-2 == this.bf) {
            if(-1 == leftChild.calBf()) {
                // 直接右旋
                rightRotate();
            } else {

                // 先左旋
                leftChild.leftRotate();

                // 再右旋
                rightRotate();
            }
        } else if (2 == this.bf) {
            if(1 == rightChild.calBf()) {
                // 直接右旋
                leftRotate();
            } else {
                // 先左旋
                rightChild.rightRotate();

                // 再右旋
                leftRotate();
            }
        }

    }

    /**
     * 右旋
     */
    public void rightRotate() {
        // 克隆當前節點(頂節點)后面右旋, 當前節點降級為中間節點
        AvlTreeNode tmpNode = new AvlTreeNode(this.value);

        // 廢棄中間節點, 當前節點替換原中間節點
        value =https://www.cnblogs.com/newcooler/p/ leftChild.value;

        // 將原中間節點的原右子樹嫁接到右旋節點的左子樹上
        tmpNode.leftChild = leftChild.rightChild;

        // 右旋節點的左子樹保持不變
        tmpNode.rightChild = rightChild;

        // 將原中間節點的左子樹嫁接到當前頂節點的左子樹
        leftChild = leftChild.leftChild;

        // 右旋頂端節點
        rightChild = tmpNode;
    }


    /**
     * 左旋
     */
    public void leftRotate() {
        // 克隆當前節點(頂節點)后面右旋, 當前節點降級為中間節點
        AvlTreeNode tmpNode = new AvlTreeNode(this.value);

        // 廢棄原中間節點, 當前節點替換中間節點
        value =https://www.cnblogs.com/newcooler/p/ rightChild.value;

        // 將原中間節點的左子樹調整到左旋節點的右子樹上
        tmpNode.rightChild = rightChild.leftChild;

        // 左旋節點的左子樹保持不變
        tmpNode.leftChild = leftChild;

        // 將原中間節點的右子樹嫁接到當前頂節點的左子樹
        rightChild = rightChild.rightChild;

        // 左旋頂端節點
        leftChild = tmpNode;
    }

    /**
     * 獲取子樹深度
     * @return
     */
    public int getSubDeep() {
        int leftDeep = 0;
        int rightDeep = 0;
        if(leftChild != null) {
            leftDeep = leftChild.getSubDeep();
        }
        if(rightChild != null) {
            rightDeep = rightChild.getSubDeep();
        }
        int subDeep = leftDeep >= rightDeep ? leftDeep : rightDeep;
        return subDeep + 1;
    }

    /**
     * 前序遍歷
     */
    public void print() {
        if(leftChild != null) {
            leftChild.print();
        }

        System.out.println("value: " + value + " bf: " + calBf());

        if(rightChild != null) {
            rightChild.print();
        }
    }
}

樹實作

public class AvlTree {
    AvlTreeNode rootNode = null;

    public void addNode(AvlTreeNode node) {
        if(null == rootNode) {
            rootNode = node;
            return;
        }
        rootNode.addNode(node);
    }

    /**
     * 前序遍歷
     */
    public void print() {
        rootNode.print();
    }

}

測驗類

public class TreeTest {

    public static void main(String[] args) {
        AvlTree tree = new AvlTree();

        // 先左旋 后右旋
        tree.addNode(new AvlTreeNode(20));
        tree.addNode(new AvlTreeNode(10));
        tree.addNode(new AvlTreeNode(5));
        tree.addNode(new AvlTreeNode(30));
        tree.addNode(new AvlTreeNode(40));
        tree.addNode(new AvlTreeNode(25));

        tree.print();
    }
}

標籤：Java

上一篇：Go語言開發筆記

下一篇：Mybatis的三種批量插入方式