使用列表实现AVL树
本文关键字：AVL 实现 列表 | 更新日期: 2023-09-27 18:12:29
所以我已经实现了一个使用参数化列表的二叉搜索树，即
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树的特征加进去。我在这一点上卡住了，因为我不知道如何在列表上进行旋转。在旋转时，我如何移动新根结点的子结点?事实是它们必须改变指标，不是吗?在List上这样做也给我带来了一个问题，即每次添加节点时，显示树将需要循环遍历List。这种情况不会在O(logn)内发生，破坏AVL树的整个点。
我在c#中做这个。我只是想知道如何使这个AVL树有效地使用列表或任何基于数组的数据结构是可索引的，而不是链表。这很重要。如果能提供一些代码来说明的话，我将不胜感激。
在数组/列表中表示树的方式对于堆数据结构是常见的，但它实际上不适用于任何其他类型的树。特别是，对于AVL树，您不能(有效地)这样做，因为每次旋转都需要太多的复制。
我在一个没有malloc可用的嵌入式应用程序中需要这个。我没有做过任何类型的数据结构算法实现之前，我试图如果它可以做到。在编写代码时，我意识到我必须移动很多东西。我寻找了一个补救措施，并得到了这篇文章。
感谢Chris的回复，我不会再花时间在这上面了。我会找到其他方法来实现我所需要的。
我相信我找到了答案，诀窍是在列表中上下移动子树，以便在旋转时不会覆盖有效节点。
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_rebalance .gif
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;
}
}
正如你所看到的，这只是使用了普通的"节点"数组，因为我从c代码中翻译了它，给出了gitHub数组-avl-tree和优化和平衡(我将在评论中发布一个链接)，但在列表中工作非常相似
最后，我对AVL树或最佳实现有最小的了解，所以我不声称这是无bug或最有效的，但至少对于我的目的，已经通过了我的初步测试