二分搜索树
一、概念及其介绍
二分搜索树(英语:Binary Search Tree),也称为 二叉查找树 、二叉搜索树 、有序二叉树或排序二叉树。
满足以下几个条件:
若它的左子树不为空,左子树上所有节点的值都小于它的根节点。
若它的右子树不为空,右子树上所有的节点的值都大于它的根节点。
它的左、右子树也都是二分搜索树。
如下图所示:
二、适用说明
二分搜索树有着高效的插入、删除、查询操作。
平均时间的时间复杂度为 O(log n),最差情况为 O(n)。二分搜索树与堆不同,不一定是完全二叉树,底层不
容易直接用数组表示故采用链表来实现二分搜索树。
下面先介绍数组形式的二分查找法作为思想的借鉴,后面继续介绍二分搜索树的查找方式。
三、二分查找法过程图示
二分查找法的思想在 1946 年提出,查找问题是计算机中非常重要的基础问题,对于有序数列,才能使用二
分查找法。如果我们要查找一元素,先看数组中间的值 V 和所需查找数据的大小关系,分三种情况: