添加新节点时保持平衡二叉树的算法

      _  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

现在，J 必须在 D 下，因为深度 3 已满。 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

一个节点知道它的父节点是整个树可能不平衡的原因。