我能在O(log(N))内实现二叉树的开始插入吗?

Question

考虑一棵二叉树和一些遍历标准，该标准定义了树中元素的排序。

是否存在某种特定的遍历准则，允许进行begin_insert操作，即根据遍历准则的排序，以O(log(N))的代价在位置1添加一个新元素的操作?

我没有什么严格的要求，像树一样保证平衡。

编辑:但如果在最坏的情况下导致退化到O(N)，我不能接受缺乏平衡。

的例子:

让我们试着看看序遍历是否可行。

考虑BT(不是二叉搜索树)

                      6
                   /     
                  13      5
                 /      /
                2    8  9

序遍历得到2-13-8-6-9-5

按顺序遍历得到7-2-13-8-6-9-5执行begin_insert(7):

                      6
                   /     
                  13      5
                 /      /
                2    8  9
               /
              7

现在，我认为这不是一个合法的O(log(N))策略，因为如果我继续以这种方式增加值，随着树变得越来越不平衡，成本退化为O(N)

                      6
                   /     
                  13      5
                 /      /
                2    8  9
               /
              7
             /
            *
           /
          *
         /

如果我通过保持排序来重新平衡树，这个策略将有效:

                      8
                   /     
                  2       9
                 /      / 
                7    13 6   5

，但这至少花费O(N)。

根据这个例子，我的结论是，按顺序遍历不能解决问题，但因为我收到的反馈，它应该工作，也许我错过了什么?

Answer 1

在二叉树中插入、删除和查找都依赖于相同的搜索算法来找到正确的位置进行操作。O(树的最大高度)的复杂度。原因是为了找到正确的位置，你从根节点开始，比较键值来决定你应该进入左子树还是右子树，你一直这样做，直到你找到正确的位置。最坏的情况是你必须沿着最长的链走下去，这也是树的高度的定义。

如果你没有任何约束并且允许任何树，那么这将是O(N)，因为你允许只有左子树(例如)。

如果你想获得更好的保证，你必须使用保证树的高度有下界的算法。例如，AVL保证你的树是平衡的，所以最大高度总是log N，上面所有的操作都在O(log N)内运行。红黑树不保证log N，但承诺树不会太不平衡(最小高度* 2>=最大高度)，所以它保持O(log N)的复杂度(详见页面)。

根据您的使用模式，您可能能够找到更专业的数据结构，从而提供更好的复杂性(参见Fibonacci堆)。