|
二叉搜索树是用于表示动态集 的一种数据结构。
定义：二叉搜索树具有如下性质，或是一颗空树：
（1） 若左子树不空，则左子树上所有结点关键字都小于根节点关键字；
（2） 若右子树不空，则右子树上所有结点关键字都大于根节点关键字；
（3） 左右子树也分别是二叉搜索树。
性质：中序遍历一棵二叉搜索树，得到一个以关键字递增的有序序列。
二叉搜索的树的搜索和修改操作所需时间取决于树的高度，有n个元素的树高度最大可达到n，这称为退化树形。这样最坏情况下搜索和修改需要时间O(n)。
但二叉搜索树的平均高度即搜索和修改的平均时间为O(logn)。
|
|
|
