平衡二叉树 (AVL)

发布于 2024-07-05 08:18:42 字数 122 浏览 12 评论 0原文

好吧，这对周围的 CS 人员来说是理论领域的又一题。

在 90 年代，我在实施 BST 方面做得相当好。我唯一无法理解的是平衡二叉树（AVL）算法的复杂性。

你们能帮我解决这个问题吗？

原文

分享到QQ

分享到微博

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

发布评论

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

我不咬妳我踢妳 2024-07-12 08:18:43

替罪羊树可能具有最容易理解的平衡确定算法。如果任何插入导致新节点太深，它会通过查看重量平衡而不是高度平衡来找到要重新平衡的节点。删除时是否重新平衡的规则也很简单。它不在节点中存储任何神秘信息。证明它是正确的比较棘手，但你不需要它来理解算法......

但是，与 AVL 不同的是，它并不总是高度平衡的。与红黑一样，它的不平衡是有限的，但与红黑不同的是，它可以通过参数进行调整，因此对于大多数实际用途，它看起来就像您需要的那样平衡。不过，我怀疑如果你把它调整得太紧，对于最坏情况的插入来说，它最终会和 AVL 一样糟糕，甚至更糟。

对问题编辑的回应

我将提供我个人理解 AVL 树的路径。

首先，您必须了解什么是树旋转，因此请忽略您听说过 AVL 算法的所有其他内容并理解它。弄清楚哪个是右旋转，哪个是左旋转，以及每种旋转对树的作用，否则精确方法的描述只会让您感到困惑。

接下来，了解平衡AVL树的技巧是每个节点在其中记录其左右子树的高度差。 “高度平衡”的定义是，对于树中的每个节点，该高度介于 -1 和 1 之间（包括 -1 和 1）。

接下来，请了解如果添加或删除节点，则可能会使树不平衡。但是您只能更改作为您添加或删除的节点的祖先的节点的平衡。因此，您要做的就是恢复树，使用旋转来平衡您发现的任何不平衡节点，并更新它们的平衡分数，直到树再次平衡。

理解它的最后一部分是在一个像样的参考中查找用于重新平衡您找到的每个节点的特定旋转：这是它的“技术”，而不是高概念。您只需要在修改 AVL 树代码时或者在数据结构考试期间记住细节即可。距离我上次在调试器中打开 AVL 树代码已经有很多年了——实现往往会达到可以工作的程度，然后继续工作。所以我真的不记得了。您可以在桌子上使用一些扑克筹码来解决这个问题，但很难确定您是否真的掌握了所有情况（数量不多）。最好只是查一下。

然后就是将其全部翻译成代码。

我认为查看代码清单对除最后一个阶段之外的任何阶段都没有太大帮助，因此请忽略它们。即使在最好的情况下，代码写得很清楚，它看起来也像教科书上描述的过程，但没有图表。在更典型的情况下，这是一团混乱的 C 结构操作。所以只要坚持看书就可以了。

A scapegoat tree possibly has the simplest balance-determination algorithm to understand. If any insertion causes the new node to be too deep, it finds a node around which to rebalance, by looking at weight balance rather than height balance. The rule for whether to rebalance on delete is also simple. It doesn't store any arcane information in the nodes. It's trickier to prove that it's correct, but you don't need that to understand the algorithm...

However, unlike an AVL it isn't height-balanced at all times. Like red-black its unbalance is bounded, but unlike red-black it's tunable with a parameter, so for most practical purposes it looks as balanced as you need it to be. I suspect that if you tune it too tightly, though, it ends up as bad or worse than AVL for worst-case insertions.

Response to question edit

I'll provide my personal path to understanding AVL trees.

First you have to understand what a tree rotation is, so ignore everything else you've ever heard the AVL algorithms and understand that. Get straight in your head which is a right rotation and which is a left rotation, and what each does to the tree, or else the descriptions of the precise methods will just confuse you.

Next, understand that the trick for balancing AVL trees is that each node records in it the difference between the height of its left and right subtrees. The definition of 'height balanced' is that this is between -1 and 1 inclusive for every node in the tree.

Next, understand that if you have added or removed a node, you may have unbalanced the tree. But you can only have changed the balance of nodes which are ancestors of the node you added or removed. So, what you're going to do is work your way back up the tree, using rotations to balance any unbalanced nodes you find, and updating their balance score, until the tree is balanced again.

The final part of understanding it is to look up in a decent reference the specific rotations used to rebalance each node you find: this is the "technique" of it as opposed to the high concept. You only have to remember the details while modifying AVL tree code or maybe during data structures exams. It's years since I last had AVL tree code so much as open in the debugger - implementations tend to get to a point where they work and then stay working. So I really do not remember. You can sort of work it out on a table using a few poker chips, but it's hard to be sure you've really got all the cases (there aren't many). Best just to look it up.

Then there's the business of translating it all into code.

I don't think that looking at code listings helps very much with any stage except the last, so ignore them. Even in the best case, where the code is clearly written, it will look like a textbook description of the process, but without the diagrams. In a more typical case it's a mess of C struct manipulation. So just stick to the books.

回复收藏 0 原文

飘过的浮云 2024-07-12 08:18:43

我最近一直在做一些 AVL 树的工作。

关于如何平衡它们，我能找到的最好帮助是通过搜索谷歌。

我只是围绕这个伪代码进行编码（如果您了解如何进行旋转，那么实现起来非常容易）。

IF tree is right heavy
{
  IF tree's right subtree is left heavy
  {
     Perform Double Left rotation 
  }
  ELSE
  {
     Perform Single Left rotation
  }
}
ELSE IF tree is left heavy
{
  IF tree's left subtree is right heavy
  {
     Perform Double Right rotation
  }
  ELSE
  {
     Perform Single Right rotation
  }
}

I've been doing some work with AVL trees lately.

The best help I was able to find on how to balance them was through searching google.

I just coded around this pseudo code (if you understand how to do rotations it is pretty easy to implement).

IF tree is right heavy
{
  IF tree's right subtree is left heavy
  {
     Perform Double Left rotation 
  }
  ELSE
  {
     Perform Single Left rotation
  }
}
ELSE IF tree is left heavy
{
  IF tree's left subtree is right heavy
  {
     Perform Double Right rotation
  }
  ELSE
  {
     Perform Single Right rotation
  }
}

回复收藏 0 原文