我有一个应用程序需要具有以下特征的数据结构：
- O(n) 中的中序遍历
- 在 O(log n) 中查找
- 在 O(log n) 中插入空间 O(log n) 或更小
- 高效的就地存储（= 树可以在没有孔的连续数组中就地修改）
- 迭代，如果可能的话
- 不需要删除
我发现完整的二叉搜索树对于这些操作来说是一个很好的结构。我已经很容易地实现了遍历和查找（它们非常通用），但是插入非常困难。我似乎无法插入任意元素并重新平衡树而不会丢失形状属性（完整树）或分区属性（节点左侧的所有元素都严格小于节点）。
我在网上也找不到其他任何东西，我找到的唯一参考资料是关于一般二叉树（没有形状属性）的，不适用于我的情况。出于某种原因，完整的树不受欢迎。
有没有人为完整的二叉树实现了插入，并且可以给我一些关于如何稳健有效地实现它的指示？这不是家庭作业，我需要它来完成一个真正的项目。