legongju.com
我们一直在努力
2024-12-23 20:38 | 星期一

php二叉树怎样构建平衡

在PHP中,构建一个平衡的二叉树可以使用AVL树。AVL树是一种自平衡二叉搜索树,它在每次插入或删除节点后都会自动调整以保持平衡状态。以下是一个简单的PHP实现:

class TreeNode {
    public $value;
    public $left;
    public $right;
    public $height;

    public function __construct($value) {
        $this->value = https://www.yisu.com/ask/$value;>left = null;
        $this->right = null;
        $this->height = 1;
    }
}

class AVLTree {
    private $root;

    private function getHeight($node) {
        if ($node === null) {
            return 0;
        }
        return $node->height;
    }

    private function getBalanceFactor($node) {
        if ($node === null) {
            return 0;
        }
        return $this->getHeight($node->left) - $this->getHeight($node->right);
    }

    private function rightRotate($y) {
        $x = $y->left;
        $T2 = $x->right;

        $x->right = $y;
        $y->left = $T2;

        $y->height = max($this->getHeight($y->left), $this->getHeight($y->right)) + 1;
        $x->height = max($this->getHeight($x->left), $this->getHeight($x->right)) + 1;

        return $x;
    }

    private function leftRotate($x) {
        $y = $x->right;
        $T2 = $y->left;

        $y->left = $x;
        $x->right = $T2;

        $x->height = max($this->getHeight($x->left), $this->getHeight($x->right)) + 1;
        $y->height = max($this->getHeight($y->left), $this->getHeight($y->right)) + 1;

        return $y;
    }

    public function insert($value) {
        $this->root = $this->insertNode($this->root, $value);
    }

    private function insertNode($node, $value) {
        if ($node === null) {
            return new TreeNode($value);
        }

        if ($value < $node->value) {
            $node->left = $this->insertNode($node->left, $value);
        } else if ($value > $node->value) {
            $node->right = $this->insertNode($node->right, $value);
        } else {
            return $node; // Duplicate values are not allowed
        }

        $node->height = 1 + max($this->getHeight($node->left), $this->getHeight($node->right));

        $balanceFactor = $this->getBalanceFactor($node);

        // Left Left Case
        if ($balanceFactor > 1 && $value < $node->left->value) {
            return $this->rightRotate($node);
        }

        // Right Right Case
        if ($balanceFactor < -1 && $value > $node->right->value) {
            return $this->leftRotate($node);
        }

        // Left Right Case
        if ($balanceFactor > 1 && $value > $node->left->value) {
            $node->left = $this->leftRotate($node->left);
            return $this->rightRotate($node);
        }

        // Right Left Case
        if ($balanceFactor < -1 && $value < $node->right->value) {
            $node->right = $this->rightRotate($node->right);
            return $this->leftRotate($node);
        }

        return $node;
    }
}

// Example usage:
$avlTree = new AVLTree();
$avlTree->insert(10);
$avlTree->insert(20);
$avlTree->insert(30);
$avlTree->insert(40);
$avlTree->insert(50);
$avlTree->insert(25);

这个实现包括了一个TreeNode类,用于表示二叉树的节点,以及一个AVLTree类,用于管理二叉树的操作。AVLTree类包含了插入节点、左旋转、右旋转等方法,以确保树在每次插入或删除节点后都能保持平衡。

未经允许不得转载 » 本文链接:https://www.legongju.com/article/34267.html

相关推荐

  • php tempnam可跨平台吗

    php tempnam可跨平台吗

    tempnam() 函数在 PHP 中用于生成一个唯一的临时文件名
    然而,tempnam() 函数并不保证在所有平台上都能生成完全相同的临时文件名。这取决于操作系统和文件系...

  • php tempnam会被系统回收吗

    php tempnam会被系统回收吗

    tempnam() 函数在 PHP 中用于生成一个唯一的临时文件名
    然而,在某些情况下,操作系统可能会回收这些临时文件。例如,当系统的临时文件夹空间不足或者文件超...

  • php tempnam可用空间多大

    php tempnam可用空间多大

    tempnam() 函数在 PHP 中用于生成一个唯一的临时文件名
    然而,实际可用的存储空间可能受到多种因素的影响,例如磁盘空间限制、操作系统和文件系统的限制等。...

  • php tempnam和tmpfile啥区别

    php tempnam和tmpfile啥区别

    tempnam 和 tmpfile 是 PHP 中两个用于创建临时文件的函数,但它们之间存在一些关键区别: tempnam: tempnam 函数用于创建一个唯一的临时文件名。
    它接受两...

  • php二叉树如何查找值

    php二叉树如何查找值

    在PHP中,可以使用递归或迭代的方法来查找二叉树中的值。以下是使用递归方法的示例:
    首先,定义一个二叉树节点类:
    class TreeNode { public $value;...

  • php二叉树能做什么应用

    php二叉树能做什么应用

    PHP 二叉树在多个领域都有实际应用,以下是一些具体的应用场景: 文件系统管理:二叉树结构非常适合用于表示和管理文件系统。每个节点可以表示一个目录或文件,节...

  • php二叉树怎样遍历节点

    php二叉树怎样遍历节点

    在 PHP 中,可以使用递归或迭代方法来遍历二叉树节点。这里,我们将介绍两种方法:前序遍历、中序遍历和后序遍历。
    首先,定义一个简单的二叉树节点类:

  • aardio php怎样进行调试

    aardio php怎样进行调试

    Aardio 是一种新的编程语言,它集成了多种现代编程语言的特性,包括 C++、Java、Python 和 JavaScript 等。然而,关于如何在 Aardio 中使用 PHP 进行调试,目前并...