PHP代碼實(shí)現(xiàn)平衡二叉樹

本篇內(nèi)容介紹了“PHP代碼實(shí)現(xiàn)平衡二叉樹”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

一、什么是平衡二叉樹

平衡二叉樹（Self-Balancing Binary Search Tree 或者 Height-Balancing Binary Search Tree）譯為 自平衡的二叉查找樹或者高度平衡的二叉查找樹，簡(jiǎn)稱平衡二叉樹，也叫 AVL 樹，是一種二叉排序樹。每個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度差至多等于 1，我們將二叉樹上結(jié)點(diǎn)的左子樹深度減去右子樹深度的值稱為平衡因子 BF（Balance Factor），那么平衡二叉樹上所有結(jié)點(diǎn)的平衡因子只可能是 -1，0，1。只要樹上有結(jié)點(diǎn)的平衡因子的絕對(duì)值大于 1，則該二叉樹就是不平衡的。

下面舉四個(gè)例子：

• 圖1不滿足平衡二叉樹定義，58和88這兩個(gè)結(jié)點(diǎn)的平衡因子BF分別是2和-2，不是平衡二叉樹

• 圖2不是平衡二叉樹，因?yàn)槠胶舛鏄涫滓嵌媾判驑洌?9比58大卻是58的左子樹，這是不符合二叉排序樹的定義的

• 圖3不滿足平衡因子小于等于1的要求，對(duì)58這個(gè)節(jié)點(diǎn)來說，平衡因子BF的值是3，因而不是平衡二叉樹

• 圖4滿足平衡二叉樹的定義，是平衡二叉樹

二、平衡二叉樹的實(shí)現(xiàn)原理

平衡二叉樹構(gòu)建的基本思想就是在構(gòu)建二叉排序樹的過程中，每當(dāng)插入一個(gè)結(jié)點(diǎn)時(shí)，先檢查是否因插入而破壞了樹的平衡性，若是，則找出最小不平衡子樹。在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點(diǎn)之間的鏈接關(guān)系，進(jìn)行相應(yīng)的旋轉(zhuǎn)（左旋或右旋），使之成為新的平衡子樹。

最小不平衡子樹

距離插入結(jié)點(diǎn)最近的，且平衡因子的絕對(duì)值大于1的結(jié)點(diǎn)為根的子樹，我們稱為最小不平衡子樹。

如下圖，當(dāng)新插入結(jié)點(diǎn)37時(shí)，距離它最近的平衡因子絕對(duì)值超過1的結(jié)點(diǎn)是58 (即它的左子樹高度2減去右子樹高度0)，所以從58開始以下的子樹為最小不平衡子樹。

左旋/右旋

• 當(dāng)右子樹比左子樹高，即平衡因子小于-1，需要進(jìn)行左旋，如下圖

• 當(dāng)右子樹比左子樹低，即平衡因子大于1，需要進(jìn)行右旋，如下圖

實(shí)例

假設(shè)插入節(jié)點(diǎn)的順序是{3,2,1,4,5,6,7,10,9,8}

根據(jù)二叉排序樹的特性，我們通常會(huì)將它構(gòu)建成如下圖1的樣子。雖然它完全符合二叉排序樹的定義，但是對(duì)這樣高度達(dá)到8的二叉樹查找是非常不利的。我們更期望能構(gòu)建成下圖2的樣子，這樣才能提供高效的查詢效率。

下面就開始構(gòu)建上圖2

對(duì)于{3,2,1,4,5,6,7,10,9,8}的前兩位3和2，我們正常的構(gòu)建，到了第三個(gè)數(shù)1時(shí)發(fā)現(xiàn)根節(jié)點(diǎn)的平衡因子變成了2，需要把以 3 為根節(jié)點(diǎn)的子樹進(jìn)行右旋

