A brief discussion on the two methods of mapping in PHP (linked list and binary tree)

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(&#39;cannot found key&#39;);
    }


    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(&#39;key is not exist&#39;);

        $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(&#39;sun&#39;,111); //O(n)
        $dict->set(&#39;sun&#39;,222);
        $dict->set(&#39;w&#39;,111);
        $dict->set(&#39;k&#39;,111);
        var_dump($dict->get(&#39;w&#39;));   //O(n)
        var_dump($dict->isExist(&#39;v&#39;));   //O(n)
        var_dump($dict->delete(&#39;sun&#39;));    //O(n)
        var_dump($dict->getSize());
        
/******************************************/
//111
//false
//true
//2

Binary 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!