0

所以我使用参数化列表实现了一个二叉搜索树，即

List<Node> tree = new List<>();

树工作正常。节点本身对它的父节点或子节点一无所知。这是因为我根据索引计算位置，例如

                         If i is the index of some None N then:
                                N's left child is in tree[i*2] 
                                N's right child is in tree[(i*2)+1]

这棵二叉树工作正常。但现在我想把 AVL 树的特性放到它上面。我被困在这一点上，因为我不知道如何在列表上进行轮换。在旋转时，我如何移动新根的孩子？事实上，他们必须改变索引，不是吗？在列表上执行此操作也会给我一个问题，即每次添加节点时显示树都需要循环遍历列表。这不会在 O(logn) 中发生，因为它会破坏 AVL 树的整个点。

我在 C# 中这样做。我只想知道如何使用列表或任何基于数组的可索引数据结构而不是链接列表有效地制作此 AVL 树。这很重要。一些代码来说明将不胜感激。

4

3 回答 3

3

以您正在执行的方式在数组/列表中表示树对于堆数据结构来说很常见，但它实际上不适用于任何其他类型的树。特别是，您不能（有效地）对 AVL 树执行此操作，因为每次旋转都需要过多的复制。

于 2013-05-07T11:15:51.770 回答
0

对于没有可用 malloc 的嵌入式应用程序，我需要这个。在我尝试是否可以完成之前，还没有完成任何类型的数据结构算法实现。在编写代码时，我意识到我必须移动很多东西。我寻找补救措施并找到了这篇文章。

感谢 Chris 的回复，我不会再花时间在上面了。我会找到其他方法来实现我所需要的。

于 2013-05-30T16:54:23.603 回答
0

我相信我找到了答案，诀窍是在列表中上下移动子树，这样您就不会在旋转时覆盖有效节点。

void shiftUp(int indx, int towards) {
    if (indx >= size || nodes[indx].key == NULL) {
        return;
    }
    nodes[towards] = nodes[indx];
    nodes[indx].key = NULL;
    shiftUp(lChild(indx), lChild(towards));
    shiftUp(rChild(indx), rChild(towards));
}

void shiftDown(int indx, int towards) {
    if (indx >= size || nodes[indx].key == NULL) {
        return;
    }

    // increase size so we can finish shifting down
    while (towards >= size) { // while in the case we don't make it big enough
        enlarge();
    }

    shiftDown(lChild(indx), lChild(towards));
    shiftDown(rChild(indx), rChild(towards));
    nodes[towards] = nodes[indx];
    nodes[indx].key = NULL;
}

正如您所看到的，这是通过递归地探索每个子树直到 NULL（在此定义为 -1）节点然后一个接一个地向上或向下复制每个元素来完成的。

有了这个，我们可以定义根据这个维基百科 Tree_Rebalancing.gif命名的 4 种旋转类型

void rotateRight(int rootIndx) {
    int pivotIndx = lChild(rootIndx);

    // shift the roots right subtree down to the right
    shiftDown(rChild(rootIndx), rChild(rChild(rootIndx)));
    nodes[rChild(rootIndx)] = nodes[rootIndx]; // move root too

    // move the pivots right child to the roots right child's left child
    shiftDown(rChild(pivotIndx), lChild(rChild(rootIndx)));

    // move the pivot up to the root
    shiftUp(pivotIndx, rootIndx);

    // adjust balances of nodes in their new positions
    nodes[rootIndx].balance--; // old pivot
    nodes[rChild(rootIndx)].balance = (short)(-nodes[rootIndx].balance); // old root
}

void rotateLeft(int rootIndx) {
    int pivotIndx = rChild(rootIndx);

    // Shift the roots left subtree down to the left
    shiftDown(lChild(rootIndx), lChild(lChild(rootIndx)));
    nodes[lChild(rootIndx)] = nodes[rootIndx]; // move root too

    // move the pivots left child to the roots left child's right child
    shiftDown(lChild(pivotIndx), rChild(lChild(rootIndx)));

    // move the pivot up to the root
    shiftUp(pivotIndx, rootIndx);

    // adjust balances of nodes in their new positions
    nodes[rootIndx].balance++; // old pivot
    nodes[lChild(rootIndx)].balance = (short)(-nodes[rootIndx].balance); // old root
}


// Where rootIndx is the highest point in the rotating tree
// not the root of the first Left rotation
void rotateLeftRight(int rootIndx) {
    int newRootIndx = rChild(lChild(rootIndx));

    // shift the root's right subtree down to the right
    shiftDown(rChild(rootIndx), rChild(rChild(rootIndx)));
    nodes[rChild(rootIndx)] = nodes[rootIndx];

    // move the new roots right child to the roots right child's left child
    shiftUp(rChild(newRootIndx), lChild(rChild(rootIndx)));

    // move the new root node into the root node
    nodes[rootIndx] = nodes[newRootIndx];
    nodes[newRootIndx].key = NULL;

    // shift up to where the new root was, it's left child
    shiftUp(lChild(newRootIndx), newRootIndx);

    // adjust balances of nodes in their new positions
    if (nodes[rootIndx].balance == -1) { // new root
        nodes[rChild(rootIndx)].balance = 0; // old root
        nodes[lChild(rootIndx)].balance = 1; // left from old root
    } else if (nodes[rootIndx].balance == 0) {
        nodes[rChild(rootIndx)].balance = 0;
        nodes[lChild(rootIndx)].balance = 0;
    } else {
        nodes[rChild(rootIndx)].balance = -1;
        nodes[lChild(rootIndx)].balance = 0;
    }

    nodes[rootIndx].balance = 0;
}

