文档章节

PHP开发中的数据类型 ( 第2篇 ) :Trees

帖子列表
 帖子列表
发布于 2014/06/18 16:28
字数 969
阅读 27
收藏 0

参考自: http://www.sitepoint.com/data-structures-2/  (PublishedJuly 5, 2013)

第二篇开始搬到OSC上面来

数据结构管理经常遇到三种类型的操作:

- 插入, 即向结构中插入数据
- 删除, 即从结构中删除数据
- 查询, 即从结构中查询数据

比如说有这么一张表:

何欢 13911111111
吴佳旻 13922222222
徐琦怡 13933333333

这时,用stack 或者 queue 数据结构都不适合了,要查找一个值,必须遍历该表,所以平均消耗是要查询n/2(n是列表长度)条记录。列表越长,查询越慢。我们需要一种对查询优化的数据结构,tree应运而生。

我们可以把一张表抽象成四种类型的操作(这跟数据库的crud操作非常类似)

- 新建, 即新建一张表
- 插入, 即向表中插入数据
- 删除, 即从表中删除数据
- 查询, 即从表中查询数据

这种表叫做线性植入,早期的数据库设计)IBM’s Indexed Sequential Access Method (ISAM),MS-DOS’s File Allocation Table (FAT)等)等采用的就是这种方式。其缺点是插入和删除的时候消耗比较大,因为值的长度是可大可小的。

