嵌套二叉搜索树的复杂性 [英] Complexity of a nested binary search tree

问题描述

有人知道如何计算嵌套二进制搜索树的复杂度吗?我已经实现了一个嵌套的二进制搜索树，深度达到3个BST.

对于造成混淆，我深表歉意，我的意思是BST的每个节点都指向另一个BST的根节点.我要求的复杂性是搜索，更新和删除(基本操作)的时间复杂性.我曾经假设，由于BST的时间复杂度为O(log(n))，因此嵌套BST的时间复杂度在搜索，更新和删除方面不会有太大差异.

解决方案

我假设嵌套"是指一棵特定树的每个节点都指向另一棵树的根，最多三层./p>

二叉搜索树通常将是O(log n)查找时间.由于您要进行3次查找，因此为O(日志a *日志b *日志c).当然，这是假设它们平衡良好，并且一切正常.对于二叉搜索树，最坏的情况是O(n)(想想一棵基本上是一条直线的树).那么最坏的情况是O(a * b * c).

根据记录，a b和c分别是第一棵树，第二棵嵌套树和第三棵双嵌套树中的元素数.

Does anyone know how to calculate the complexity of a nested binary search tree? I have implemented a nested binary search tree to a depth of 3 BSTs.

EDIT: I apologize for the confusion, I had meant that each node of the BST would point to the root node of another BST. The complexity I was asking for was time complexity of search, update, and delete (basic operations). I had assume that since the time complexity of a BST was O(log(n)), the time complexity of a nested BST in terms of search, update, and delete wouldn't differ that much.

解决方案

I'm assuming that by "nested" you mean that each node of a particular tree points to the root of another tree, up to 3 levels deep.

Well a binary search tree is generally going to be O(log n) lookup time. Since you're doing 3 lookups, that's O(log a * log b * log c). Of course that's assuming that they're well balanced and everything. The worst case for a binary search tree is O(n) (think of a tree where it's basically a straight line). Then the worst case time would be O(a * b * c).

And for the record, a b and c are the number of elements in the first tree, second nested tree, and third doubly-nested tree, respectively.

这篇关于嵌套二叉搜索树的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！