如何在没有父指针的情况下实现AVL树？

Question

我看到一些关于AVL的rebalance()函数实现的文章.每次插入后,我们应检查插入节点的祖先是否有平衡.所以我认为,为了检查祖先的平衡,我必须知道插入节点的父节点.

但是,我想知道有没有其他方法可以做到这一点,而不必使用父指针？例如,节点结构:

struct Node{
int data;
struct Node *lchit, *rchild; //*parent;
};

Answer 1

如果我没记错我的数据结构作业：

\n\n

您要做的是将平衡因子作为 int 存储在节点本身中，即：

\n\n

\n\n

insert(Node subtree) 函数返回一个布尔值，如果插入使子树的高度增加，则该值为 true。当您从递归 insert() 调用返回时，您可以更新平衡因子并重新平衡树。

\n\n

这可能可以用几个例子来最好地解释：

\n\n

如果当前节点处于平衡因子-1，您将插入到右子树中，并且 insert(rchild) 返回true，您：

\n\n

\n\n

如果要插入任一子树，并且 insert(\xe2\x80\xa6) 返回false：

\n\n

\n\n

如果当前节点的平衡因子为0，则插入到左子树中，并且 insert(lchild) 返回true：

\n\n

\n\n

（类似地，如果插入到右子树，平衡因子将变为1。）

\n\n

如果当前节点的平衡因子为-1，则插入到左子树中，并且 insert(lchild) 返回true：

\n\n

平衡因子将更改为 -2，这意味着您必须通过进行适当的旋转来重新平衡节点。我承认我对四次旋转中的每一次对平衡因子的影响以及插入（当前）将返回的内容一无所知，希望前面的示例充分解释了跟踪节点平衡的方法。

\n

Answer 2

您可以在遍历树时维护当前节点的堆栈

stack<Node*> nodeStack;

当你遍历到一个新节点时，将其添加到堆栈中，然后你就有了你的祖先。当处理完一个节点后，将其从堆栈中弹出。

** 编辑 **

对齐注释的详细说明：

struct Node {
    int data;
    struct Node *children, *parent
};

创建孩子时，这样做：

node.children = new Node[2]; or node.children = malloc(sizeof(Node) * 2);
node.children[0].parent = node;
node.children[1].parent = node;

@Alcott：另一种方法是仅使用递归沿着树向下走，那里的堆栈是隐式的（函数帧堆栈），并且“Node”可以保留为函数局部变量的一部分或函数参数。 (3认同)
关于使用单个新的优化 - 这是行不通的，因为现在没有办法正确释放内存。重新平衡后，右子节点可能是另一个节点的左子节点，并且调用“delete[] another_node.children”可能会导致段错误。PS 我知道这个帖子已经有 6 年历史了 :P (2认同)