AVL树是一种自平衡的二叉搜索树，它通过在插入和删除节点时进行旋转操作来保持树的平衡。本文将提供一个PHP实现的AVL树的实例，包括树的创建、插入、删除和搜索等基本操作。
实例代码
```php
class AVLNode {
public $key;
public $left;
public $right;
public $height;
public function __construct($key) {
$this->key = $key;
$this->left = null;
$this->right = null;
$this->height = 1;
}
}
class AVLTree {
private $root;
public function insert($key) {
$this->root = $this->insertNode($this->root, $key);
}
private function insertNode($node, $key) {
if ($node === null) {
return new AVLNode($key);
}
if ($key < $node->key) {
$node->left = $this->insertNode($node->left, $key);
} else if ($key > $node->key) {
$node->right = $this->insertNode($node->right, $key);
} else {
return $node;
}
$node->height = 1 + max($this->getHeight($node->left), $this->getHeight($node->right));
$balance = $this->getBalance($node);
if ($balance > 1 && $key < $node->left->key) {
return $this->rightRotate($node);
}
if ($balance < -1 && $key > $node->right->key) {
return $this->leftRotate($node);
}
if ($balance > 1 && $key > $node->left->key) {
$node->left = $this->leftRotate($node->left);
return $this->rightRotate($node);
}
if ($balance < -1 && $key < $node->right->key) {
$node->right = $this->rightRotate($node->right);
return $this->leftRotate($node);
}
return $node;
}
private function leftRotate($y) {
$x = $y->right;
$T2 = $x->left;
$x->left = $y;
$y->right = $T2;
$y->height = 1 + max($this->getHeight($y->left), $this->getHeight($y->right));
$x->height = 1 + max($this->getHeight($x->left), $this->getHeight($x->right));
return $x;
}
private function rightRotate($x) {
$y = $x->left;
$T2 = $y->right;
$y->right = $x;
$x->left = $T2;
$x->height = 1 + max($this->getHeight($x->left), $this->getHeight($x->right));
$y->height = 1 + max($this->getHeight($y->left), $this->getHeight($y->right));
return $y;
}
private function getHeight($node) {
if ($node === null) {
return 0;
}
return $node->height;
}
private function getBalance($node) {
if ($node === null) {
return 0;
}
return $this->getHeight($node->left) - $this->getHeight($node->right);
}
public function preOrder() {
$result = [];
$this->preOrderTraversal($this->root, $result);
return $result;
}
private function preOrderTraversal($node, &$result) {
if ($node === null) {
return;
}
array_push($result, $node->key);
$this->preOrderTraversal($node->left, $result);
$this->preOrderTraversal($node->right, $result);
}
}
// 使用示例
$avlTree = new AVLTree();
$avlTree->insert(10);
$avlTree->insert(20);
$avlTree->insert(30);
$avlTree->insert(40);
$avlTree->insert(50);
$avlTree->insert(25);
$result = $avlTree->preOrder();
echo "
