search tree（搜索树）：一种用于高效查找、插入、删除数据的树形数据结构。常见形式是二叉搜索树（BST），其基本性质是：对任一节点，左子树的键值通常小于该节点，右子树的键值通常大于该节点（具体规则视实现而定）。在计算机科学中也可泛指用于“搜索/探索”的树结构（如博弈树、状态空间树），但最常见指数据结构意义上的搜索树。
/ˈsɝːtʃ triː/
A search tree can speed up lookups.
搜索树可以加快查找速度。
To keep the search tree balanced, the implementation rotates nodes after insertions.
为了保持搜索树的平衡，该实现会在插入后通过旋转节点来调整结构。
search 来自古法语 cerchier / serchier（“寻找、搜查”），进一步与拉丁语中表示“环绕、探索”的词根相关；tree 来自古英语 trēow（“树”）。合起来 search tree 字面意思是“用于搜索的树”，在计算机科学中引申为用树形结构组织数据，从而更快地“搜索/查找”。
Select Language