5

到目前为止，我一直在制定一个攻击计划，看看我如何才能做到这一点，这就是我所拥有的：

bool isEmpty() const- 如果为空，则返回 true，否则返回 false

int getSize()- 返回字典中存储了多少单词

void insert (String word)- 如果不存在，则将单词插入字典，否则更新。

boolfind(String word, WordNode & x)- 如果单词存在，则返回 true，并将数据放入 x。

void printSorted()- 按字典顺序（指定）打印树中的单词

void remove (String word)-实现节点的延迟删除

我有我想做什么的概念，并且我了解 AVL 树的工作原理。但是在实际编写代码时我完全卡住了，有人可以帮我开始吗？

4

1 回答 1

2

首先实现一个简单的二叉树（即没有平衡），以及相应的程序来计算文件中的单词。让它工作，所以你会有一些东西可以测试。暂时不要担心平衡；那是真正困难的部分。

这是一个简单二叉树的插入函数（未经测试）：

/*
 * Insert a new key into a binary tree, or find an existing one.
 *
 * Return the new or existing node whose key is equal to the one requested.
 * Update *node with the new (sub)tree root.
 */
Node *insert(Node **node, String key)
{
    if (*node == NULL) {
        *node = new Node(key);
        return *node;
    }

    if (key < (*node)->key)
        return insert(&(*node)->left, key);

    if (key > (*node)->key)
        return insert(&(*node)->right, key);

    return *node;
}

一旦你有一个简单的二叉树工作和测试，重新实现插入函数来执行平衡，这是 AVL 算法的核心。

首先了解 AVL 树的不变量：

  • 任何节点的平衡因子（左孩子的身高和右孩子的身高之差）要么是-1，要么是0，要么是+1。
  • 中序遍历产生字典顺序。

推荐参考维基百科上的AVL树插入图。它说明了您需要实施的四个轮换以及需要它们的位置。

当节点的平衡因子超出范围时，需要进行旋转——换句话说，当左子树和右子树之间的高度差大于 1 时。

如何确定节点的平衡因子？好吧，以下任何一项都可以：

  1. 将height成员添加到 Node 结构，并通过从左孩子的高度减去右孩子的高度来确定任何给定节点的平衡因子。
  2. 将balance成员添加到节点结构。这可能有点难以弄清楚，但它会产生更简单的代码（我认为）。
  3. 通过遍历计算树的高度和平衡。这是低效的，以至于它违背了 AVL 的目的。但是，它更容易理解并且不易出错。

我建议从第三种方法开始，这样您就可以更快地测试您的平衡代码。

为了阐明“高度”和“平衡因子”的含义，以下是计算它们的函数：

int height(Node *node)
{
    if (node == NULL)
        return -1;
    return std::max(height(node->left), height(node->right)) + 1;
}

int balanceFactor(Node *node)
{
    assert(node != NULL);
    return height(node->right) - height(node->left);
}

弄清楚如何逐步更新高度或平衡因素将涉及纸张、铅笔、简单的代数和常识。

我希望这有帮助！

于 2011-07-24T21:47:22.340 回答