平衡BST

Question

参考: 我被问到这个问题@MS SDE采访,第3轮.这不是一个家庭作业问题.我也考虑了一下,并在下面提到了我的方法.

问题: 修改BST以使其尽可能平衡.不用说,你应该尽可能高效地做到这一点.

提示: 采访者说这是一个合乎逻辑的问题,如果你有不同的想法,你会得到答案.没有困难的编码.
- >话虽如此,我认为他不指望我指向AVL/RB树.

我的解决方案: 我提出,我会按顺序遍历树,将中间元素作为新树的根(让我们称之为新的根).然后转到中间元素的左侧部分,将其中间元素作为树根新子根的左子树的根.同样适用于正确的部分.递归地执行此操作将提供最佳平衡BST.

我为什么要在这里张贴它: 但他对答案不满意:(那么,有没有办法做这个没有用于权重/ RB着色策略,还是他只是和我一起鬼混？请放入你的专家想法.

重复？没有! 我知道有这个问题但是请求者提出的解决方案太复杂了,而另一个讨论了AVL树.

Answer 1

您可能需要查看Day-Stout-Warren算法,该算法是一种O(n)时间,O(1)空间算法,用于将任意二进制搜索树重新整形为完整的二叉树.直觉上,该算法的工作原理如下:

1. 使用树旋转,将树转换为简并链接列表.
2. 通过将选择性旋转应用于链表,将列表转换回完全平衡的树.

这种算法的优点在于它在线性时间内运行,只需要恒定的内存开销; 事实上,它只是重塑了底层树,而不是创建一个新树并复制旧数据.编码也相对简单.

希望这可以帮助!

Answer 2

"尽可能平衡"= 完整(或完整)二叉树¹.你无法更加平衡它.

解决方案很简单 - 构建一个"空"完整二叉树,并在inorder-traversal中迭代新树和输入树(同时)以填充整个树.

完成后,您可以获得最平衡的树,并且这种方法的时间复杂度是O(n).

编辑:
这应该按照以下步骤完成:

1. 使用n节点构建虚拟完整树.每个节点的所有值都将初始化为一些垃圾值.
2. 创建两个迭代器:(1)originalIter用于原始树,(2)newIter用于new(用垃圾初始化)树.两个迭代器都将按顺序遍历返回元素.

3. 执行以下操作以使用原始值填充树:

    while (originalIter.hasNext()):
         newIter.next().value = originalIter.next().value
   

(1)(来自维基百科):一个完整​​的二叉树是一个二叉树,其中除了可能是最后一个级别之外,每个级别都被完全填充,并且所有节点都尽可能地离开

Answer 3

DSW算法可以解决这个O(n)时间问题.算法如下:

1] Using right-rotation operations, turn the tree into a linked list
   (a.k.a. backbone or vine)
2] Rotate every second node of the backbone about its parent to turn
   the backbone into a perfectly balanced BST. 

参考