搜索树
在计算机科学中，搜索树是一种树状数据结构，它的作用是能更方便地从一个集合中找到所要查找的键。搜索树规定其每个节点的键必须大于其左子树中的任何一个键且小于其右子树中的任何一个键。二叉查找树、三叉搜索树、B树等都属于搜索树。
原文地址：
https://zh.wikipedia.org/wiki/%E6%90%9C%E7%B4%A2%E6%A0%91
在知识共享 署名-相同方式共享 3.0协议之条款下提供
本站所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 IT技术记录小站！
相关推荐
2022-12-28
倒排索引
倒排索引（英语：Inverted index），也常被称为反向索引、置入文件或反向文件，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。 有两种不同的反向索引形式： 一条记录的水平反向索引（或者反向文件索引）包含每个引用单词的文档的列表。 一个单词的水平反向索引（或者完全反向索引）又包含每个单词在一个文档中的位置。 后者的形式提供了更多的兼容性（比如短语搜索），但是需要更多的时间和空间来创建。 例子以英文为例，下面是要被索引的文本： {\displaystyle T_{0}=}0. "it is what it is" {\displaystyle T_{1}=}1. "what is it" {\displaystyle T_{2}=}2. "it is a banana" 我们就能得到下面的反向文件索引： 12345"a": {2}"banana": {2...
2022-12-31
康托展开
康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。 以下称第x个全排列都是指由小到大的顺序。 公式{\displaystyle X=a_{n}(n-1)!+a_{n-1}(n-2)!+\cdots +a_{1}\cdot 0!}其中,{\displaystyle a_{i}}为整数,并且{\displaystyle 0\leq a_{i}
2022-12-31
八皇后问题
八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。 历史八皇后问题最早是由国际象棋棋手马克斯·贝瑟尔（Max Bezzel）于1848年提出。第一个解在1850年由弗朗兹·诺克（Franz Nauck）给出。并且将其推广为更一般的n皇后摆放问题。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。 在此之后，陆续有数学家对其进行研究，其中包括高斯和康托，1874年，S.冈德尔提出了一个通过行列式来求解的方法[2]，这个方法后来又被J.W.L.格莱舍加以改进。 1972年，艾兹格·迪杰斯特拉用这个问题为例来说明他所谓结构化编程的能力[3]。他对深度优先搜索回溯算法有着非常详尽的描述2。 八皇后问题在1990年代初期的著名电子游戏《第七访客》和NDS平台的著名电子游戏《雷顿教授与不可思议的小镇》中都有出现。 解题...
2023-01-05
线性散列
线性散列 (LH) 是一种动态数据结构，它实现哈希表并一次增加或收缩一个存储桶。它是由Witold Litwin于1980年发明的。巴埃萨-耶茨和索萨-波尔曼对此进行了分析。 它是许多称为动态散列的方案中的第一个，例如拉尔森的线性散列与部分扩展，线性散列与优先级分割，线性散列与部分扩展和优先级分割，或递归线性散列。 动态散列数据结构的文件结构会适应文件大小的变化，因此避免了昂贵的定期文件重组。线性哈希文件通过拆分进行扩展 将一个预定的桶一分为二，通过将两个预定的桶合并为一个来收缩。重建的触发因素取决于方案的风格;它可能是存储桶或负载因子(记录数除以存储桶数)的溢出，超出了预定范围。 在线性哈希中有两种类型的桶，一种是要拆分的，另一种是要拆分的 已经分裂了。虽然可扩展散列只拆分溢出的存储桶，但螺旋散列(又名螺旋存储)在桶上不均匀地分布记录，例如 插入、删除或检索成本高的存储桶最早排队 进行拆分。 线性哈希也已制成可扩展的分布式数据结构 LH。在 LH 中，每个存储桶驻留在不同的服务器上。 LH 本身已扩展，可在存在 失败的存储桶。LH 和 LH 中基于键的操作(插入、删除、更新、读...
2023-01-05
爬山算法
爬山算法是一种局部择优的方法，采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。 爬山算法一般存在以下问题： 1.局部最大 2.高地：也称为平顶，搜索一旦到达高地，就无法确定搜索最佳方向，会产生随机走动，使得搜索效率降低。 3.山脊：搜索可能会在山脊的两面来回震荡，前进步伐很小。解决方法：随机重启爬山算法 原文地址：https://zh.wikipedia.org/wiki/%E7%88%AC%E5%B1%B1%E7%AE%97%E6%B3%95 在知识共享 署名-相同方式共享 3.0协议之条款下提供
2022-12-24
A*搜索算法
A*搜索算法（A* search algorithm）是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或网络游戏的BOT的移动计算上。 该算法综合了最良优先搜索和Dijkstra算法的优点：在进行启发式搜索提高算法效率的同时，可以保证找到一条最优路径（需要评估函数满足单调性）。 在此算法中，如果以{\displaystyle g(n)}表示从起点到任意顶点{\displaystyle n}的实际距离，{\displaystyle h(n)}表示任意顶点{\displaystyle n}到目标顶点的估算距离（根据所采用的评估函数的不同而变化），那么A*算法的估算函数为： {\displaystyle f(n)=g(n)+h(n)}这个公式遵循以下特性： 如果{\displaystyle g(n)}为0，即只计算任意顶点{\displaystyle n}到目标的评估函数{\displaystyle h(n)}，而不计算起点到顶点{\displaystyle n}的距离，则算法转化为使用贪心策略的最良优先搜索，速度最快，但可能得不出最优解...
