在 AVL 树上设置父级

Question

我正在尝试实现 AVL 树，但不确定插入和跟踪每个节点的父节点的最佳方法。这是有教育意义的，所以请不要建议“使用 boost”:)

这可以编译，但我不相信它的正确性或它是最好的方法。 具体来说

insert(someNumber,root,root);

，当我重新平衡并向上移动树时，我将重做高度部分。

我这样插入

myTree.insert(someNumber);

这是方法。我不确定我的第二个参数应该在这里。我本以为 NULL 但编译器不喜欢这样（不同的函数定义）。

void Tree::insert(int someNumber){
    insert(someNumber,root,root);
}

这是我的插入内容

void Tree::insert(int someNumber,Node*& subTreeRoot,Node*& parent){
    if(subTreeRoot==NULL)
    {
        subTreeRoot = new Node(someNumber,parent);
        if(subTreeRoot->myParent)   
    }
    else if (someNumber<subTreeRoot->myNumber)
    {
        if((subTreeRoot->right==NULL)||((subTreeRoot->left!=NULL)&&(subTreeRoot->right!=NULL)))
            subTreeRoot->height++;
        insert(someNumber,subTreeRoot->left,subTreeRoot);
    }
    else
    {
        if((subTreeRoot->left==NULL)||((subTreeRoot->left!=NULL)&&(subTreeRoot->right!=NULL)))
            subTreeRoot->height++;
        insert(someNumber,subTreeRoot->right,subTreeRoot);
    }
}

-

Answer 1

由于您这样做是为了教育，我建议您手动解决一些案例，然后将它们编码为

 Insert(6);
 Insert(11);
 // ...
 Insert(3);

 Node test = root;
 assert(root->height == 3);
 assert(root->value == 6);
 test = root->right;
 assert( ... );

完全由数字组成的形式的测试。

这将给

1. 您带来更多关于您的代码是否正常工作的感觉。 （提示：如果您不确定您的代码是否正常工作，那么它可能无法正常工作）
2. 为您提供一个开始找出问题所在的地方。
3. 养成测试的习惯。对于某些人来说，编写两倍的代码（测试+代码）比一开始就编写代码要快，这是违反直觉的，但请尝试一下。加上编写更多代码=更多练习。

Answer 2

树和节点有什么区别？ （树只是根节点的占位符，仅此而已。有时说一个节点有两个子树。树和节点没有什么不同。一个类就足够了。）

为什么不只在需要时计算高度？更容易编程和证明正确性。如果性能对您造成影响，您可以随时更改该函数以返回缓存的值。

节点不应该知道它的父节点（在我看来）。所以插入函数需要一个父参数。创建新节点后，比较父子节点的深度，看看是否需要进行任何旋转。对旋转进行编程很棘手：尝试、调试和测试！

Node::insert(int number,Node * parent)
{
  //code
  left=new node(number);
  if (parent->left->depth() > parent->right->depth()+1)
    parent->rotate_tree_or_something();
  //
}