Arbre binaire PHP (2) : arbre binaire équilibré (AVL)

Il existe pas mal de ressources sur Internet sur le principe des arbres binaires équilibrés, et la situation est un peu compliquée, donc je ne l'expliquerai pas ici Passons directement au code :

<!--?php
/**
 * author:zhongjin
 * time:2016/10/20 11:53
 * description: 平衡二叉树
 */
//结点
class Node
{
    public $key;
    public $parent;
    public $left;
    public $right;
    public $bf; //平衡因子
 
    public function __construct($key)
    {
        $this--->key = $key;
        $this->parent = NULL;
        $this->left = NULL;
        $this->right = NULL;
        $this->bf = 0;
    }
}
 
//平衡二叉树
class Avl
{
    public $root;
    const LH = +1;  //左高
    const EH = 0;   //等高
    const RH = -1;  //右高
 
    /**
     * 初始化树结构
     * @param $arr 初始化树结构的数组
     * @return null
     */
    public function init($arr)
    {
        $this->root = new Node($arr[0]);
        for ($i = 1; $i < count($arr); $i++) {
            $this->Insert($arr[$i]);
        }
    }
 
    /**
     * （对内）中序遍历
     * @param $root （树或子树的）根节点
     * @return null
     */
    private function mid_order($root)
    {
        if ($root != NULL) {
            $this->mid_order($root->left);
            echo $root->key . "-" . $root->bf . "  ";
            $this->mid_order($root->right);
        }
    }
 
    /**
     * （对外）中序遍历
     * @param null
     * @return null
     */
    public function MidOrder()
    {
        $this->mid_order($this->root);
    }
 
    /**
     * 将以$root为根节点的最小不平衡二叉树做右旋处理
     * @param $root（树或子树）根节点
     * @return null
     */
    private function R_Rotate($root)
    {
        $L = $root->left;
        if (!is_NULL($root->parent)) {
            $P = $root->parent;
            if ($root == $P->left) {
                $P->left = $L;
            } else {
                $P->right = $L;
            }
            $L->parent = $P;
        } else {
            $L->parent = NULL;
        }
        $root->parent = $L;
        $root->left = $L->right;
        $L->right = $root;
        //这句必须啊！
        if ($L->parent == NULL) {
            $this->root = $L;
        }
    }
 
    /**
     * 将以$root为根节点的最小不平衡二叉树做左旋处理
     * @param $root（树或子树）根节点
     * @return null
     */
    private function L_Rotate($root)
    {
        $R = $root->right;
        if (!is_NULL($root->parent)) {
            $P = $root->parent;
            if ($root == $P->left) {
                $P->left = $R;
            } else {
                $P->right = $R;
            }
            $R->parent = $P;
        } else {
            $R->parent = NULL;
        }
        $root->parent = $R;
        $root->right = $R->left;
        $R->left = $root;
        //这句必须啊！
        if ($R->parent == NULL) {
            $this->root = $R;
        }
    }
 
    /**
     * 对以$root所指结点为根节点的二叉树作左平衡处理
     * @param $root（树或子树）根节点
     * @return null
     */
    public function LeftBalance($root)
    {
        $L = $root->left;
        $L_bf = $L->bf;
        switch ($L_bf) {
            //检查root的左子树的平衡度，并作相应的平衡处理
            case self::LH:    //新结点插入在root的左孩子的左子树上，要做单右旋处理
                $root->bf = $L->bf = self::EH;
                $this->R_Rotate($root);
                break;
            case self::RH:    //新节点插入在root的左孩子的右子树上，要做双旋处理
                $L_r = $L->right;   //root左孩子的右子树根
                $L_r_bf = $L_r->bf;
                //修改root及其左孩子的平衡因子
                switch ($L_r_bf) {
                    case self::LH:
                        $root->bf = self::RH;
                        $L->bf = self::EH;
                        break;
                    case self::EH:
                        $root->bf = $L->bf = self::EH;
                        break;
                    case self::RH:
                        $root->bf = self::EH;
                        $L->bf = self::LH;
                        break;
                }
                $L_r->bf = self::EH;
                //对root的左子树作左平衡处理
                $this->L_Rotate($L);
                //对root作右平衡处理
                $this->R_Rotate($root);
        }
    }
 
