avl树的php实现
nuoyazhou110 2020-9-21 19:51:00 阅读(78) 评论(0)

点击(此处)折叠或打开

  1. <?php
  2. class Node {
  3.     public $left = null;
  4.     public $right = null;
  5.     public $height = null;
  6.     public $data = '';

  8.     public function __construct($data) {
  9.         $this->data = $data;
  10.         $this->height = 1;
  11.     }

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

  27.     /**
  28.      * 获取平衡因子
  29.      * @param $node
  30.      * @return int
  31.      */
  32.     function getBf($node) {
  33.         if ($node == null) {
  34.             return 0;
  35.         }
  36.         $leftHeight = $node->left->height ?? 0;
  37.         $rightHeight = $node->right->height ?? 0;
  38.         return $leftHeight - $rightHeight;
  39.     }

  41.     /**
  42.      * 右旋操作
  43.      * @param $node
  44.      * @return mixed
  45.      */
  46.     function treeRotateRight($node) {
  47.         //获取左子节点
  48.         $left = $node->left;

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

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

  58.         return $left;
  59.     }

  61.     /**
  62.      * 左旋操作
  63.      * @param $nodesz
  64.      * @return mixed
  65.      */
  66.     function treeRotateLeft($node) {
  67.         $right = $node->right;
  68.         $node->right = $right->left;
  69.         $right->left = $node;

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

  74.         return $right;
  75.     }

  77.     /**
  78.      * 平衡节点
  79.      * @param $node
  80.      * @return mixed
  81.      */
  82.     function balance($node) {
  83.         $factor = $this->getBf($node);
  84.         if($factor > 1 && $this->getBf($node->left) > 0 ){//LL
  85.             return $this->treeRotateRight($node);
  86.         } elseif ($factor > 1 && $this->getBf($node->left) <= 0) {
  87.             //LR 先左旋 left子节点
  88.             $temp = $this->treeRotateLeft($node->left);
  89.             //再右旋
  90.             return $this->treeRotateRight($temp);
  91.         } elseif ($factor < -1 && $this->getBf($node->right) <= 0) {
  92.             return $this->treeRotateLeft($node);
  93.         } elseif ($factor < -1 && $this->getBf($node->right) > 0 ) {
  94.             $temp = $this->treeRotateRight($node->right);
  95.             return $this->treeRotateLeft($temp);
  96.         } else {
  97.             return $node;
  98.         }
  99.     }

  101.     function add($node,$value) {
  102.         if($node == null) {
  103.             $node = new Node($value);
  104.             return $node;
  105.         } elseif ($value > $node->data) {
  106.             $node->right = $this->add($node->right,$value);
  107.         } elseif ($value < $node->data) {
  108.             $node->left = $this->add($node->left,$value);
  109.         } else {

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

  115.         //计算节点的平衡因子
  116.         $bf = $node->getBf($node);
  117.         if(abs($bf) > 1) {
  118.             $node = $node->balance($node);
  119.         }
  120.         return $node;
  121.     }

  123. }

  125. /**
  126.  * 中序遍历
  127.  * @param $tree
  128.  */
  129. function inOrder($tree) {
  130.     if($tree === null) {
  131.         return;
  132.     }
  133.     inOrder($tree->left);
  134.     var_dump($tree->data);
  135.     inOrder($tree->right);
  136. }

  138. //根节点
  139. $root = new Node(5);
  140. $root = $root->add($root,4);
  141. $root = $root->add($root,3);
  142. $root = $root->add($root,2);
  143. $root = $root->add($root,1);
  144. $root = $root->add($root,0);
  145. $root = $root->add($root,-1);
  146. $root = $root->add($root,-2);
  147. $root = $root->add($root,10000);
  148. $root = $root->add($root,100001);
  149. inOrder($root);
  150. print_r($root);
  151. ?>

原文链接:http://blog.chinaunix.net/uid-27003384-id-5838316.html