二分搜索树(Binary Search Tree)
一.概念及其介绍
- 概念
- 二分搜索树（英语：Binary Search Tree），也称为 二叉查找树 、二叉搜索树 、有序二叉树或排序二叉树。满足以下几个条件：
- 每个节点的键值大于左孩子
- 每个节点的键值小于右孩子
- 以左右孩子为根的子数仍然为二分搜索树
- 优点
- 可以高效的查找数据，还可以高效的插入，删除，及动态维护数据
二分搜索树有着高效的插入、删除、查询操作。
平均时间的时间复杂度为 O(log n)，最差情况为 O(n)。二分搜索树与堆不同，不一定是完全二叉树，底层不容易直接用数组表示故采用链表来实现二分搜索树。
二. 操作：二分搜索树
- 插入操作(insert)
- 数据的查找(Search)
- 二分搜索树的包含(Contain)
- 二分搜索树的遍历
- 二分搜索树节点删除