    /**
     * 对以$root所指结点为根节点的二叉树作右平衡处理
     * @param $root（树或子树）根节点
     * @return null
     */
    public function RightBalance($root)
    {
        $R = $root->right;
        $R_bf = $R->bf;
        switch ($R_bf) {
            //检查root的右子树的平衡度，并作相应的平衡处理
            case self::RH:    //新结点插入在root的右孩子的右子树上，要做单左旋处理
                $root->bf = $R->bf = self::EH;
                $this->L_Rotate($root);
                break;
            case self::LH:    //新节点插入在root的右孩子的左子树上，要做双旋处理
                $R_l = $R->left;   //root右孩子的左子树根
                $R_l_bf = $R_l->bf;
                //修改root及其右孩子的平衡因子
                switch ($R_l_bf) {
                    case self::RH:
                        $root->bf = self::LH;
                        $R->bf = self::EH;
                        break;
                    case self::EH:
                        $root->bf = $R->bf = self::EH;
                        break;
                    case self::LH:
                        $root->bf = self::EH;
                        $R->bf = self::RH;
                        break;
                }
                $R_l->bf = self::EH;
                //对root的右子树作右平衡处理
                $this->R_Rotate($R);
                //对root作左平衡处理
                $this->L_Rotate($root);
        }
    }
 
    /**
     * 查找树中是否存在$key对应的节点
     * @param $key 待搜索数字
     * @return $key对应的节点
     */
    public function search($key)
    {
        $current = $this->root;
        while ($current != NULL) {
            if ($current->key == $key) {
                return $current;
            } elseif ($current->key > $key) {
                $current = $current->left;
            } else {
                $current = $current->right;
            }
        }
        return $current;
    }
 
    /**
     * 查找树中的最小关键字
     * @param $root 根节点
     * @return 最小关键字对应的节点
     */
    function search_min($root)
    {
        $current = $root;
        while ($current->left != NULL) {
            $current = $current->left;
        }
        return $current;
    }
 
    /**
     * 查找树中的最大关键字
     * @param $root 根节点
     * @return 最大关键字对应的节点
     */
    function search_max($root)
    {
        $current = $root;
        while ($current->right != NULL) {
            $current = $current->right;
        }
        return $current;
    }
 
    /**
     * 查找某个$key在中序遍历时的直接前驱节点
     * @param $x 待查找前驱节点的节点引用
     * @return 前驱节点引用
     */
    private function predecessor($x)
    {
        //左子节点存在，直接返回左子节点的最右子节点
        if ($x->left != NULL) {
            return $this->search_max($x->left);
        }
        //否则查找其父节点，直到当前结点位于父节点的右边
        $p = $x->parent;
        //如果x是p的左孩子，说明p是x的后继，我们需要找的是p是x的前驱
        while ($p != NULL && $x == $p->left) {
            $x = $p;
            $p = $p->parent;
        }
        return $p;
    }
 
    /**
     * 查找某个$key在中序遍历时的直接后继节点
     * @param $x 待查找后继节点的节点引用
     * @return 后继节点引用
     */
    private function successor($x)
    {
        if ($x->left != NULL) {
            return $this->search_min($x->right);
        }
        $p = $x->parent;
        while ($p != NULL && $x == $p->right) {
            $x = $p;
            $p = $p->parent;
        }
        return $p;
    }
 
    /**
     * （对内）插入结点，如果结点不存在则插入，失去平衡要做平衡处理
     * @param $root 根节点 $key 待插入树的数字
     * @return null
     */
    private function insert_node(&$root, $key)
    {
        //找到了插入的位置，插入新节点
        if (is_null($root)) {
            $root = new Node($key);
            //插入结点成功
            return TRUE;
        } else {
            //在树中已经存在和$key相等的结点
            if ($key == $root->key) {
                //插入节点失败
                return FALSE;
            } //在root的左子树中继续搜索
            elseif ($key < $root->key) {
                //插入左子树失败
                if (!($this->insert_node($root->left, $key))) {
                    //树未长高
                    return FALSE;
                }
 
                //成功插入,修改平衡因子
                if (is_null($root->left->parent)) {
                    $root->left->parent = $root;
                }
 
                switch ($root->bf) {
                    //原来左右子树等高，现在左子树增高而树增高
                    case self::EH:
                        $root->bf = self::LH;
                        //树长高
                        return TRUE;
                        break;
                    //原来左子树比右子树高，需要做左平衡处理
                    case self::LH:
                        $this->LeftBalance($root);
                        //平衡后，树并未长高
                        return FALSE;
                        break;
                    //原来右子树比左子树高，现在左右子树等高
                    case self::RH:
                        $root->bf = self::EH;
                        //树并未长高
                        return FALSE;
                        break;
                }
            } //在root的右子树中继续搜索
            else {
                //插入右子树失败
                if (!$this->insert_node($root->right, $key)) {
                    //树未长高
                    return FALSE;
                }
                //成功插入,修改平衡因子
                if (is_null($root->right->parent)) {
                    $root->right->parent = $root;
                }
                switch ($root->bf) {
                    //原来左右子树等高，现在右子树增高而树增高
                    case self::EH:
                        $root->bf = self::RH;
                        //树长高
                        return TRUE;
                        break;
                    //原来左子树比右子树高，现在左右子树等高
                    case self::LH:
                        $root->bf = self::EH;
                        return FALSE;
                        break;
                    //原来右子树比左子树高，要做右平衡处理
                    case self::RH:
                        $this->RightBalance($root);
                        //树并未长高
                        return FALSE;
                        break;
                }
            }
        }
    }
 
