This article will introduce to you how PHP uses linked lists or binary trees to implement mapping. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to everyone.
[Recommended learning: "PHP Video Tutorial"]
Mapping
Maps, or projections, are often equated with functions in mathematics and related fields. Based on this, a partial mapping is equivalent to a partial function, and a complete mapping is equivalent to a complete function.
Map is a data structure (key, value) used to access key-value pairs. One key can only correspond to one value and the key cannot be repeated.
Implementation
The implementation of mapping can be implemented using a linked list or a binary tree.
Linked list implementation:
<?php
/**
* 接口 字典
* Interface Dict
* @package app\models
*/
Interface Dict
{
public function set( $key , $value );
public function get( $key );
public function isExist( $key );
public function delete($key);
public function getSize();
}
class DictLinkList implements Dict
{
protected $size=0;
public $key;
public $value;
public $next;
public function __construct($key=null,$value=null,$next=null)
{
$this->key = $key;
$this->value = $value;
$this->next = $next;
}
public function set($key,$value){
$node = $this;
while( $node && $node->next ){
if( $node->next->key==$key ){
$node->next->value = $value;
return $node->next;
}
$node = $node->next;
}
$node->next = new self($key,$value,$node->next);
$this->size++;
return $node->next;
}
public function get($key){
$node = $this;
while($node){
if( $node->key ==$key ){
return $node->value;
}
$node = $node->next;
}
throw new \Exception('cannot found key');
}
public function isExist($key)
{
$node = $this;
while($node){
if( $node->key ==$key ){
return true;
}
$node = $node->next;
}
return false;
}
public function delete($key)
{
if( $this->size==0)
throw new \Exception('key is not exist');
$node = $this;
while($node->next){
if( $node->next->key == $key ){
$node->next = $node->next->next;
$this->size--;
break;
}
$node = $node->next;
}
return $this;
}
public function getSize()
{
return $this->size;
}
}Test:
<?php
$dict = new DictLinkList();
$dict->set('sun',111); //O(n)
$dict->set('sun',222);
$dict->set('w',111);
$dict->set('k',111);
var_dump($dict->get('w')); //O(n)
var_dump($dict->isExist('v')); //O(n)
var_dump($dict->delete('sun')); //O(n)
var_dump($dict->getSize());
/******************************************/
//111
//false
//true
//2Binary tree implementation
<?php
class DictBtree implements Dict
{
public $key;
public $value;
public $left;
public $right;
private $size;
public function __construct($key=null,$value=null)
{
$this->key = $key;
$this->value = $value;
$this->left = null;
$this->right = null;
$this->size = 0;
}
public function set( $key , $value ){
if( $this->size ==0 ){
$node = new static( $key,$value );
$this->key = $node->key;
$this->value = $node->value;
$this->size++;
}else{
$node = $this;
while($node){
if( $node->key == $key ){
$node->value = $value;
break;
}
if($node->key>$key){
if($node->left==null){
$node->left = new static( $key,$value );
$this->size++;
break;
}
$node = $node->left;
}else{
if($node->right==null){
$node->right = new static( $key,$value );
$this->size++;
break;
}
$node = $node->right;
}
}
}
return $this;
}
public function get( $key ){
if( $this->size ==0 )
throw new \Exception('empty');
$node = $this;
while($node) {
if ($node->key == $key) {
return $node->value;
}
if ($node->key > $key) {
$node = $node->left;
} else {
$node = $node->right;
}
}
throw new \Exception('this key not exist');
}
public function isExist( $key ){
if( $this->size ==0 )
return false;
$node = $this;
while($node) {
if ($node->key == $key) {
return true;
}
if ($node->key > $key) {
$node = $node->left;
} else {
$node = $node->right;
}
}
return false;
}
public function delete($key){
//找到元素，寻找元素左边最小元素
$node = $this->select($key);
if( $node->right!=null ){
$node1 = $node->selectMin($node->right);
//替换当前node
$node->key = $node1->key;
$node->value = $node1->value;
//删除$node->right最小元素，获取最终元素赋给$node->right
$nodeMin = $this->deleteMin($node->right);
$node->right = $nodeMin;
}else{
$node1 = $node->selectMax($node->left);
$node->key = $node1->key;
$node->value = $node1->value;
$nodeMax = $this->deleteMax($node->left);
$node->left = $nodeMax;
}
return $this;
}
protected function deleteMin( $node ){
// if( $this->size ==0 )
// throw new \Exception('empty');
// $prev = new static();
// $prev->left = $node;
// while($prev->left->left!=null){
//
// $prev = $prev->left;
// }
// $prev->left = $prev->left->right;
if( $node->left==null ){
$rightNode = $node->right;
$node->right = null;
$this->size--;
return $rightNode;
}
$node->left = $this->deleteMin($node->left);
return $node;
}
protected function deleteMax($node){
if( $node->right==null ){
$leftNode = $node->left;
$node->left = null;
$this->size--;
return $leftNode;
}
$node->right = $this->deleteMax($node->right);
return $node;
}
public function getSize(){
return $this->size;
}
public function select($key){
$node = $this;
while($node){
if($node->key==$key){
return $node;
}
if ($node->key > $key) {
$node = $node->left;
} else {
$node = $node->right;
}
}
throw new \Exception('this key not exist');
}
public function selectMin( $node ){
while($node->left){
$node = $node->left;
}
return $node;
}
public function selectMax( $node ){
while($node->right){
$node = $node->right;
}
return $node;
}
}Complexity analysis
Linked list O(n)
Binary search tree O(log n)
For more programming-related knowledge, please visit: programming video! !
The above is the detailed content of A brief discussion on the two methods of mapping in PHP (linked list and binary tree). For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
