二叉排序树（Binary Search Tree，简称BST），也称为二叉查找树或二叉搜索树，是一种特殊的二叉树，具有以下主要特点：
-
节点的排序规则：
- 每个节点包含一个键及其关联的值。
- 对于树中的任意节点X，其左子树中的所有节点的键都小于节点X的键。
- 对于树中的任意节点X，其右子树中的所有节点的键都大于节点X的键。
-
动态数据结构：
- 二叉排序树是一个动态数据结构，可以在维护其排序特性的同时，允许插入和删除节点。
-
查找效率：
- 在平衡的二叉排序树中，查找效率较高，时间复杂度为O(log n)，其中n是树中节点的数量。不过在最坏的情况下（如树退化成链表），查找效率会降低到O(n)。
-
中序遍历有序：
- 对二叉排序树进行中序遍历（左子树—根节点—右子树）将得到一个有序的节点序列。
-
用途广泛：
- 由于其查找、插入和删除操作的效率，在很多情况下都非常有用，如在实现映射（Map）和集合（Set）数据结构中。
-
不一定是平衡的：
- 标准的二叉排序树不自动保证树的平衡，因此可能需要额外的算法或数据结构（如AVL树、红黑树）来保证操作的效率。
例题：
利用逐点插入建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，要查找元素 30 要进行几次元素间的比较？
要确定查找元素30在二叉排序树中需要进行多少次比较，首先需要根据给定的序列建立二叉排序树。序列是：50，72，43，85，75，20，35，45，65，30。
我们按照序列逐点插入的方式来建立二叉排序树：
- 插入50，它成为根节点。
- 插入72，它比50大，放在50的右子节点。
- 插入43，它比50小，放在50的左子节点。
- 插入85，它比50大，也比72大，放在72的右子节点。
- 插入75，它比50大，比72大，但比85小，放在85的左子节点。
- 插入20，它比50小，也比43小，放在43的左子节点。
- 插入35，它比50小，比43小，但比20大，放在20的右子节点。
- 插入45，它比50小，比43小，比20大，也比35大，放在35的右子节点。
- 插入65，它比50大，比72小，放在72的左子节点。
- 插入30，它比50小，比43小，比20大，比35小，放在35的左子节点。
现在，查找元素30的过程是：
- 与根节点50比较，30小于50，向左走。
- 与左子节点43比较，30小于43，向左走。
- 与43的左子节点20比较，30大于20，向右走。
- 与20的右子节点35比较，30小于35，向左走。
- 与35的左子节点30比较，找到目标。
因此，总共进行了5次比较。