    /**
     * （对外）将$key插入树中
     * @param $key 待插入树的数字
     * @return null
     */
    public function Insert($key)
    {
        $this->insert_node($this->root, $key);
    }
 
    /**
     * 获取待删除的节点（删除的最终节点）
     * @param $key 待删除的数字
     * @return 最终被删除的节点
     */
    private function get_del_node($key)
    {
        $dnode = $this->search($key);
        if ($dnode == NULL) {
            throw new Exception("结点不存在！");
            return;
        }
        if ($dnode->left == NULL || $dnode->right == NULL) { #如果待删除结点无子节点或只有一个子节点，则c = dnode
            $c = $dnode;
        } else { #如果待删除结点有两个子节点，c置为dnode的直接后继，以待最后将待删除结点的值换为其后继的值
            $c = $this->successor($dnode);
        }
 
        $dnode->key = $c->key;
        return $c;
    }
 
 
    /**
     * （对内）删除指定节点，处理该结点往上结点的平衡因子
     * @param $node 最终该被删除的节点
     * @return null
     */
    private function del_node($node)
    {
        if ($node == $this->root) {
            $this->root = NULL;
            return;
        }
 
        $current = $node;
        //现在的node只有两种情况，要么只有一个子节点，要么没有子节点
        $P = $current->parent;
        //删除一个结点，第一个父节点的平衡都肯定会发生变化
        $lower = TRUE;
        while ($lower == TRUE && !is_null($P)) {
            //待删除结点是左节点
            if ($current == $P->left) {
                if($current == $node){
                    if (!is_null($current->left)) {
                        $P->left = $current->left;
                    } else {
                        $P->left = $current->left;
                    }
                }
                $P_bf = $P->bf;
                switch ($P_bf) {
                    case self::LH:
                        $P->bf = self::EH;
                        $lower = TRUE;
                        $current = $P;
                        $P = $current->parent;
                        break;
                    case self::EH:
                        $P->bf = self::RH;
                        $lower = FALSE;
                        break;
                    case self::RH:
                        $this->RightBalance($P);
                        $lower = TRUE;
                        $current = $P->parent;
                        $P = $current->parent;
                        break;
                }
            } //右结点
            else {
                if($current == $node){
                    if (!is_null($current->left)) {
                        $P->right = $current->left;
                    } else {
                        $P->right = $current->left;
                    }
                }
                $P_bf = $P->bf;
                switch ($P_bf) {
                    case self::LH:
                        $this->LeftBalance($P);
                        $lower = TRUE;
                        $current = $P->parent;
                        $P = $current->parent;
                        break;
                    case self::EH:
                        $P->bf = self::LH;
                        $lower = FALSE;
                        break;
                    case self::RH:
                        $P->bf = self::LH;
                        $lower = TRUE;
                        $current = $P;
                        $P = $current->parent;
                        break;
                }
            }
        }
    }
 
    /**
     * （对外）删除指定节点
     * @param $key 删除节点的key值
     * @return null
     */
    public function Delete($key)
    {
        $del_node = $this->get_del_node($key);
        $this->del_node($del_node);
    }
 
    /**
     * （对内）获取树的深度
     * @param $root 根节点
     * @return 树的深度
     */
    private function getdepth($root)
    {
        if ($root == NULL) {
            return 0;
        }
        $dl = $this->getdepth($root->left);
 
        $dr = $this->getdepth($root->right);
 
        return ($dl > $dr ? $dl : $dr) + 1;
    }
 
    /**
     * （对外）获取树的深度
     * @param null
     * @return null
     */
    public function Depth()
    {
        return $this->getdepth($this->root);
    }
}

Pendant le débogage, vous pouvez appeler le parcours dans l'ordre pour le faire. Dans mon dernier blog, j'ai fourni un graphique d'arborescence binaire implémenté en PHP. Avec une aide visuelle, nous pouvons mieux nous aider à déboguer. visitez mon dernier blog. : "Utiliser PHP pour réaliser l'affichage graphique d'arbres binaires"

Ce qui précède est le contenu de PHP Binary Tree (2) : Balanced Binary Tree (AVL). faites attention au site Web PHP chinois (www.php.cn) !