给出了BST(二叉搜索树)T. 如何找到T的第n个最小元素?BST的第n个最小元素
0
A
回答
2
二叉搜索树被有效排序,所以你只需要按顺序遍历树并到达第n个点。如果树是完全平衡的,你可以计算要去的地方。
0
如果二叉搜索树不完全平衡,那么您需要执行递归搜索以查找第n个最小元素。通过让每个节点存储每个分支指针所指向的子节点的数量,可以大大加速这种情况,从而有效地将搜索转换为二进制指针。但是,这会增加树更新的开销,因为每次插入或删除都需要通过叶到根遍历来更新节点计数。
或者,您可以保持树平衡,并使用上述答案。
相关问题
- 1. BST第n小(C)
- 2. 如何找到BST的最小元素?
- 3. 在大小为N的数组的每k个元素中查找最小元素和第二小元素
- 4. 重复间隔数组的第n个最小元素
- 5. 在bst中第k个最小数字
- 6. 在排序中查找数组中第n个最小元素?
- 7. MATLAB:查找每行第n个最小元素
- 8. 在O(log n)中查找第k个最小元素
- 9. 通过base px * n第n个元素缩进每个第n个元素
- 10. Zen第n个元素
- 11. 获取BST的第n个项目
- 12. 更新嵌套列表中第n个元素的第n个元素
- 13. 第K个最小元素算法
- 14. 找到第k个最小元素
- 15. 作业:返回大于给定元素的集合中的最小元素BST
- 16. 删除BST中的最大元素
- 17. 的Python:用最大值/最小值的第n个元素的元组提取从元组
- 18. 得到每一个第n个元素或最后一个
- 19. KST BST递归解决方案中的最小元素
- 20. 查找二进制搜索树中的第n个最小元素
- 21. 计划中的第n个元素
- 22. 第n个孩子的元素1,6,7,10,13 ECT
- 23. 获得集合的第n个元素
- 24. CSS第n个子公式选择第7个元素和第5个元素
- 25. 如何更改:第n个元素的背景大小
- 26. 如何选择具有最大第n个元素的矢量
- 27. C++查找地图的第N个最高元素
- 28. 获取Python中列表中最小N个元素的索引
- 29. 如何查找矢量中n个最小元素的索引
- 30. 算法找不到。大小为n的子集,其中每个元素都小于其前一个元素,索引是第一个元素是最少的
看起来像家庭作业 –