文档章节

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




© 著作权归作者所有

共有 人打赏支持
帖子列表

帖子列表

粉丝 115
博文 141
码字总数 35661
作品 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
Decision Trees 笔记

Decision Tree(决策树)属于监督学习算法, 训练过程根据训练集各个属性的不同取值进行逐层划分, 每一层都是对一个属性的划分, 直至节点中的所有样本都为同一个标签(label), 从而构建出决策树;...

sailtseng
2013/11/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

集群介绍 ..

12月19日任务 18.1 集群介绍 18.2 keepalived介绍 18.3/18.4/18.5 用keepalived配置高可用集群 一.集群介绍 根据功能划分为两大类:高可用和负载均衡 高可用集群通常为两台服务器,一台工作,...

hhpuppy
14分钟前
0
0
TensorFlow的基础概念02

TensorFlow的计算流图 import osos.environ['TF_CPP_MIN_LOG_LEVEL'] = '2'#TensorFlow的计算模型,数据流图'''TensorFlow = Tensor + FlowTensor 张量 数据结构:多维数组Flo...

怪咖先生forever
20分钟前
1
0
大数据技术的发展趋势

大数据领域已经涌现出了大量新的技术,它们成为大数据采集、存储、处理和呈现的有力武器。这些技术下一步将如何发展?它们之中哪些技术将广为流行?又会诞生哪些新的技术? 技术趋向多样化,...

董黎明
35分钟前
8
0
藏在正则表达式里的陷阱

前几天线上一个项目监控信息突然报告异常,上到机器上后查看相关资源的使用情况,发现 CPU 利用率将近 100%。通过 Java 自带的线程 Dump 工具,我们导出了出问题的堆栈信息。 我们可以看到所...

前端小攻略
37分钟前
3
0
关联更新,关联查询

关联更新 update A,B SET A.c1=B.c1,A.c2=B.c2 where A.id=B.id and ... update A inner join on A.id=B.id set A.c1=B.c1,A.c2=B.c2 where... 关联查询 交叉连接(cross join),内连接(inner ......

关元
41分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部