代码之家 › 专栏 › 技术社区 › Maestro1024

在AVL树上设置父级

avl-tree computer-science

0

Maestro1024 · 技术社区 · 14 年前

我正在尝试实现一个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);
    }
}

-

2 回复 | 直到 14 年前

1

deinst 14 年前

既然你这样做是为了教育,我建议你手工制作一些案例,然后把它们编码成表格的测试

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

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

这些数字完全是编造出来的。

这将

给你的不仅仅是你的代码是否工作的感觉(提示:如果您不确定您的代码是否正常工作,则可能不是)
给你一个地方开始找出哪里出了问题。
养成测试的习惯。对某些人来说,编写两倍的代码(测试+代码)比一开始就编写代码要快,这是违反直觉的,但是请尝试一下。加上写更多的代码=更多的实践。

2

0

Ishtar 14 年前

树和节点有什么区别(树只是根节点的占位符,仅此而已。一个节点有时被称为有两个子树。树和节点没有区别。一节课就够了。)

节点不应该知道它的父节点(在我看来)。因此insert函数需要一个父参数。创建新节点后,比较父节点和子节点的深度,看看是否需要进行任何旋转。编程的旋转是棘手的:尝试,调试和测试!

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