文档章节

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

帖子列表
 帖子列表
发布于 2014/06/18 16:28
字数 969
阅读 27
收藏 0
点赞 0
评论 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
博文 107
码字总数 34824
作品 1
浦东
程序员
学界 | Jeff Dean新提出机器学习索引替代B-Trees:可提速3倍

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

机器之心 ⋅ 2017/12/13 ⋅ 0

Jeff Dean新提出机器学习索引替代B-Trees:可提速3倍

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

机器之心 ⋅ 2017/12/14 ⋅ 0

PHP扩展实现类扩展

在第一篇文章中,我们所开发的扩展是单个函数,本篇文章看一下如何开发一个类扩展。假设我们要用PHP扩展实 现一个类Person,它有一个private的成员变量$_name和两个public的实例方法getName...

mickelfeng ⋅ 2013/04/13 ⋅ 0

php 数据类型转换

本篇文章主要分享一下PHP数据类型转换的知识。 PHP的数据类型转换属于强制转换,允许转换的PHP数据类型有: (int)、(integer):转换成整形 (float)、(double)、(real):转换成浮点...

微信迷 ⋅ 2014/01/28 ⋅ 0

PHP视频教程搜集整理分享【www.eaglephp.com】

1、PHP视频教程 (第一讲) PHP环境搭配和代码调试 2、PHP视频教程 (第二讲) PHP的数据类型 源码调试 3、PHP视频教程 (第三讲) 常用PHP运算类型介绍与应用 4、PHP视频教程 (第四讲) PHP条件语句...

maoxiaojian ⋅ 2013/02/28 ⋅ 5

现货!《PHP7实践指南:o2o网站与App后台开发》京东天猫有售

终于发售了,啥也不想说了,喜欢的或需要的就点击 链接 进去购买吧。 另外此书将作为 2017 PHP全球开发者大会 现场活动用书 天猫购书 包邮 PHP7实践指南:O2O网站与App后台开发 数据库设计 PH...

szxy1234 ⋅ 2017/11/02 ⋅ 0

JSON进阶第二篇 AJAX方式传递JSON数据

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

长平狐 ⋅ 2012/12/10 ⋅ 0

JSON进阶第二篇 AJAX方式传递JSON数据

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

彭博 ⋅ 2012/04/12 ⋅ 0

JSON进阶第二篇 AJAX方式传递JSON数据

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

晨曦之光 ⋅ 2012/05/21 ⋅ 0

MoreWindows博客目录(微软最有价值专家,原创技术文章152篇)

为了方便大家查找和学习,现将本人博客中所有博客文章列出目录。 一. 白话经典算法 目前有17篇,分为七大排序和经典面试题讲解两大类 1. 《白话经典算法系列之一 冒泡排序的三种实现》 2. 《...

morewindows ⋅ 2013/12/24 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

个人博客的运营模式能否学习TMALL天猫质量为上?

心情随笔|个人博客的运营模式能否学习TMALL天猫质量为上? 中国的互联网已经发展了很多年了,记得在十年前,个人博客十分流行,大量的人都在写博客,而且质量还不错,很多高质量的文章都是在...

原创小博客 ⋅ 48分钟前 ⋅ 0

JavaScript零基础入门——(十一)JavaScript的DOM操作

JavaScript零基础入门——(十一)JavaScript的DOM操作 大家好,欢迎回到我们的JavaScript零基础入门。最近有些同学问我说,我讲的的比书上的精简不少。其实呢,我主要讲的是我在开发中经常会...

JandenMa ⋅ 今天 ⋅ 0

volatile和synchronized的区别

volatile和synchronized的区别 在讲这个之前需要先了解下JMM(Java memory Model :java内存模型):并发过程中如何处理可见性、原子性、有序性的问题--建立JMM模型 详情请看:https://baike.b...

MarinJ_Shao ⋅ 今天 ⋅ 0

深入分析Kubernetes Critical Pod(一)

Author: xidianwangtao@gmail.com 摘要:大家在部署Kubernetes集群AddOn组件的时候,经常会看到Annotation scheduler.alpha.kubernetes.io/critical-pod"="",以表示这是一个关键服务,那你知...

WaltonWang ⋅ 今天 ⋅ 0

原子性 - synchronized关键词

原子性概念 原子性提供了程序的互斥操作,同一时刻只能有一个线程能对某块代码进行操作。 原子性的实现方式 在jdk中,原子性的实现方式主要分为: synchronized:关键词,它依赖于JVM,保证了同...

dotleo ⋅ 今天 ⋅ 0

【2018.06.22学习笔记】【linux高级知识 14.4-15.3】

14.4 exportfs命令 14.5 NFS客户端问题 15.1 FTP介绍 15.2/15.3 使用vsftpd搭建ftp

lgsxp ⋅ 今天 ⋅ 0

JeeSite 4.0 功能权限管理基础(Shiro)

Shiro是Apache的一个开源框架,是一个权限管理的框架,实现用户认证、用户授权等。 只要有用户参与一般都要有权限管理,权限管理实现对用户访问系统的控制,按照安全规则或者安全策略控制用户...

ThinkGem ⋅ 昨天 ⋅ 0

python f-string 字符串格式化

主要内容 从Python 3.6开始,f-string是格式化字符串的一种很好的新方法。与其他格式化方式相比,它们不仅更易读,更简洁,不易出错,而且速度更快! 在本文的最后,您将了解如何以及为什么今...

阿豪boy ⋅ 昨天 ⋅ 0

Python实现自动登录站点

如果我们想要实现自动登录,那么我们就需要能够驱动浏览器(比如谷歌浏览器)来实现操作,ChromeDriver 刚好能够帮助我们这一点(非谷歌浏览器的驱动有所不同)。 一、确认软件版本 首先我们...

blackfoxya ⋅ 昨天 ⋅ 0

线性回归原理和实现基本认识

一:介绍 定义:线性回归在假设特证满足线性关系,根据给定的训练数据训练一个模型,并用此模型进行预测。为了了解这个定义,我们先举个简单的例子;我们假设一个线性方程 Y=2x+1, x变量为商...

wangxuwei ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部