插入第四個(gè)節(jié)點(diǎn) 4 的時(shí)候，左右子樹高度為 -1，符合平衡二叉樹要求，繼續(xù)插入第五個(gè)節(jié)點(diǎn)，此時(shí)又不符合平衡二叉樹的要求了，這個(gè)時(shí)候右子樹比較高，需要左旋：旋轉(zhuǎn)的時(shí)候以最小不平衡子樹為單位，此時(shí)最小的不平衡子樹是3、4、5節(jié)點(diǎn)構(gòu)成的子樹，我們以4為中心進(jìn)行左旋

繼續(xù)增加節(jié)點(diǎn)，當(dāng)插入節(jié)點(diǎn) 6 時(shí)，發(fā)現(xiàn)根節(jié)點(diǎn) 2 上維護(hù)的高度差值為 -2，又不滿足平衡二叉樹了，這個(gè)時(shí)候，需要以 2 為中心對(duì)樹進(jìn)行左旋：如下圖所示（右子樹中旋轉(zhuǎn)到根節(jié)點(diǎn)的節(jié)點(diǎn)對(duì)應(yīng)子樹需要移到旋轉(zhuǎn)后二叉樹的左子樹中）

增加結(jié)點(diǎn)7，同樣的左旋，使得整棵樹達(dá)到平衡

繼續(xù)增加節(jié)點(diǎn) 10，結(jié)構(gòu)無變化。再插入節(jié)點(diǎn) 9，發(fā)現(xiàn)結(jié)點(diǎn)7的BF變成-2又需要調(diào)整。但是這次調(diào)整需要繞個(gè)彎，不能簡(jiǎn)單的進(jìn)行簡(jiǎn)單的左旋，需要先將以10作為根節(jié)點(diǎn)的子樹做一次右轉(zhuǎn)，再將以7為根節(jié)點(diǎn)的子樹做一次左轉(zhuǎn)，讓這棵不平衡子樹轉(zhuǎn)化為平衡子樹

最后，插入節(jié)點(diǎn)8，此時(shí)情況和剛才類似，這個(gè)時(shí)候，我們以 9 為根節(jié)點(diǎn)對(duì)子樹進(jìn)行右旋，再以6為根節(jié)點(diǎn)對(duì)子樹進(jìn)行左旋，最終達(dá)到平衡狀態(tài)

相信大家應(yīng)該有點(diǎn)明白，所謂的平衡二叉樹，其實(shí)就是在二叉排序樹創(chuàng)建過程中保證它的平衡性，一旦發(fā)現(xiàn)有不平衡的情況，馬上處理，這樣就不會(huì)造成不可收拾的情況出現(xiàn)。

通過剛才這個(gè)例子，你會(huì)發(fā)現(xiàn)，當(dāng)最小不平衡子樹根結(jié)點(diǎn)的平衡因子BF是大于1時(shí)，就右旋，小于-1時(shí)就左旋

三、平衡二叉樹PHP代碼實(shí)現(xiàn)

平衡二叉樹結(jié)點(diǎn)類

<?php
/**
 * AVLNode.php
 * Created on 2019/4/27 16:44
 * Created by Wilin
 */

class AVLNode
{
    public $data;
    public $left = null;
    public $right = null;
    public $bf = 0;
    public $parent = null;

    public function __construct($data) {
        $this->data = $data;
    }
}

中序遍歷

<?php
/**
 * Traverse.php 遍歷
 * Created on 2019/4/27 11:10
 * Created by Wilin
 */
function midOrderTraverse($tree) {
    if($tree == null) {
        return;
    }

    midOrderTraverse($tree->left);
    printf("%s\n", $tree->data);
    midOrderTraverse($tree->right);
}

平衡二叉樹

<?php
/**
 * AVLTree.php
 * Created on 2019/4/27 16:51
 * Created by Wilin
 */

include "AVLNode.php";
include "../Traverse.php";

class AVLTree
{
    private $root;

    const LH = 1;
    const EH = 0;
    const RH = -1;

    public function getTree() {
        return $this->root;
    }

    public function insert(int $data) {
        $this->insert_node($data, $this->root);
    }

