[数据结构] 弹性数组

win_hate

在 imperative 风格的编程中，数组是最基本的数据结构。而在函式风格的编程中，列表是最基本的数据结构。这两个结构有一个很本质的区别，对数组中任一元素进行访问，其时间复杂度是 O(1) 的，但在列表中，随机访问一个元素的平均复杂度为 O(n)，n 为列表长度。

这里介绍一种称为弹性数组(flexible array)数据结构，支持随机访问，上下端伸缩，更新元素等。所有的操作都是 O(log n) 的。可以作为数组的一个折衷替代。

win_hate

假如现在有 n 个数，a[1], a[2], ..., a[n]，把下标 k 写成 2 进制，比如 100110.

构造一棵二叉树，a[1] 为根，a[k] 定位方式为，从二进表达低位向高位读，0 向左，1向右，但最高位不要。

看个图就清楚了:



13 = 8+4+1 = 1101

所以 13 的位置为: 从根起，右、左、右.

于是：访问 a[k] 只需要不断把 k 除以 2，根据余数决定方向，直到商为 1 停止。访问时间和更新时间都是 O(log n) 的。

一些性质:

• 容易看出，左右子树对应位置的下标有相同的二进制前缀。比如 12 与 13 对应，它们只有最低一位有差别。
       而在 2 为根的子树中，8 与 10 想相对，8 有后缀 00，而 10 有后缀 10.
  
• 左子树下标都是偶数，除以 2 后，得到一个规模减半的弹性数组;
  
• 右子树下标都是奇数，减 1 除以 2 后，得到一个规模减半的弹性数组。
  

[ 本帖最后由 win_hate 于 2008-11-14 12:05 编辑 ]

win_hate

每次只能伸缩一个元素。用一个额外的变量记录数组大小 n.

• 删除：找到 n 对应元素，把值替换成叶子即可；
  
• 插入：找到相应的叶子，将叶子换成插入值即可。
  
  

win_hate

具有挑战性的是下端伸缩，即把数组中所有元素往右移动一格，以容纳新元素。 imperative  风格的数组一般不支持这个操作。

新插入的元素为根；

原来左子树上全是偶数下标，增加 1 后都成奇数。而且最低位的前缀没变，直接移到右子树上即可。

原来的右子树中某节点下标记为 2k-1，如果右子数直接移动到左边，则下标变为 2k-1-1=2k-2。但下标为 2k 才是正确的。

此时还有一个节点没有插入，这就是原来的根，它的原下标为 1，新下标应该为 2。只要把它插入原右子树，或现在的左子树，即可以把左子数的下标 2k-2 调节为 2k. 这个插入操作的递归的。因为这些下标除以 2 后，得到一个规模较小的弹性数组。

• 新元素为根；
  
• 原左子树移动到右边；
  
• 原来的根插入（递归）原右子树并接在新元素的左边。
  
  

看个图就清楚了：



再插入一个元素：



[ 本帖最后由 win_hate 于 2008-11-14 12:07 编辑 ]

win_hate

在非纯函式语言中使用上述数据结构是很自然的，更新的时候直接把值改掉就行。

如果是纯函式语言，则要指出一点：在纯函式语言中，绑定的值是不能改变的。因此前面的更新，伸缩都会产生一棵"新"树。之所以用引号，是因为新树与旧树共享几乎所有数据，只有更新的部分是不同的。但这不会带来混淆，因为绑定的值是不会改变的。

tfyt1234

删除根元素：

1、原右子树移动到左边
2、删除原左子树根（递归），作为新的根，删除后的左子树移动到右边

1. 
   
2.         F                   E
   
3.      /     \              /   \
   
4.     E       D     ==>    D     C
   
5.    / \     /            /     /
   
6.   C   A   B            B     A
   

复制代码

[ 本帖最后由 tfyt1234 于 2008-11-27 09:45 编辑 ]