数据结构与算法：二叉查找树

欢迎大家来到IT世界,在知识的湖畔探索吧!

一、定义

二叉查找树(binary search tree)，二叉查找树在二叉树的基础上增加了以下几个条件：

如果左子树不为空，则左子树上所有节点的值均小于根节点的值；

如果右子树不为空，则右子树上所有节点的值均大于根节点的值；

左、右子树也都是二叉查找树。

二叉查找树要求左子树小于父节点，右子树大于父节点，正是这样保证了二叉树的有序性。 因此二叉查找树还有另一个名字——二叉排序树（binary sort tree）。

二、查找

例如查找值为4的节点，步骤如下：

1. 访问根节点6，发现4<6；

2. 访问节点6的左孩子节点3，发现4>3；

3. 访问节点3的右孩子节点4，发现4=4，这正是要查找的节点。

对于一个节点分布相对均衡的二叉查找树来说，如果节点总数是n，那么搜索节点的时间复杂度就是O(logn)，和树的深度是一样的。这种方式正是二分查找思想。

三、插入

例如插入新元素5，步骤如下：

1. 访问根节点6，发现5<6；

2. 访问节点6的左孩子节点3，发现5>3；

3. 访问节点3的右孩子节点4，发现5>4；

4. 5最终会插入到节点4的右孩子位置。