二叉排序树(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次比较。