    /**
     * 插入節(jié)點(diǎn)
     * @param int $data
     * @param $tree
     * @return bool 是否需要調(diào)整樹結(jié)構(gòu)，true：是，false：否
     */
    protected function insert_node(int $data, &$tree) {

        //創(chuàng)建節(jié)點(diǎn)
        if (!$tree) {
            $tree = new AVLNode($data);
            $tree->bf = self::EH;
            return true;                            //插入成功之后需要判斷是否需要調(diào)整
        }

        if ($data < $tree->data) {
            //遞歸插入節(jié)點(diǎn)
            if (!$this->insert_node($data, $tree->left)) {
                return false;
            } else {
                //更正新插入節(jié)點(diǎn)對(duì)父節(jié)點(diǎn)的指向
                if (empty($tree->left->parent)) {
                    $tree->left->parent = $tree;
                }
                //判斷是否需要調(diào)整子樹
                switch ($tree->bf) {
                    case self::LH:                  //左子樹偏高，需要對(duì)左子樹進(jìn)行調(diào)整
                        $this->left_balance($tree);
                        return false;               //已經(jīng)進(jìn)行過調(diào)整，不需要繼續(xù)調(diào)整
                    case self::EH:
                        $tree->bf = self::LH;
                        return true;                //由等高變?yōu)樽蟾?，樹的整體高度發(fā)生變化，需要繼續(xù)判斷上層節(jié)點(diǎn)是否需要調(diào)整
                    case self::RH:
                        $tree->bf = self::EH;
                        return false;               //由右高變?yōu)榈雀撸瑯涞恼w高度沒有發(fā)生變化，不需要調(diào)整
                }
            }
        } else {
            if (!$this->insert_node($data,$tree->right)) {
                return false;
            } else {
                if (empty($tree->right->parent)) {
                    $tree->right->parent = $tree;
                }
                switch ($tree->bf) {
                    case self::LH:
                        $tree->bf = self::EH;
                        return false;
                    case self::EH:
                        $tree->bf = self::RH;
                        return true;
                    case self::RH:
                        $this->right_balance($tree);
                        return false;
                }
            }
        }
    }

    /**
     * 右旋
     * @param $tree
     */
    protected function right_rotate(&$tree) {
        //修改父節(jié)點(diǎn)與子樹之間的指向時(shí)需要特別注意根節(jié)點(diǎn)

        $subTree = $tree->left;
        //修改子樹對(duì)父節(jié)點(diǎn)的指向
        if ($tree->parent) {
            $subTree->parent = $tree->parent;
            $left = false;              //調(diào)整之前記錄當(dāng)前調(diào)整的子樹是父節(jié)點(diǎn)的左子樹還是右子樹
            if($tree->parent->left == $tree){
                $left = true;
            }
        } else {
            $subTree->parent = null;    //根節(jié)點(diǎn)的父節(jié)點(diǎn)為空
        }
        //交換節(jié)點(diǎn)位置
        $tree->left = $subTree->right;
        $tree->parent = $subTree;
        $subTree->right = $tree;

        $tree = $subTree;
        //修改父節(jié)點(diǎn)對(duì)子樹的指向
        if (!$tree->parent) {
            $this->root = $tree;
        } else {
            if ($left) {
                $tree->parent->left = $tree;
            } else {
                $tree->parent->right = $tree;
            }
        }
    }

    /**
     * 左旋
     * @param $tree
     */
    protected function left_rotate(&$tree) {

        $subTree = $tree->right;
        if ($tree->parent) {
            $subTree->parent  = $tree->parent;
            $left = true;
            if ($tree->parent->right == $tree) {
                $left = false;
            }
        } else {
            $subTree->parent = null;
        }

        $tree->right = $subTree->left;
        $tree->parent = $subTree;
        $subTree->left = $tree;
        $tree = $subTree;
        if (!$tree->parent) {
            $this->root = $tree;
        } else {
            if ($left) {
                $tree->parent->left = $tree;
            } else {
                $tree->parent->right = $tree;
            }
        }
    }

