在PHP中,構建一個平衡的二叉樹可以使用AVL樹。AVL樹是一種自平衡二叉搜索樹,它在每次插入或刪除節點后都會自動調整以保持平衡狀態。以下是一個簡單的PHP實現:
class TreeNode {
public $value;
public $left;
public $right;
public $height;
public function __construct($value) {
$this->value = $value;
$this->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
類包含了插入節點、左旋轉、右旋轉等方法,以確保樹在每次插入或刪除節點后都能保持平衡。