什么是拉链数据结构，我应该使用它？ [英] What is the Zipper data structure and should I be using it?

问题描述

问题很简单：我无法理解拉链数据结构。

我的问题与使用Tree有关。

我想了解如何更改树节点使用拉链。而且如何复制整棵树（或其中大部分）。

请澄清拉链是否错误。也许它不能帮助树更新？

或者也许，可以更新树，我只是看不到方式？

（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））。

拉链是应用于树的一样想法。你在树上加上一个重点，加上一个上下文（直到父母，直到孩子），这样可以让你整个树的形状在焦点上很容易被修改，并且很容易上下移动焦点。

The question is simple: I cannot understand the Zipper data structure.

My question is related to its uses with a Tree.

I want to understand how can I change the tree node using zipper. And how not to copy the whole tree (or the most part of it).

Please, clarify if I'm wrong with zipper. Maybe it cannot help with the tree update?
Or, maybe, it is possible to update the tree and I just cannot see the way?

解决方案

Let's start with the Zipper-analog for lists. If you'd like to modify the nth element of a list, it takes O(n) because you have to copy the n-1 first elements. Instead, you can keep the list as a structure ((first n-1 elements reversed) nth element (remaining elements)). For example, the list (1 2 3 4 5 6) modifiable at 3 would be represented as ((2 1) 3 (4 5 6)). Now, you can easily change the 3 to something else. You can also easily move the focus left ((1) 2 (3 4 5 6)) and right ((3 2 1) 4 (5 6)).

A zipper is the same idea applied to trees. You represent a certain focus in the tree plus a context (up to parents, down to children) which gives you the whole tree in a form where it's easily modifiable at the focus and it's easy to move the focus up and down.

这篇关于什么是拉链数据结构，我应该使用它？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！