PHP开发中的数据类型 ( 第2篇 ) :Trees
PHP开发中的数据类型 ( 第2篇 ) :Trees
添加软件 发表于3年前
PHP开发中的数据类型 ( 第2篇 ) :Trees
  • 发表于 3年前
  • 阅读 24
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

参考自: 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




共有 人打赏支持
添加软件
粉丝 116
博文 106
码字总数 34813
作品 1
×
添加软件
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: