数据挖掘 数据增强

增强数据结构 (Augmenting Data Structure)

Augmenting data structure means adding some extra information to the existing data structure so that the data structure can be implemented efficiently. Typically any node of a tree contains some useful information such as a left pointer, right pointer, data, parent node, the color of the node. This information is useful for accessing particular node more efficiently from the given tree. For each node k, add a new field size(k) now with this size information there can be fast computing access of dynamic order statics and rank of a particular node will be determined. In this position of a node is in linear order. Let us see know how this augmentation helps us to use the .

增强数据结构意味着向现有数据结构中添加一些额外的信息，以便可以有效地实现该数据结构 。 通常，树的任何节点都包含一些有用的信息，例如左指针，右指针，数据，父节点，节点的颜色。 此信息对于从给定树更有效地访问特定节点很有用。 对于每个节点k，现在添加一个新的字段大小(k)，并使用该大小信息，可以快速计算动态顺序静态变量的访问量，并确定特定节点的等级。 在此位置，节点呈线性顺序。 让我们知道这种增强如何帮助我们使用 。

动态订单静态 (Dynamic order statics)

For augmenting the data structure we will simply store, extra information of size. The augmented tree is also called as order static tree. Hence every node of order static tree has following features which are as follows:

为了扩展数据结构，我们将简单地存储额外的大小信息。 扩充树也称为顺序静态树。 因此，顺序静态树的每个节点都具有以下特征：

1. Address of parent node

   父节点地址

2. Address of left child

   遗失子女的地址

3. Address of right child

   合适子女的地址

4. Color

   颜色

5. Key value

   核心价值

6. Size of a particular node

   特定节点的大小

Representation of order static tree

订单静态树的表示

In the above-given tree, the Red Black Tree is augmented because in this we have computed the size of each node and storing the information about size in each node.

在上面给出的树中，红黑树得到了增强，因为在这种情况下，我们已经计算了每个节点的大小，并在每个节点中存储了有关大小的信息。

Consider that if we need to compute the size of node k then:

考虑一下，如果我们需要计算节点k的大小，则：

size[k] = size[left node[k]] +size[right node[k]]+1

Consider the leaf node 22 which has no left child and right child hence:

考虑没有左孩子和右孩子的叶子节点22，因此：

size[22] =size[left[22]]+size[right[22]]+1    size[22] =0+0+1=1

扩充策略 (Augmentation strategy)

Following are the steps which are needs to be followed when we want to augment a data structure.

以下是我们要扩充数据结构时需要遵循的步骤。

1. Firstly choose a data structure which has to be augmented.

   首先选择必须扩充的数据结构。

2. Then find out the additional information which is needed to be added and which also support the algorithm.

   然后找出需要添加的附加信息，这些附加信息也支持该算法。

3. Then it is verified whether the operation of Red Black tree will work with this additional information or not.

   然后，验证“红黑树”的操作是否可以使用此附加信息。

4. The information which is required by Red Black tree is chosen for developing new operations.

   选择红黑树所需的信息来开发新的操作。

5. Size and rank are the two types of additional information which are required to enhance the performance of a basic data structure.

   大小和等级是增强基本数据结构性能所需的两种附加信息。

确定节点的等级 (Determining, Rank of the node)

Rank of the particular node in the order static tree indicates the position of that node in the inorder sequence. For determining the position of a particular node the following algorithm is prescribed below:

顺序静态树中特定节点的等级指示该节点在顺序序列中的位置。 为了确定特定节点的位置，下面规定了以下算法：

Algorithm Determining the rank(root, k){	//input: root denotes the root node of the tree and k 	//denotes the node whose rank is to be determined.	//output: rank of k node.	rank ← size [left[k]] +1	temp ← k	While (temp! =root)	{		If (temp=right[parent[temp]])then			rank  ← rank +size [left[parent[temp]]]+1		temp ← k[temp]	}	return rank}

By this algorithm, we can derive a rank for a particular node for a given order static tree.

通过这种算法，我们可以得出给定阶数静态树的特定节点的等级。

翻译自:

数据挖掘 数据增强