有谁知道如何计算嵌套二叉搜索树的复杂度？我已经实现了一个深度为 3 个 BST 的嵌套二叉搜索树。
编辑:对于造成的混淆，我深表歉意，我的意思是 BST 的每个节点都将指向另一个 BST 的根节点。我要求的复杂性是搜索、更新和删除(基本操作)的时间复杂性。我曾假设，由于 BST 的时间复杂度为 O(log(n))，因此嵌套 BST 在搜索、更新和删除方面的时间复杂度不会有太大差异。
最佳答案
我假设“嵌套”是指特定树的每个节点都指向另一棵树的根，最多 3 层深。
二叉搜索树通常需要 O(log n) 的查找时间。由于您要进行 3 次查找，因此是 O(log a * log b * log c)。当然，这是假设它们非常平衡和一切。二叉搜索树的最坏情况是 O(n)(想想它基本上是一条直线的树)。那么最坏情况下的时间就是 O(a * b * c)。
记录一下，a b 和 c 分别是第一棵树、第二棵嵌套树和第三棵双嵌套树中的元素数。
关于algorithm - 嵌套二叉搜索树的复杂性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5572454/