有谁知道如何计算嵌套二进制搜索树的复杂性？我已经实现了一个嵌套的二进制搜索树，深度为3个BST .
编辑：我为混乱道歉，我的意思是BST的每个节点都指向另一个BST的根节点 . 我要求的复杂性是搜索，更新和删除（基本操作）的时间复杂性 . 我假设由于BST的时间复杂度为O（log（n）），嵌套BST在搜索，更新和删除方面的时间复杂度差别不大 .
我假设“嵌套”意味着特定树的每个节点都指向另一棵树的根，最多可达3级 .
二进制搜索树通常是O（log n）查找时间 . 因为你正在进行3次查找，所以是O（log a * log b * log c） . 当然，这是假设他们很 balancer 和一切 . 二叉搜索树的最坏情况是O（n）（想象一下它基本上是一条直线的树） . 那么最坏的情况是O（a * b * c） .
对于记录，b和c分别是第一个树，第二个嵌套树和第三个双嵌套树中的元素数 .
1 回答
我假设“嵌套”意味着特定树的每个节点都指向另一棵树的根，最多可达3级 .
二进制搜索树通常是O（log n）查找时间 . 因为你正在进行3次查找，所以是O（log a * log b * log c） . 当然，这是假设他们很 balancer 和一切 . 二叉搜索树的最坏情况是O（n）（想象一下它基本上是一条直线的树） . 那么最坏的情况是O（a * b * c） .
对于记录，b和c分别是第一个树，第二个嵌套树和第三个双嵌套树中的元素数 .