我正在实现一个AVL树，我试图围绕添加过程的时间复杂性。我的理解是，为了实现O（log n），您需要在树节点中保持平衡或高度状态，这样您就不必在每次需要时重新计算它们（这可能需要大量额外的树遍历） ）。
为了解决这个问题，我有一个协议，以递归的方式“向上移动”指向根的父指针的路径，在需要时进行平衡并沿途设置高度。这样，加法算法有一个“捕获”和“气泡”阶段，然后备份树状DOM事件。
我的问题是：这仍然是技术上的O（log n）时间吗？从技术上讲，你只需要在树的每个级别处理一半的分区，但是你还需要每次都向下移动然后再进行备份。这个操作的确切时间复杂度是多少？
假设树的高度为H，并且在所有操作期间结构保持平衡。然后，如您所述，插入节点将采用O（H）。
但是，每次将节点添加到AVL树时，都需要更新父节点到根节点的高度。
由于树是平衡的，更新高度将仅通过尾部中新插入的节点遍历链表式结构。
可以看到高度更新等效于遍历长度等于H的链表。因此，更新高度将需要另一个O（H），总更新时间为2 * O（H），这仍然是O（log N ）如果我们摆脱常数因素。
希望这对你有意义。