排序列表中的多个 AVL 树?

发布于 2024-12-12 10:11:32 字数 178 浏览 1 评论 0原文

我正在研究 AVL 树分配,我对它们的定义有一个简单的问题 - 我们给出了一个排序列表,我们必须在 O(n) 时间内从它生成一个 AVL 树。我已经完成了这个(感谢 StackOverflow 的其他帮助!),但我的结果虽然是有效的 AVL 树,但与提供的示例的结果不同。是否可以从同一个排序列表生成多个 AVL 树?

谢谢!

I'm working on an AVL tree assignment and I have a quick question about their definition - we're given a sorted list, and we have to generate an AVL tree from it in O(n) time. I've completed this (thanks to other help from StackOverflow!), but my result, while a valid AVL tree, is different from the result of the example provided. Are multiple AVL trees able to be generated from the same sorted list?

Thanks!

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

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

发布评论

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

评论(2

一袭白衣梦中忆 2024-12-19 10:11:32

是的。考虑只有两个节点的树的退化情况。在这种情况下,任一节点可以是根,另一个节点可以是叶。就整体平衡而言,两者是相当的。

在此处输入图像描述

Yes. Consider the degenerate case of a tree with only two nodes. In this case, either node can be the root, and the other will be a leaf. The two are equivalent as far as overall balance goes.

enter image description here

深爱成瘾 2024-12-19 10:11:32

是的,例如,<1,2,3,4,5>有两个可能的 AVL 树:

(2 1 (3 4 5))

(4 (2 1 3) 5)

,其中 (a T1 T2)表示一棵树,根为a,左树T1,左树T2。

Yes, for instance, these are two possible AVL trees for <1,2,3,4,5>:

(2 1 (3 4 5))

and

(4 (2 1 3) 5)

where (a T1 T2) denotes a tree with root a, left tree T1 and left right T2.

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