c++ - 我将如何平衡退化的树？C++ 数据结构

Question

我目前正在使用 C++ 学习数据结构。我了解在插入新节点时如何平衡二叉搜索树。

但是，如果您已经有一个退化的树（单个链接列表），并且想要在不创建新树的情况下平衡它怎么办？总之，我将如何使用现有节点将退化树重新组装成完整的树？（使用旋转方法）

例如，我的节点保存（9 个节点）的数据：1、3、6、9、12、15、18、21、24

我需要一个推动开始。我不知道从哪里开始。感谢您的帮助。

Answer 1

退化树只是一个排序的链表。找到列表的中间元素，去掉中间之前的列表开头，附加到中间元素的左边。现在你有中间元素作为根，每边有两个退化树（链表）。对每一侧递归地重复此过程。