_ 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
一个节点知道它的父节点是整个树可能不平衡的原因。
考虑这种方法:
在每个节点上,维护两个值:
- 最大左深度:左侧子树中叶子的最大深度 最大右深度
- :右子树中叶子的最大深度
选择最大深度较小的方向。
递归。
顺便说一句,这个例子具有误导性,当双方几乎平衡时,您可能会从稳定状态开始。