无间隙二叉搜索树是具有无间隙性质的自平衡二叉搜索树“无间隙”属性表示树的宽度优先顺序中没有间隙宽度优先顺序中的间隙最好通过图表来定义。在下图中，红色虚线圆圈突出显示的区域被视为宽度优先顺序中的间隙：
如果重新构造此树以消除间隙，它将如下所示：
如果在不重新平衡的情况下将数字7添加到此重新构造的树中，它将如下所示：
同样，在消除间隙之后：
在插入和删除任意大小的树之后，是否有log（n）算法来确保无间隙属性？
最佳答案
在插入和删除任意大小的树之后，是否有log（n）算法来确保无间隙属性？
不。
要了解原因，请考虑此树（它具有无间隙属性）：
4
/ \
2 6
/| |\
1 3 5 7
要插入8，您需要完成以下操作：
5
/ \
3 7
/| |\
2 4 6 8
/
1
这显然需要至少访问每个节点一次，因为每个节点之后都有一个不同的父节点因此，你不能保证比O（N）时间更好。
同样，要删除1，您需要完成以下操作：
5
/ \
3 7
/| |
2 4 6
同样的问题。