// Where rootIndx is the highest point in the rotating tree
// not the root of the first Left rotation
void rotateRightLeft(int rootIndx) {
    int newRootIndx = lChild(rChild(rootIndx));

    // shift the root's left subtree down to the left
    shiftDown(lChild(rootIndx), lChild(lChild(rootIndx)));
    nodes[lChild(rootIndx)] = nodes[rootIndx];

    // move the new roots left child to the roots left child's right child
    shiftUp(lChild(newRootIndx), rChild(lChild(rootIndx)));

    // move the new root node into the root node
    nodes[rootIndx] = nodes[newRootIndx];
    nodes[newRootIndx].key = NULL;

    // shift up to where the new root was it's right child
    shiftUp(rChild(newRootIndx), newRootIndx);

    // adjust balances of nodes in their new positions
    if (nodes[rootIndx].balance == 1) { // new root
        nodes[lChild(rootIndx)].balance = 0; // old root
        nodes[rChild(rootIndx)].balance = -1; // right from old root
    } else if (nodes[rootIndx].balance == 0) {
        nodes[lChild(rootIndx)].balance = 0;
        nodes[rChild(rootIndx)].balance = 0;
    } else {
        nodes[lChild(rootIndx)].balance = 1;
        nodes[rChild(rootIndx)].balance = 0;
    }

    nodes[rootIndx].balance = 0;
}

请注意，在移位会覆盖节点的情况下，我们只需复制单个节点

至于在每个节点中存储余额的效率是必须的，因为在每个节点处获取高度差异将非常昂贵

int getHeight(int indx) {
    if (indx >= size || nodes[indx].key == NULL) {
        return 0;
    } else {
        return max(getHeight(lChild(indx)) + 1, getHeight(rChild(indx)) + 1);
    }
}

尽管这样做需要我们在修改列表时更新受影响节点的余额，但通过仅更新严格必要的情况，这可能会有些效率。对于删除，此调整是

// requires non null node index and a balance factor baised off whitch child of it's parent it is or 0
private void deleteNode(int i, short balance) {
    int lChildIndx = lChild(i);
    int rChildIndx = rChild(i);

    count--;
    if (nodes[lChildIndx].key == NULL) {
        if (nodes[rChildIndx].key == NULL) {

            // root or leaf
            nodes[i].key = NULL;
            if (i != 0) {
                deleteBalance(parent(i), balance);
            }
        } else {
            shiftUp(rChildIndx, i);
            deleteBalance(i, 0);
        }
    } else if (nodes[rChildIndx].key == NULL) {
        shiftUp(lChildIndx, i);
        deleteBalance(i, 0);
    } else {
        int successorIndx = rChildIndx;

        // replace node with smallest child in the right subtree
        if (nodes[lChild(successorIndx)].key == NULL) {
            nodes[successorIndx].balance = nodes[i].balance;
            shiftUp(successorIndx, i);
            deleteBalance(successorIndx, 1);
        } else {
            int tempLeft;
            while ((tempLeft = lChild(successorIndx)) != NULL) {
                successorIndx = tempLeft;
            }
            nodes[successorIndx].balance = nodes[i].balance;
            nodes[i] = nodes[successorIndx];
            shiftUp(rChild(successorIndx), successorIndx);
            deleteBalance(parent(successorIndx), -1);
        }
    }
}

同样对于插入这是

void insertBalance(int pviotIndx, short balance) {
    while (pviotIndx != NULL) {
        balance = (nodes[pviotIndx].balance += balance);

        if (balance == 0) {
            return;
        } else if (balance == 2) {
            if (nodes[lChild(pviotIndx)].balance == 1) {
                rotateRight(pviotIndx);
            } else {
                rotateLeftRight(pviotIndx);
            }
            return;
        } else if (balance == -2) {
            if (nodes[rChild(pviotIndx)].balance == -1) {
                rotateLeft(pviotIndx);
            } else {
                rotateRightLeft(pviotIndx);
            }
            return;
        }

        int p = parent(pviotIndx);

        if (p != NULL) {
            balance = lChild(p) == pviotIndx ? (short)1 : (short)-1;
        }

        pviotIndx = p;
    }
}

正如你所看到的，这只是使用“节点”的普通数组，因为我从给定gitHub array-avl-tree和优化和平衡的 c 代码翻译它（我将在评论中发布的链接）但在一个列表

最后，我对 AVL 树或最佳实现知之甚少，所以我不声称这是没有错误或最有效的，但至少出于我的目的已经通过了我的初步测试

于 2016-05-15T13:25:17.963 回答