0

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

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

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);
    }
}

-

4

2 回答 2

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. 养成测试的习惯。对于某些人来说，编写两倍的代码（测试 + 代码）比一开始编写代码要快，这是违反直觉的，但请尝试一下。加上编写更多代码 = 更多练习。
于 2010-08-06T00:23:55.273 回答
0

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

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

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

Node::insert(int number,Node * parent)
{
  //code
  left=new node(number);
  if (parent->left->depth() > parent->right->depth()+1)
    parent->rotate_tree_or_something();
  //
}
于 2010-08-06T00:28:53.250 回答