添加新节点时维护平衡二叉树的算法

Question

 _ A _   - depth 1 
    _ B  _C_  - depth 2 
    D   E _F_ - depth 3 
       G H - depth 4 

比方说，我有那个二叉树，我想添加新节点 - I，J，K，L，M，N，O.值是不是没有排序/订购。添加节点可以是任何值。

添加I时，应将其添加到B下，以使深度3平衡良好。

 _ A _   - depth 1 
    _ B_  _C_  - depth 2 
    D I E _F_ - depth 3 
       G H - depth 4 

现在，由于深度3已满，J必须在D之下。 K也是如此。

 _ A _   - depth 1 
    _ B_  _C_  - depth 2 
_D_ I E _F_ - depth 3 
J K   G H - depth 4 

当然，L，M，N必须以相同的方式插入。

 _ A _   - depth 1 
    _ B_  _C_  - depth 2 
_D_ _I_ _E_ _F_ - depth 3 
J K L M N O G H - depth 4 

换句话说，我试图在继续下一个深度之前在树中找到任何缺失的点以添加一个节点。

我正在寻找一个快速的算法，完成这项工作或参考，很好地解释了这个算法。

呃...这是一个可选的东西......但它会真的很棒，如果这个算法可以用嵌套集模型完成，因为我正在应用它来存储整个树的分贝。我正在使用的语言是PHP。

注：

对不起，我故意跳过这个要求澄清，并专注于问题本身。

树可以不平衡的原因是没有未知父节点的节点将被添加以填充空白点（如示例），但知道它自己的父节点的节点将直接添加到其父节点下（如果父母已经有两个节点，那么它将根据算法找到比父深度更低的位置）。例如，

 _ A _   - depth 1 
    _ B  _C_  - depth 2 
    D   E _F_ - depth 3 
       G H - depth 4 

在这里，我们假设节点X知道其父^ h了。然后，节点X将被添加到H.不是一个问题。

 _ A _   - depth 1 
    _ B  _C_  - depth 2 
    D   E _F_ - depth 3 
       G _H - depth 4 
        X 

现在，添加没有父节点的节点P.然后它应该看起来像这样

 _ A _   - depth 1 
    _ B_  _C_  - depth 2 
    D P E _F_ - depth 3 
       G _H - depth 4 
        X 

假设节点Z的父母也是F，但它已经满了。在这种情况下，算法必须适用和Z节点必须在节点G平衡节点的子树F.

 _ A _   - depth 1 
    _ B_  _C_  - depth 2 
    D  P E _F_ - depth 3 
       _G _H - depth 4 
      Z X - depth 5 

节点的知道其父是为什么整个树可以不平衡的原因。

Answer 1

考虑使用此方法：

在每一个节点上，保持两个值：

• 最大左深度：叶子的最大深度在左子树
• 最大右深度：最大深度叶在右子树

选择具有较小最大深度的方向。

递进。

顺便说一句，这个例子有误导性，你可能从稳定状态开始，当双方接近平衡时。