java - 我的高度函数会破坏我的 O(log N) AVL 树插入和删除吗？高度如何实现？

Question

我已经实现了一个 AVLtree，但现在它已经完成了，我想到了一些事情。基本上我通过每次计算每个子树的高度来计算高度。算法类似于:

if node is null return -1;
else return 1 + max( height(left), height(right))

这意味着当我检查我的树是否平衡时我使用这个函数。但这样的高度是线性的，对吧？那么这意味着删除和插入将是 N log N 或 N，而不是 log N？

Answer 1

是的，这与树中的节点数量呈线性关系。

您能否缓存子树的高度，以便只有您变异的树部分需要重新计算高度(变异节点及其祖先)？这应该会让您以 O(n) 存储成本回到 O(log n)。