avl树的php实现

<?php
class Node {
    public $left = null;
    public $right = null;
    public $height = null;
    public $data = '';

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

    /**
     * 计算节点高度 (叶子 节点1 每往上一层 + 1)
     * 在插入结点时， 沿插入的路径更新结点的高度值
     * 在删除结点时（delete）,沿删除的路径更新结点的高度值
     * @param $node
     * @return int|mixed
     */
    function getHeight($node) {
        if ($node == null) {
            return 0;
        }
        return max($node->getHeight($node->left),$node->getHeight($node->right)) +1;
    }

    /**
     * 获取平衡因子
     * @param $node
     * @return int
     */
    function getBf($node) {
        if ($node == null) {
            return 0;
        }
        $leftHeight = $node->left->height ?? 0;
        $rightHeight = $node->right->height ?? 0;
        return $leftHeight - $rightHeight;
    }

    /**
     * 右旋操作
     * @param $node
     * @return mixed
     */
    function treeRotateRight($node) {
        //获取左子节点
        $left = $node->left;

        //将要被抛弃的节点 转为旋转后的root的左孩子
        $node->left = $left->right;
        //$left 作为根节点
        $left->right = $node;

        $left->height = $this->getHeight($left);
        $node->height = $this->getHeight($node);

        return $left;
    }

    /**
     * 左旋操作
     * @param $nodesz
     * @return mixed
     */
    function treeRotateLeft($node) {
        $right = $node->right;
        $node->right = $right->left;
        $right->left = $node;

        $right->height = $this->getHeight($right);
        $node->height = $this->getHeight($node);

        return $right;
    }

    /**
     * 平衡节点
     * @param $node
     * @return mixed
     */
    function balance($node) {
        $factor = $this->getBf($node);
        if($factor > 1 && $this->getBf($node->left) > 0 ){//LL
            return $this->treeRotateRight($node);
        } elseif ($factor > 1 && $this->getBf($node->left) <= 0) {
            //LR 先左旋 left子节点
            $temp = $this->treeRotateLeft($node->left);
            //再右旋
            return $this->treeRotateRight($temp);
        } elseif ($factor < -1 && $this->getBf($node->right) <= 0) {
            return $this->treeRotateLeft($node);
        } elseif ($factor < -1 && $this->getBf($node->right) > 0 ) {
            $temp = $this->treeRotateRight($node->right);
            return $this->treeRotateLeft($temp);
        } else {
            return $node;
        }
    }

    function add($node,$value) {
        if($node == null) {
            $node = new Node($value);
            return $node;
        } elseif ($value > $node->data) {
            $node->right = $this->add($node->right,$value);
        } elseif ($value < $node->data) {
            $node->left = $this->add($node->left,$value);
        } else {

        }
        //插入新节点后重新计算节点高度
        $node->height = max($node->getHeight($node->left),$node->getHeight($node->right)) + 1;

        //计算节点的平衡因子
        $bf = $node->getBf($node);
        if(abs($bf) > 1) {
            $node = $node->balance($node);
        }
        return $node;
    }

}

/**
 * 中序遍历
 * @param $tree
 */
function inOrder($tree) {
    if($tree === null) {
        return;
    }
    inOrder($tree->left);
    var_dump($tree->data);
    inOrder($tree->right);
}

//根节点
$root = new Node(5);
$root = $root->add($root,4);
$root = $root->add($root,3);
$root = $root->add($root,2);
$root = $root->add($root,1);
$root = $root->add($root,0);
$root = $root->add($root,-1);
$root = $root->add($root,-2);
$root = $root->add($root,10000);
$root = $root->add($root,100001);
inOrder($root);
print_r($root);
?>