    /**
     * 調(diào)整左子樹
     * @param $tree
     */
    protected function left_balance(&$tree) {
        $subTree = $tree->left;
        switch ($subTree->bf) {
            case self::LH:
                $tree->bf = $subTree->bf = self::EH;            //先修改平衡因子，再進(jìn)行旋轉(zhuǎn)
                $this->right_rotate($tree);
                break;
            case self::RH:
                $subTree_r = $subTree->right;
                switch ($subTree_r->bf) {
                    case self::LH:
                        $tree->bf = self::RH;
                        $subTree->bf = self::EH;
                        break;
                    case self::RH:
                        $tree->bf = self::EH;
                        $subTree->bf = self::LH;
                        break;
                }
                $subTree_r->bf = self::EH;
                $this->left_rotate($subTree);
                $this->right_rotate($tree);
                break;
        }
    }

    /**
     * 調(diào)整右子樹
     * @param $tree
     */
    protected function right_balance(&$tree) {
        $subTree = $tree->right;
        switch ($subTree->bf) {
            case self::RH:
                $tree->bf = $subTree->bf = self::EH;
                $this->left_rotate($tree);
                break;
            case self::LH:
                $subTree_l = $subTree->left;
                switch ($subTree_l->bf) {
                    case self::RH:
                        $tree->bf = self::LH;
                        $subTree->bf = self::EH;
                        break;
                    case self::EH:
                        $tree->bf = $subTree->bf = self::EH;
                        break;
                    case self::LH:
                        $tree->bf = self::EH;
                        $subTree->bf = self::RH;
                        break;
                }
                $subTree_l->bf = self::EH;
                $this->right_rotate($subTree);
                $this->left_rotate($tree);
        }
    }
}

$avlTree = new AVLTree();
$avlTree->insert(3);
$avlTree->insert(2);
$avlTree->insert(1);
$avlTree->insert(4);
$avlTree->insert(5);
$avlTree->insert(6);
$avlTree->insert(7);
$avlTree->insert(10);
$avlTree->insert(9);
$avlTree->insert(8);
midOrderTraverse($avlTree->getTree());
print_r($avlTree->getTree());

打印結(jié)果如下

E:\www\tree\2>php AVLTree.php
2
4
6
8
10
AVLNode Object
(
    [data] => 4
    [left] => AVLNode Object
        (
            [data] => 2
            [left] => AVLNode Object
                (
                    [data] => 1
                    [left] =>
                    [right] =>
                    [bf] => 0
                    [parent] => AVLNode Object
 *RECURSION*
                )

            [right] => AVLNode Object
                (
                    [data] => 3
                    [left] =>
                    [right] =>
                    [bf] => 0
                    [parent] => AVLNode Object
 *RECURSION*
                )

            [bf] => 0
            [parent] => AVLNode Object
 *RECURSION*
        )

    [right] => AVLNode Object
        (
            [data] => 7
            [left] => AVLNode Object
                (
                    [data] => 6
                    [left] => AVLNode Object
                        (
                            [data] => 5
                            [left] =>
                            [right] =>
                            [bf] => 0
                            [parent] => AVLNode Object
 *RECURSION*
                        )

                    [right] =>
                    [bf] => 1
                    [parent] => AVLNode Object
 *RECURSION*
                )

            [right] => AVLNode Object
                (
                    [data] => 9
                    [left] => AVLNode Object
                        (
                            [data] => 8
                            [left] =>
                            [right] =>
                            [bf] => 0
                            [parent] => AVLNode Object
 *RECURSION*
                        )

                    [right] => AVLNode Object
                        (
                            [data] => 10
                            [left] =>
                            [right] =>
                            [bf] => 0
                            [parent] => AVLNode Object
 *RECURSION*
                        )

                    [bf] => 0
                    [parent] => AVLNode Object
 *RECURSION*
                )

            [bf] => 0
            [parent] => AVLNode Object
 *RECURSION*
        )

    [bf] => -1
    [parent] =>
)

“PHP代碼實(shí)現(xiàn)平衡二叉樹”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！