而Tree的设计避免了这个问题(Why?),许多数据库(如MySQL的MYISAM,Apple's HFS+, Microsoft’s NTFS, and btrfs for Linux等)都用Tree数据结构来构建索引。

tree-02

Tree是按等级划分的,有父、子级,没有父的节点称作root(根),没有子的节点称作leaf(叶),拥有相同父的节点叫做siblings。二叉树(binary tree)就是有双向节点的树形数据结构,它是最简单的树结构。

把它们变成PHP代码:

class BinaryNode
{
    public $value;    // contains the node item
    public $left;     // the left child BinaryNode
    public $right;     // the right child BinaryNode
 
    public function __construct($item) {
        $this->value = $item;
        // new nodes are leaf nodes
        $this->left = null;
        $this->right = null;
    }
}
 
class BinaryTree
{
    protected $root; // the root node of our tree
 
    public function __construct() {
        $this->root = null;
    }
 
    public function isEmpty() {
        return $this->root === null;
    }
}
插入节点的逻辑

1 如果Tree是空的,就在root节点插入一个新节点
2 只要Tree不为空:
    a 如果当前节点是空的,就在这里插入新节点,中止
    b 否则,如果新节点 > 当前节点,就尝试插入新节点到该节点的右侧,然后重复步骤2
    c 否则,如果新节点  < 当前节点,就尝试插入新节点到该节点的左侧,然后重复步骤2
    d 否则,就说明值已经在Tree里存在了,插不插都一样,所以不插

插入节点的代码

class BinaryTree
{
...
    public function insert($item) {
        $node = new BinaryNode($item);
        if ($this->isEmpty()) {
            // special case if tree is empty
            $this->root = $node;
        }
        else {
            // insert the node somewhere in the tree starting at the root
            $this->insertNode($node, $this->root);
        }
    }
   
    protected function insertNode($node, &$subtree) {
        if ($subtree === null) {
            // insert node here if subtree is empty
            $subtree = $node;
        }
        else {
            if ($node->value > $subtree->value) {
                // keep trying to insert right
                $this->insertNode($node, $subtree->right);
            }
            else if ($node->value < $subtree->value) {
                // keep trying to insert left
                $this->insertNode($node, $subtree->left);
            }
            else {
                // reject duplicates
            }
        }
    }
}

查询树的四种策略

- pre-order,即先查询当前节点,然后查询左右子节点 (比较适合于节点的插入 和 子树克隆)
- in-order,即先查询左节点,再查当前节点,再查右节点 (比较适合于搜索二叉树)
- post-order,即先查询左右节点,再查询中节点 (比较适合于删除节点)
- level-order,即先查询当前节点,再查询全部的相邻节点,最后查询下一级节点

下面的代码演示了用 in-order 方式查询:

class BinaryNode
{
...
    // perform an in-order traversal of the current node
    public function dump() {
        if ($this->left !== null) {
            $this->left->dump();
        }
        var_dump($this->value);
        if ($this->right !== null) {
            $this->right->dump();
        }
    }
}
 
class BinaryTree
{
...
    public function traverse() {
        // dump the tree rooted at "root"
        $this->root->dump();
    }
}

调用 traverse() 方法会显示从root节点开始的按顺序排序的整个Tree。

最后,这tmd有啥用? 谁能告诉我一下?

EOF




© 著作权归作者所有

共有 人打赏支持
帖子列表

帖子列表

粉丝 114
博文 139
码字总数 35083
作品 1
浦东
程序员
学界 | Jeff Dean新提出机器学习索引替代B-Trees:可提速3倍

  选自arXiv   机器之心编译   参与:黄小天、刘晓坤      Jeff Dean 的最新论文中把索引视为模型,探索了深度学习模型学习的索引优于传统索引结构的条件。初步结果表明,借助神经...

机器之心
2017/12/13
0
0
Jeff Dean新提出机器学习索引替代B-Trees:可提速3倍

摘要:Jeff Dean 的最新论文中把索引视为模型,探索了深度学习模型学习的索引优于传统索引结构的条件。初步结果表明,借助神经网络学习索引可以超过缓存优化的 B-Trees 高达 70%的速度,同时...

机器之心
2017/12/14
0
0
机器学习算法 --- Pruning (decision trees) & Random Forest Algorithm

一、Table for Content   在之前的文章中我们介绍了Decision Trees Agorithms,然而这个学习算法有一个很大的弊端,就是很容易出现Overfitting,为了解决此问题人们找到了一种方法,就是对...

码农47
06/26
0
0
买《Python从小白到大牛》专题视频课程,送配套纸质图书

经过一年多时间的呕心沥血,Python立体化图书——《Python从小白到大牛》即将与大家见面了。所谓立体化图书包括:电子图书、视频、课件和服务等内容。 《Python从小白到大牛》纸质图书将于9...

tony关东升
07/23
0
0
JSON进阶第二篇 AJAX方式传递JSON数据

上一篇《JSON进阶第一篇 在PHP与javascript 中使用JSON》示范了在PHP和javascript中如何使用JSON类型的数据,本篇将介绍用AJAX方式得到JSON数据从而动态生成标题和提示语句。这种技术在静态页...

晨曦之光
2012/05/21
75
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

idea新建springCloud项目(5)- 订单服务

1.创建订单api,如下: 2.创建订单实现逻辑 3.新建订单、订单商品表 -- 订单 create table `order_master` ( `order_id` varchar(32) not null, `buyer_name` varchar(32) not null comment......

monroeCode
20分钟前
1
1
游戏开发经验谈(二):对战类全球服游戏的设计与实现

上篇文章《游戏开发经验谈(一):游戏架构里隐藏的五个坑及其应对方案》,我们主要讲解了游戏架构设计当中隐藏的一些坑及其应对方案,错过的小伙伴可以回溯之前的内容。本期内容,将会重点介...

UCloudTech
30分钟前
0
0
Mysql基本语法

一.联合主键 drop table CONTENT_AND_CATALOG;CREATE TABLE `tobebetter`.`CONTENT_AND_CATALOG` ( `ID` VARCHAR(120) NOT NULL , `CONTENT_ID` VARCHAR(120) , `CA......

我是菜鸟我骄傲
31分钟前
0
0
179. centos7 安装mariadb

1. centos7 中安装mariadb 1.1 执行安装 centos7 自带了mariadb yum -y install mariadb mariadb-server 1.2 启动mariadb systemctl start mariadb 1.3 设置开机启动 systemctl enable maria......

Lucky_Me
38分钟前
0
0
【AI实战】动手训练自己的目标检测模型(YOLO篇)

在前面的文章中,已经介绍了基于SSD使用自己的数据训练目标检测模型(见文章:手把手教你训练自己的目标检测模型),本文将基于另一个目标检测模型YOLO,介绍如何使用自己的数据进行训练。 ...

雪饼
45分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部