首页 文章

balancer BST

提问于
浏览 次
37

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

Question: 修改BST，使其尽可能 balancer . 不用说，你应该尽可能高效地做到这一点 .

Hint: 采访者说这是一个合乎逻辑的问题，如果你有不同的想法，你会得到答案 . 没有困难的编码 .

  • 话虽如此，我认为他不指望我指向AVL / RB树 .

My Solution: 我提出，我会按顺序遍历树，把中间元素作为新树的根（让我们称之为新的根） . 然后转到中间元素的左侧部分，将其中间元素作为树根新子根的左子树的根 . 同样适用于正确的部分 . 递归地执行此操作将提供最佳 balancer BST .

Why I am posting it here: 但是他对答案不满意:(那么，有没有办法做这个没有用于权重/ RB着色策略，还是他只是和我一起鬼混？请提出你的专家意见 .

Duplicate? No! 我知道有这个question但是请求者提出的解决方案太复杂了，另一个讨论了AVL树 .

algorithm data-structures binary-search-tree

3 回答

  • 10

    您可能希望查看 Day-Stout-Warren 算法，该算法是一种O（n）-time，O（1）空间算法，用于将任意二进制搜索树重新整形为完整的二叉树 . 直觉上，该算法的工作原理如下：

    • 使用树旋转，将树转换为简并链接列表 .

    • 通过将选择性旋转应用于链表，将列表转换回完全 balancer 的树 .

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

    希望这可以帮助！

    回复于
  • 35

    "Balanced as possible" = complete (or full) binary tree 1.你无法获得更多的 balancer .

    解决方案很简单 - 构建一个“空”完整二叉树，并在inorder-traversal中迭代新树和输入树（同时）以填充整个树 .

    完成后，您可以获得最 balancer 的树，并且此方法的时间复杂度为 O(n) .

    EDIT:
    这应该按照以下步骤完成：

    • 使用 n 节点构建虚拟完整树 . 每个节点的所有值都将初始化为一些垃圾值 .

    • 创建两个迭代器：（1） originalIter 用于原始树，（2） newIter 用于新（用垃圾初始化）树 . 两个迭代器都将按顺序遍历返回元素 .

    • 执行以下操作以使用原始值填充树：

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

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

    回复于
  • 15

    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.

    Reference

    回复于

相关问题