首先实现一个简单的二叉树(即没有平衡),以及相应的程序来计算文件中的单词。让它工作,所以你会有一些东西可以测试。暂时不要担心平衡;那是真正困难的部分。
这是一个简单二叉树的插入函数(未经测试):
/*
* 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 时。
如何确定节点的平衡因子?好吧,以下任何一项都可以:
- 将
height
成员添加到 Node 结构,并通过从左孩子的高度减去右孩子的高度来确定任何给定节点的平衡因子。
- 将
balance
成员添加到节点结构。这可能有点难以弄清楚,但它会产生更简单的代码(我认为)。
- 通过遍历计算树的高度和平衡。这是低效的,以至于它违背了 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);
}
弄清楚如何逐步更新高度或平衡因素将涉及纸张、铅笔、简单的代数和常识。
我希望这有帮助!