导入
二叉搜索树（BST）简介
让我们来学习二叉搜索树。
什么是二叉搜索树（BST）？
二叉搜索树（BST）是一种特殊的二叉树，其中节点按如下规则有序排列：
- 左子节点的键值小于其父节点的键值。
- 右子节点的键值大于其父节点的键值。
- 不允许存在重复的键值。
通过下图可以更直观地理解二叉搜索树的结构：
...
二叉搜索树示例
在此图中，左子树中的所有数据均小于根节点 6，右子树中的所有数据均大于根节点 6。这一性质对树中的每一个节点都成立。
一些重要说明
在继续学习之前，请牢记以下几点：
- 树的节点中可能包含独立的键（key）和值（value）两个字段。但为了简化问题，我们通常将节点的值视为键。
- 所有关于二叉搜索树的问题都基于这样一个前提：节点中的值即为该树的键。
- 由于二叉搜索树本质上也是二叉树，因此适用于二叉树的所有算法（前一章已介绍）同样适用于二叉搜索树。