AVL树字典

发布于 2024-11-26 07:57:42 字数 505 浏览 1 评论 0原文

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

bool isEmpty() const - 如果为空则返回 true,如果不是则返回 false

< code>int getSize() - 返回字典中存储的单词数

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

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

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

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

我有这样的概念我想做什么,并且我了解 AVL 树是如何工作的。但在实际编写代码时我完全陷入困境,有人可以帮助我开始吗?

So far I've been drawing up a plan of attack to see how I could go about doing this and this is what I have:

bool isEmpty() const - returns true if empty, false if not

int getSize() - returns how many words are stored in the dictionary

void insert (String word) -insert word into dictionary if not already present, else update.

boolfind(String word, WordNode & x) - returns true if the word is present and place data in x.

void printSorted() - prints the words in the tree in lexicographic order (specified)

void remove (String word) -implements the lazy deletion of a node

I have the concept of what I want to do down, and I understand how AVL trees work. But I get completely stuck when it comes to actually writing the code, can anyone help me get started?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

沩ん囻菔务 2024-12-03 07:57:42

首先实现一个简单的二叉树(即,没有平衡),以及相应的程序来计算文件中的单词数。让它工作起来,这样你就有了可以测试的东西。现在先不要担心平衡问题;这是真正困难的部分。

这是一个简单二叉树的插入函数(未经测试):

/*
 * 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 成员添加到 Node 结构中。这可能有点难以弄清楚,但它会产生更简单的代码(我认为)。
  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);
}

弄清楚如何增量更新高度或平衡系数将涉及纸、铅笔、简单的代数和常识。

我希望这有帮助!

Start by implementing a simple binary tree (that is, without balancing), along with the corresponding program to count words in a file. Get that working, so you'll have something to test with. Don't worry about balancing just yet; that's the really hard part.

Here's an insertion function (untested) for a simple binary tree:

/*
 * 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;
}

Once you have a simple binary tree working and tested, re-implement the insertion function to perform balancing, which is the heart of the AVL algorithm.

Start by knowing the invariants of an AVL tree:

  • The balance factor of any node (the difference between the left child's height and the right child's height) is either -1, 0, or +1.
  • In-order traversal produces a dictionary order.

I recommend referring to the AVL tree insertion diagram on Wikipedia. It illustrates the four rotations you will need to implement and where they are needed.

A rotation is necessary when the balance factor of a node goes out of range—in other words, when the difference in height between the left subtree and right subtree is greater than 1.

How do you determine the balance factor of a node? Well, any of the following will work:

  1. Add a height member to the Node structure, and determine the balance factor of any given node by subtracting the right child's height from the left child's height.
  2. Add a balance member to the Node structure. This might be a little harder to figure out, but it yields simpler code (I think).
  3. Compute tree heights and balances by traversal. This is inefficient, so much so that it defeats the purpose of AVL. However, it's easier to understand and less bug-prone.

I recommend starting with the 3rd approach, so you can test your balancing code sooner.

To clarify what is meant by "height" and "balance factor", here are functions to compute them:

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

Figuring out how to update heights or balance factors incrementally is going to involve paper, pencil, simple algebra, and common sense.

I hope this helps!

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文