数据结构:二叉排序树(二叉查找树)

说明

二叉排序树(Binary Sort Tree),又称 二叉查找树,是一颗空树,或者是具有如下性质的二叉树:

  1. 若它的左子树不空,则 左子树 上所有结点的值 均小于 它的根结点的值;

  2. 若它的右子树不空,则 右子树 上所有结点的值 均大于 它的根结点的值;

  3. 它的 左、右子树又分别为二叉排序树

下图是一颗典型的二叉排序树:

优点

查找速度快

在线演示

有如下 无序序列

通过下面网址:
https://www.cs.usfca.edu/~galles/visualization/BST.html

体验放入到 二叉排序树的过程

第一步:插入 8 作为根结点。

第二步:插入 3 ,与根结点 8 进行比较,发现比8小,且根结点没有左孩子,则将 3 插入到 8 的左孩子。

第三步:插入10,首先与根结点比较,发现比 8 大,则要将 10 插入根结点的右子树;根结点 8 的右子树为空,则将 10 作为 8 的右孩子。

第四步:插入 1,首先与根结点比较,比根结点小,则应插入根结点的左子树。再与根结点的左孩子 3 比较,发现比 3 还小,则应插入 3 的左孩子。

第五步:插入 6,先与根结点8比较,小于 8,向左走;再与 3 比较,大于 3,向有走,没有结点,则将6 作为3的右孩子。

第六步:插入14,先与8比较,比 8 大,向右走;再与8的右孩子10比较,比10大,向右走,没有结点,则将14作为10的右孩子。

第七步:插入4,先与8比较,发现比8小,向左走,再与3比较,比3大向右走,再与6比较,向左走且没有左孩子,将4作为6的左孩子。

第八步:插入7,先与8比较,发现比8小,向左走,再与3比较,向右走,在与6比较,继续向右走,发现6没有右孩子,则将7作为 6的右孩子插入。

第九步:插入13,先与8比较(大于)向右,再与10比较(大于)向右,再与14比较(小于)向左,发现14的左孩子为空,则将13插入到14的左孩子位置。

二叉排序树的查找

查找值为 13 的结点:

第一步:访问根结点 8

第二步:根据二叉排序树的左子树均比根结点小,右子树均比根结点大的性质, 13 > 8 ,因此值为13的结点可能在根结点 8 的右子树当中,我们查看根结点的右子节点 10 :

第三步:与第二步相似, 13 > 10 ,因此查看结点 10 的右孩子 14 :

第四步:根据二叉排序树的左子树均比根结点小,右子树均比根结点大的性质, 13 < 14 ,因此查看 14 的左孩子 13 ,发现刚好和要查找的值相等:

查找最大最小元素

从根节点一直往左走,直到无路可走就可得到最小值
从根节点一直往右走,直到无路可走,就可以得到最大值

缺点

当数据,按照 顺序存放 时,如下:

存放 2、3、5、7、6、8

会退化成 链表 ,查询效率降低,如下:

查找元素 68 时,效率降低

参考:
https://mp.weixin.qq.com/s/9-M9V12JBl41PiygZUgJ_w
https://blog.csdn.net/gu_zhang_w/article/details/107372917
https://blog.csdn.net/yixianfeng41/article/details/52802855


原文出处:https://malaoshi.top/show_1IX3cJo0to5t.html