在二进制搜索树中查找最接近的值- Python
在二进制搜索树中查找最接近的值是指在一个二叉搜索树中，给定一个目标值，需要找到与目标值最接近的节点的值。
二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树，它满足以下性质：
- 左子树中的所有节点的值小于根节点的值。
- 右子树中的所有节点的值大于根节点的值。
- 左右子树也分别为二叉搜索树。
在Python中，可以通过递归或迭代的方式实现在二叉搜索树中查找最接近的值。
递归实现的代码如下：
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def closestValue(root, target):
if not root:
return None
if root.val == target:
return root.val
if target < root.val:
if not root.left:
return root.val
left_closest = closestValue(root.left, target)
return root.val if abs(root.val - target) < abs(left_closest - target) else left_closest
else:
if not root.right:
return root.val
right_closest = closestValue(root.right, target)
return root.val if abs(root.val - target) < abs(right_closest - target) else right_closest迭代实现的代码如下：
def closestValue(root, target):
closest = root.val
while root:
closest = min(root.val, closest, key=lambda x: abs(target - x))
root = root.left if target < root.val else root.right
return closest这个算法的时间复杂度是O(logN)，其中N是二叉搜索树中的节点数。
在腾讯云的产品中，可以使用云数据库MySQL、云数据库Redis等来存储二叉搜索树的节点数据。此外，云函数SCF（Serverless Cloud Function）可以用来部署和运行这个算法的代码。
相关·内容
2回答
我正在探索Python中的bisect模块。这个模块的全部用途对我来说已经很清楚了，我现在知道如何使用它了。但是文档中的声明如下：
二分法是搜索值范围的有效方法。对于定位特定的值，字典更有表现力。
“搜索值的范围”是什么意思？bisect有bisect_left()和bisect_right()，它们都接受要查找索引的单个值。医生有什么解释吗？谢谢。
浏览 8提问于2021-12-02得票数 1
回答已采纳
1回答
我正在尝试创建一个搜索树，它可以存储重复的键，并对这些键具有不同的值。
基本上，我有一个位字符串形式的哈希码。值是位串，键是位串中出现的1的个数。
例如，我可以有两个位串：
bitstring1 = "00001111";
bitstring2 = "11110000";
所以它们有相同的密钥：
key1 = 4;
key2 = 4;
有可能在搜索树中实现这一点吗？
浏览 0提问于2017-11-24得票数 0
2回答
堆还是红黑树？
、、、、
我愿意使用数据结构作为常量空间的溢出缓冲区。我希望有有效的插入，但最重要的是高效删除min元素。我考虑使用堆，因为我有O( log(n) )、find_min()和log(N)插入和删除。另一方面，我知道与红黑树相比，我不理解它的优势，因为它还有O(log(n))、insert和delete，以及O(1)查找min/max。以及排序输出的优点(我不关心这个)。
这个问题与：有关
既然我有std::map和boost：：堆这两种结构，为什么我更喜欢使用堆而不是红黑树呢？最后，使用红黑树，我还有O(log(n))搜索条目的时间，而堆的搜索时间是O(n)，这一点很重要，因为存在重复。
浏览 3提问于2013-07-17得票数 10
回答已采纳
2回答
我有一个简单的问题，我对此感到困惑。我知道在二进制搜索树中拥有键/值对的概念是什么，以及树在构建时是什么样子的。
我不确定的是，如果我不知道它的键是什么，如何在这样的BST中搜索值？
例如：
假设我有一个充满整数(作为值)和唯一整数(作为键)的二进制搜索树。假设我想计算特定整数(比方说: 200)在此BST中出现的次数。所以我所知道的是，200是“值”而不是“键”。因此，我根本不知道密钥。
我现在如何在整个BST中搜索所有的“200”？它现在是不是变成了一个简单的BST，我根本不需要密钥？但是，使用"key“而不是value将树排列到左子对象和右子对象。
我还可以给你一个初始化BST的
浏览 3提问于2013-03-17得票数 6
回答已采纳
2回答
为什么二叉树比已排序的值数组更可取？
在任何一种情况下，找到给定的键值(通过遍历二叉树，或者通过在排序的数组上执行二进制搜索)都需要O(log )的时间复杂度。
浏览 1提问于2015-03-10得票数 1
2回答
可能重复：
我做过各种各样的练习，包括添加、删除、排序等。
然而，我很难想象二进制搜索树在实际程序中的使用。我是说，它比其他一些搜索算法要快得多。但这是唯一的用途吗？
你能给我一些这个算法在实际软件中使用的例子吗？
浏览 0提问于2012-12-16得票数 5
回答已采纳
22回答
每个程序员都被教导二进制搜索是搜索有序数据列表的一种很好的、快速的方法。有许多使用二进制搜索的玩具教科书示例，但在实际编程中又如何呢:二进制搜索在现实程序中实际使用的位置在哪里？
浏览 0提问于2009-02-12得票数 38
2回答
问题
有没有一种简单的方法来判断系统可执行文件在使用node的系统路径上是否可用？例如，如果用户在/usr/bin/python上安装了python，而/usr/bin在$PATH中，我如何在Node中检测到它？反之，当某些东西没有安装或不在path上时，也就是/usr/opt/local/mycustompath/python？理想情况下，希望他们的是一个可用的npm包…
我确信这是一个快速的谷歌搜索，有正确的搜索词，但我失败了，因为事实是在哪里和哪些是非常通用的搜索词。
背景
我正在为一个node工具开发一些dev config，希望能够检测到python (或pip)是否已经在path上
浏览 1提问于2014-09-29得票数 5
我正在尝试在我的应用程序中实现二进制搜索。我正在创建一个方法来查看用户的联系人列表，将数字添加到数组中，对其进行排序，然后使用二进制搜索来定位号码等等。
但是我在想应该使用什么类型的数组，然后对其进行排序，然后实现二进制搜索。或者有一种存储数据的方法？比如布景，还是地图等等？
场景-我会从他们的电话里得到用户的联系方式。当然，每个数字都需要存储在数组或列表中(哪个更好)。然后对数组进行排序。现在我想用二进制搜索来搜索一个数字。由于用户可以拥有一个大的联系人集，我认为这是一个很好的方法。
浏览 0提问于2018-06-07得票数 1
回答已采纳
我想在c# 4.0中对排序列表使用二进制搜索选项。我一直在寻找旧的二进制搜索：
我想要一些帮助，我将如何使用binarySearch在两个日期之间进行范围搜索。我有一个包含多个日期的列表，我想快速搜索这两个日期之间的大型列表，并返回找到的项目(如果有)。我认为二进制搜索会很快，因为它会在排序时迅速消除不必要的比较。
浏览 0提问于2012-08-03得票数 1
5回答
我有一个值列表(一维)，我想知道用来查找最接近查询值的最佳数据结构/算法。大多数解决方案(所有？)我发现这里的问题是针对2个或更多维度的。有没有人能给我建议我的案例的方法？
我的直觉告诉我对数据进行排序，并以某种方式使用二进制搜索。顺便说一句，对于任何所需的树，都没有构造或插入时间的限制，所以可能有人会建议一种比简单的排序列表更好的树。
浏览 1提问于2010-07-19得票数 9
回答已采纳
3回答
今天我有一个面试，我被问到如何搜索一个数组中的数字，我说二进制搜索，他问我一个有数千个对象(例如股票)的大数组如何，例如通过股票的价格进行搜索，我又说二进制搜索，他说在应用二进制搜索之前，对数千个数组进行排序需要很长时间。
你能耐心点教我怎么解决这个问题吗？谢谢，感谢您的帮助。
浏览 0提问于2012-03-23得票数 7
我有一个任务是通过一些对象的字段在巨大的内存中对象数组中执行快速搜索。我需要选择满足某些条件的对象子集。
标准可以被指定为浮点值或这种值的范围(例如，2.5..10)。
问题是要搜索的float属性并不是完全均匀分布的；它可能包含几个值范围为10-20的对象(例如)和一百万个值为0-1的对象，以及一百万个值为100-150的对象。
那么，如何建立索引来有效地搜索这些对象呢？欢迎使用代码示例。
浏览 0提问于2012-07-17得票数 0
回答已采纳
#include <iostream>
#include <set>
#include <tuple>
struct Key {
int field1;
int field2;
Key(int field1, int field2) : field1(field1), field2(field2) {}
bool operator<(const Key& other) const {
// Is this acceptable?! Seems to work
if (field2 == 0 || other
浏览 1提问于2016-02-09得票数 0
2回答
我一直在使用一种数据结构，最初的开发人员称之为heap，它用于实现优先级队列。
虽然有很多关于二叉树的文章，但(min/max)堆似乎定义得不太好(细节因实现而异)。
我注意到一些不一定适用于二叉树结构的特性。
相同的元素可以多次出现在队列中，而不会造成执行或实现上的复杂性。
搜索(虽然可能并且比彻底搜索更快)，但效率不高(因为每个节点的子元素不需要平衡)。
由于搜索效率不高，而且可能存在重复搜索，因此删除可能需要存储对node的引用，而不是使用key查找节点(这是二叉树的常见做法)。
，与二叉树相比。
(与二叉树相比，最好的情况更好，最差的情况更糟)
对于符合这些特征
浏览 4提问于2017-10-31得票数 1
回答已采纳
我有一个浮动数组，从最小到最大排序，并且需要能够选择大于或小于传递的输入值的最近的浮点数。此输入值不一定以数组中的值形式表示。
一种简单的方法是在数组中进行简单的线性搜索。看起来可能是这样：
void FindClosestFloatsInArray( float input, std::vector<float> array,
float *min_out, float *max_out )
{
assert( input >= array[0] && input < array[
浏览 0提问于2011-09-20得票数 10
回答已采纳
4回答
搜索大量已排序的数据块
、、、
我有一个巨大的数据记录在磁盘上，根据一些键按排序顺序排列。数据一次被读取到内存中一个块(数千条记录)。我必须搜索并显示所有匹配密钥的记录。我在考虑一些基于二进制搜索的算法，但我在这里有一些限制。
记录只能从块的开始按顺序在块中查找。
具有相同键的记录可以跨越多个块(如图8所示)。在二进制搜索中，如果我正在加载中间块，如果第一个记录匹配，则必须在匹配块之前扫描这些块。
有人能帮我设计出一种在C++中有效的策略吗？采用线性搜索方法是否有效？
+---+
| 1 | Block1
| 3 |
| 3 |
| 4 |
+---+
| 4 | Block2
| 6 |
| 7 |
| 8
浏览 8提问于2011-03-07得票数 6
回答已采纳
2回答
我在业余时间一直在使用二进制搜索树，我希望能够从树中删除节点。
为了让它工作，我需要找到最大值。你是怎么做的呢？伪代码或提示将不胜感激。我被卡住了，甚至不知道该如何开始。
浏览 0提问于2012-05-01得票数 1
1回答
ternery搜索树需要O( log(n) +k)比较，其中n是字符串的数目，k是要搜索的字符串的长度，二进制搜索树需要log(N)比较，那么为什么TST比BST快呢？
浏览 4提问于2014-10-12得票数 2
2回答
在Python2.7或Python3.x中是否存在自平衡二进制搜索树(红黑、AVL或其他)内置类型？
我正在寻找类似于Java的或的东西。
如果没有这样的内置设备，为什么会被置之不理呢？是否有特别的理由，不包括这些工具？
浏览 3提问于2013-07-25得票数 35
回答已采纳
我需要将数字范围定义为字典索引，例如：
SCHEDULE = {
(0, 5000): 1,
(5001, 22500): 2,
(22501, 999999999): 3
}
我通过这个函数搜索它：
def range_index(table, val):
new_table = {k: v for tup, v in table.items() for k in range(tup[0], tup[1]+1)}
return new_table.get(int(val)) # int() is used to deal with floats.
只
浏览 0提问于2020-01-31得票数 0
回答已采纳
如何进行线性运算我想要得到数组中要插入的项的位置，我指的是必须在数组中插入数据的索引。我如何仅使用线性搜索来实现这一点。建议请提出来。
浏览 2提问于2012-04-02得票数 0
3回答
我目前正在中存储大量无符号32位整数(有效地为32位值中的每一位形成一个具有节点的二叉树)。这对于快速查找精确值是非常有效的。
现在，我希望能够在trie中搜索可能存在或不存在的键，并找到小于或等于搜索键的第一个键的值。是否可以有效地使用一些trie，还是应该使用不同的数据结构？
我使用trie，因为它的速度和缓存的局部性，理想情况下，想要牺牲两者。
例如，假设trie添加了两个键：
0x00AABBCC
0x00AABB00
我现在正在寻找一个不存在的密钥，0x00AABB11。我想找到树中的第一个键，它的值是<=，搜索键，在本例中，搜索键将是0x00AABB00的节
浏览 3提问于2013-12-10得票数 1
我有一个BST树大小为n的后置数组，如何显示只有一个BST可以从它构造。我知道如果从右到左添加节点，我可以重建树，但是如何显示只有一个正确的树呢？
我试着说有两棵可能的树，并试图证明它是不可能的，但被卡住了。
浏览 2提问于2012-01-13得票数 1
我有点糊涂。我现在正试着学习二进制搜索树，我的理解是，在预顺序遍历中，左分支节点的值应该小于根值。例如，根: 7，左: 6，右: 8。
但是我已经看到了一个前置遍历的例子:1，2，4，5，3，图像重新迭代，1是根，2是左节点。但2明显大于1。
我是不是误会了什么？
浏览 4提问于2022-10-27得票数 0
4回答
我正在寻找一种STL排序，如果容器中不存在确切值，它会返回与目标值“最接近”的元素。它需要很快，所以基本上我在寻找一个稍微修改过的二进制搜索...我可以写它，但它看起来应该已经存在了……
浏览 0提问于2010-09-02得票数 4
2回答
最小值不是在二叉树中？
、、、
我试图找到一种方法来找到最小正值([0，INT_MAX)) (最大整数)值，而不是在二进制搜索树中。树有所有正整数。我正在考虑穿过树的左边。然后创建一个struct值struct { int data; bool found; };，如果它是min值，则返回t/f。
我这样做是通过遍历左侧，如果根->data+1>左侧>data，则返回
左->数据+1
否则就往右走。那如果
根->数据+1<右->数据
，然后是return root->data + 1.否则，如果right不是null，则返回root->data or ri
浏览 6提问于2013-01-28得票数 1
回答已采纳
2回答
二进制搜索的最佳运行时间是O(log(n))，如果二叉树是平衡的。最坏的情况是，如果二叉树是如此不平衡，它基本上代表一个链接列表。在这种情况下，二进制搜索的运行时间是O(n)。
但是，如果树只是稍微不平衡呢，就像这棵树的情况一样：
如果我没有弄错的话，最好的情况仍然是O(log )。但最坏的情况是什么？
浏览 4提问于2017-04-01得票数 1
1回答
考虑以下二进制搜索树，以及以下查找频率：
13 Key | 13 | 11 | 26 | 1 | 12 | 28
/ \ -----------------------------------------
浏览 2提问于2017-09-18得票数 2
回答已采纳
我用python 3.6.2写了一个程序。
我将.py转换为安装文件。
我希望在python程序中，或者编写一个函数，下载新版本的程序并自动安装并删除旧版本。我在网上搜索了一下，但没有找到一个好的解决方案。有人能帮我吗？
浏览 3提问于2017-08-31得票数 1
3回答
我对二叉树数据结构是个新手。我不明白的一件事是为什么最左边的节点是最小的
10
/ \
5 12
/ \ / \
1 6 0 14
在上面的例子中，0是最小值，而不是1。
告诉我我弄错了什么地方。
谢谢!
浏览 1提问于2015-09-01得票数 1
优先级队列:基本操作:插入删除(Delete minumum元素)
目标:为上述功能提供高效的运行时间或增长顺序。
通过：实现优先级队列：
Linked List: Insertion will take o(n) in case of insertion at end o(1) in case of
insertion at head.
Delet (Finding minumum and Delete this ) will take o(n)
BST:
Insertion/Deltion of minimum = In av
浏览 7提问于2012-05-29得票数 2
回答已采纳
3回答
我想到了一个排序算法，但我不确定这个算法是否已经存在。
假设我们有一个包含n个项目的容器：
我们选择第三个元素，并对第一个2进行二进制搜索，将其放在正确的位置。对容器中的前3个项目进行排序。
我们选择第四个元素，对前三个元素进行二进制搜索，并将其放在正确的位置。现在对前4个项目进行了排序。
我们选择第五个元素，对前四个项目进行二进制搜索，并将其放在正确的位置。现在已对5个项目进行排序。
。。。
我们选择第n个元素，并对其他n-1个元素进行二进制搜索，将其放在正确的位置。所有项目都已排序。
对于k个元素，二分搜索需要logk，假设插入需要固定的时间。这不应该是这样的：
log2将第三个元素放在正
浏览 0提问于2014-04-09得票数 0
1回答
考虑到“三元搜索的大O时间是Log_3 N而不是二进制搜索的Log_2 N”
这应该是因为经典的三值搜索需要3次比较，而不是2次，但是这种实现会比二进制搜索效率更低吗？
#!/usr/bin/python3
List = sorted([1,3,5,6,87,9,56, 0])
print("The list is: {}".format(List))
def ternary_search(L, R, search):
"""iterative ternary search"""
if L > R:
浏览 2提问于2017-10-15得票数 1
回答已采纳
我正在看书，我发现了这个问题，我不知道它的正确答案是什么。以下是一个问题：
假设您正在为手机实现地址簿功能。地址簿需要按人的姓氏进行排序，并在查询姓氏时支持快速访问。以下哪一种数据结构是用来存储地址簿的好选择？解释一下原因。这是个糟糕的选择，为什么呢？
(a)未排序的链接列表
(b)分类链接列表
(c)二进制搜索树
(d)散列表
我的答案是使用哈希表，因为它有键和值.我的答案正确吗？
谢谢
浏览 0提问于2016-01-04得票数 1
回答已采纳
我觉得这是必须存在的，但我就是想不出来。有没有一种数据结构可以保存已排序的值列表并快速搜索(可能是log(N)时间，就像数组一样)，并且还支持在log(N)或常量时间中插入和删除元素？
浏览 0提问于2013-07-15得票数 1
回答已采纳
3回答
我刚刚完成了一个工作面试，我正在努力解决这个问题，对于我来说，在15分钟的面试中，这个问题似乎是一个非常难回答的问题。
问题是:编写一个函数，它给定一个整数流(无序)，构建一个平衡的搜索树。现在，您不能等待输入结束(它是一个流)，所以您需要动态地平衡树。
我的第一个答案是使用红黑树，这当然可以完成这项工作，但我必须假设他们没有期望我在15分钟内实现一棵红黑树。
那么，对于这个我不知道的问题，有什么简单的解决方案吗？
谢谢,
戴夫
浏览 1提问于2011-08-30得票数 11
4回答
二进制搜索和二叉树有什么区别？
是一样的吗？阅读互联网，它似乎第二只为树(多达2个子节点)和二进制搜索不遵循这条规则。我不太明白。
浏览 1提问于2014-02-05得票数 38
回答已采纳
假设我想存储有序的值，其中键值表示一个下限。如下例所示： d = {1: "pear", 4: "banana", 7: "orange"} 我可以通过d[1]访问第一个对象。假设我想存储它，这样我就可以通过调用[1,4)之间的任意值来访问第一个对象"pear"。如果我在[4,7)之间输入任何"keyvalue"，我希望返回"banana"。有没有像python中那样的数据结构？我找到了intervalTrees，但它看起来比我想要的要高级一点。在intervalTrees中，作为关键点的间隔可以
浏览 20提问于2021-10-17得票数 0
回答已采纳
6回答
我有一个词汇表，里面有不同的单词和关于它们的信息。它的大小约为100MB。但是，搜索此文件需要很长时间。有什么方法可以提高我查找数据的速度吗？例如，我正在考虑编写一个程序，将文本文件拆分为26个不同的文本文件(按单词的第一个字母)，然后，该程序只需检查给定单词的第一个字母，并且将有一个小得多的文件可供搜索。这会改善程序的执行时间吗？有没有什么有效的数据结构可以用来存储文件？比如json。另外，数据库是怎么回事？我使用的是Kotlin/Java。
编辑:到目前为止，我已经对整个文件进行了暴力搜索，直到找到匹配的文件。但是，正如我所说的，该文件的大小大于100MB。程序的执行时间大约是5秒，也就是
浏览 49提问于2020-06-26得票数 0
我使用的是Mac10.6.8计算机，在此之前，每当我启动终端并输入" python“时，它都会告诉我使用python2.6.1，尽管几个月前我已经从Python.org安装了2.7.3：
cd
python
Python 2.6.1 (r261:67515, Jun 24 2010, 21:47:49)
因此，我在网上搜索，看看如何在使用Python解释器时更改为Python2.7.3。我是从Python.org安装的，根据这个问题( )，苹果和Python.org的python的默认位置不同。然后，我移到了Python.org python所在的位置，并简单地输入了python：
浏览 2提问于2013-01-23得票数 0
回答已采纳
1回答
我正在为算法分析考试做准备，在我学习了C#并以不同的方式实现了字典之后，我对它的优缺点感到困惑。
以下是我的问题：
使用无序数组而不是总是排序数组来实现字典的原因是什么？
使用排序数组而不是无序数组来实现并行化的准备吗？
使用二进制搜索树而不是总是排序的数组来实现字典的原因？
浏览 4提问于2013-12-11得票数 0
回答已采纳
2回答
假设我有一个Binary Search Tree
50
/ \
17 72
/ \ / \
12 23 54 76
/\ / \
9 14 19 67
对不起，我不擅长画树
我想返回属于某个范围内的所有节点。例如
[12, 23] --> {12, 14, 17, 23, 19}
我的方法很简单
寻找LCA
找到下界
While节点!= LCA.parent，添加右子树
从LCA，而节点!=上界，添加左子树
添加上界和上界的左子树
但是，
浏览 1提问于2016-05-05得票数 0
回答已采纳
我正在尝试理解段树。我在hackerrank ()上尝试了一个问题，并尝试使用c++中的geeksforgeek代码。但是，我在第19行遇到了转储值问题。
int right = RMQUtil(st, mid+1, se, qs, qe, 2*index+2); // why this is getting a dump value here?
我还发现这会超时。有没有其他有效的方法来解决这个问题？我想知道为什么我的代码不能有效地解决这个问题，并且需要在c++中有一个更好的解决方案
这是我尝试过的代码。
// you will see the comments on the geeksfor
浏览 8提问于2020-01-21得票数 0
1回答
如问题标题中所述，我需要一个适合快速高效搜索的数据结构。数据结构还应该能够在数据结构中的任何地方添加/删除元素。
目前我使用的是链接列表。但是问题是，我应该遍历这个列表来找到一个想要的元素。一般搜索算法(二进制搜索、跳转搜索和.)在链接列表中不能直接使用，因为没有对列表元素的随机访问。对这些算法所需的列表元素进行排序也是一个问题。另一方面，我不能使用数组，因为很难将一个元素添加/移除到任何想要的索引中。
我一直在寻找链表中的搜索算法，然后我开始寻找“跳过列表”。现在我想问一下，我的情况是否有一个更好的数据结构，或者是否有一个更好的链表搜索算法。
浏览 0提问于2019-06-19得票数 1
回答已采纳
在一些浮点数上调用.as_integer_ratio()时，我注意到一些奇怪的事情。例如：
(2.2).as_integer_ratio()
这将返回一个元组：(2476979795053773,1125899906842624)
我想知道是否可以让它以某种方式直接返回11/5？
浏览 5提问于2018-11-21得票数 0
5回答
使用二叉树的具体例子？
、、、
我了解二进制搜索树是如何实现的，但我不确定使用它相对于大多数编程语言在其标准库中构建的哈希表有什么优势。
谁能提供一些可以用二叉搜索树解决的现实问题的例子？
浏览 4提问于2011-02-16得票数 14
回答已采纳
我在项目根目录中有一个.venv文件夹，它有一个python虚拟环境。当我使用Pycharm的搜索特性时，它还显示了这个.venv文件夹的结果。如何从搜索结果中忽略虚拟环境文件夹？
我试着将目录标记为Excluded，但这没有帮助。
浏览 0提问于2019-09-04得票数 12
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
云直播活动推荐
腾讯云开发者
