AVL 树插入的 space 复杂度是多少？

Question

AVL 插入不会是 O(logn) space，因为您需要 logn 堆栈帧来执行插入？ AVL 树本身是 O(n) space 并且插入时间是 O(logn)

Answer 1

由于平衡属性，插入、删除和搜索操作都需要O(logn)平均情况和最坏情况。因此，AVL 树给了我们优于二叉搜索树的优势，二叉搜索树在 最坏情况下具有 O(n) 时间复杂度 场景。

AVL 树的 space 复杂度在平均和最坏情况下都是 O(n)。