二叉搜索树

二叉搜索树

二叉搜索树(Binary Search Tree),它或者是一棵空树,或者是具有下列性质的二叉树:

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值
  • 它的左、右子树也分别为二叉搜索树

特点与应用场景

二叉搜索树作为一种经典的数据结构,能高效的进行以下操作:

  • 插入一个数值
  • 查询是否包含某个数值
  • 删除某个数值

不论哪一种操作,所花的时间都和树的高度成正比。因此,如果共有n个元素,那么平均每次操作需要O(logn)的时间。 所以应用十分广泛,例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

中序遍历

二叉树的中序遍历即按照访问左子树——根结点——右子树的方式遍历二叉树;
由二叉搜索树的性质可知:二叉搜索树的中序遍历是按照键增加的顺序进行的。

总结

二叉搜索树的节点查询、构造和删除性能,与树的高度相关,如果二叉搜索树能够更“平衡”一些,避免了树结构向线性结构的倾斜,则能够显著降低时间复杂度。二叉搜索树的存储方面,相对于线性结构只需要保存元素值,树中节点需要额外的空间保存节点之间的父子关系,所以在存储消耗上要高于线性结构。