data-structures - 二叉搜索树问题：将 BST 转换为左右节点数相差 1 的 BST

Question

我正在做一个需要我平衡任何二叉搜索树的问题，其标准是每个级别的左右子树应该具有相同数量的节点或最多 1 个节点差异

我该如何解决这个问题？到目前为止，我已经将树转换为链表......就是这样。我很确定这是第一步，但不太确定。我到处寻找资源，但我能找到的最接近的是 day-stout-warren 算法，它基于高度而不是节点数量来平衡。

我只是在寻找伪代码

标签： data-structuresbinary-treebinary-search-treegraph-theorybalance

Answer 1

这是一个在 O(n) 时间内工作的 Python 解决方案，在 O(h) 辅助空间中就地工作，其中 h 是树的高度；唯一的辅助数据结构是递归函数所需的堆栈。

它使用生成器函数工作，该生成器函数在消费者更改树时迭代树，但我们在生成它们之前制作了子树left和子树的本地副本right，因此消费者可以在不破坏生成器的情况下重新分配它们。（实际上只需要本地副本right，但无论如何我都制作了本地副本。）

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
    def __repr__(self):
        # display for debug/testing purposes
        def _r(n):
            return '*' if n is None else '(%s ← %r → %s)' % (_r(n.left), n.data, _r(n.right))
        return _r(self)

def balance(root):
    def _tree_iter(node):
        if node is not None:
            # save to local variables, could be reassigned while yielding
            left, right = node.left, node.right
            yield from _tree_iter(left)
            yield node
            yield from _tree_iter(right)
    
    def _helper(it, k):
        if k == 0:
            return None
        else:
            half_k = (k - 1) // 2
            left = _helper(it, half_k)
            node = next(it)
            right = _helper(it, k - half_k - 1)
            node.left = left
            node.right = right
            return node
    
    n = sum(1 for _ in _tree_iter(root))
    return _helper(_tree_iter(root), n)

例子：

>>> root = Node(4, left=Node(3, left=Node(1, right=Node(2))), right=Node(6, left=Node(5), right=Node(8, left=Node(7), right=Node(9))))
>>> root
(((* ← 1 → (* ← 2 → *)) ← 3 → *) ← 4 → ((* ← 5 → *) ← 6 → ((* ← 7 → *) ← 8 → (* ← 9 → *))))
>>> balance(root)
(((* ← 1 → *) ← 2 → (* ← 3 → (* ← 4 → *))) ← 5 → ((* ← 6 → *) ← 7 → (* ← 8 → (* ← 9 → *))))