数据结构七：二叉搜索树

 

二叉搜索树是用于表示动态集 的一种数据结构。

 

定义：二叉搜索树具有如下性质，或是一颗空树：

（1） 若左子树不空，则左子树上所有结点关键字都小于根节点关键字；

（2） 若右子树不空，则右子树上所有结点关键字都大于根节点关键字；

（3） 左右子树也分别是二叉搜索树。

 

性质：中序遍历一棵二叉搜索树，得到一个以关键字递增的有序序列。

 

二叉搜索的树的搜索和修改操作所需时间取决于树的高度，有n个元素的树高度最大可达到n，这称为退化树形。这样最坏情况下搜索和修改需要时间O(n)。

但二叉搜索树的平均高度即搜索和修改的平均时间为O(logn)。