什么是拉链数据结构和应我会使用它吗？

Question

问题是简单的：我不能理解的 拉链 数据结构。

我的问题是有关其使用的一棵树。

我想了解我如何可以改变的树节点使用拉链。怎么不复制整个树(或最部分)。

请澄清如果我错了与拉链。也许它不能帮助树更新？
或者，也许，它是可能的，更新的树和我只是看不到的方式吗？

Answer 1

让我们先从拉链模拟的名单。如果你想修改列表的第n个元素，它需要为O（n），因为你必须复制n-1个第一要素。相反，你可以保持列表作为结构（（第n-1个元素逆转）第n个元素（其余的元素））。例如，该列表(1 2 3 4 5 6)修改在3将表示为((2 1) 3 (4 5 6))。现在，你可以很容易地改变3到别的东西。您也可以轻松移动焦点左((1) 2 (3 4 5 6))和右((3 2 1) 4 (5 6))。

一个拉链是施加到树木同样的想法。你代表了一定的焦点在树中加上环境（最多父母，下至儿童），让你的整个树的形式，其中它很容易修改的焦点，很容易将焦点上下。

Answer 2

这是一个非常不错的文章说明 使用拉链的切片窗口管理在Haskell.维基百科的文章不是一个很好的参考。

在短短的，拉链是指或处理一个特定的节点在一棵树上，或者列出的结构。拉链给人一种自然的方式把树形结构，并把它作为虽然树是"捡到"由侧重点--实际上，你会得到第二的树，而不需要额外副本的原树或影响的其他使用者树。

给出的实例展示了如何你们的窗户最初是按在屏幕上的位置，然后模型重点使用拉链指向的重点放的窗口。你会得到一个漂亮的一套O(1)操作，例如插入和删除，而无需特殊情况的重点窗户或编写额外的代码。

Answer 3

了解您一个Haskell也有一个伟大的篇章约拉链的。

Answer 4

本文有关Haskell的，但它也解释了拉链相当不错，并它应易于从抽象Haskell的-细节。