Python 数据结构入门 - 二叉搜索树（Binary Search Tree）

什么是树

树中，从一个根结点开始，每个结点都有一些它指向的子结点。除根结点外，所有结点都有父结点，根结点是所有结点的祖先。没有任何子结点的结点称为叶结点。树有很多变化，其中二叉树是每个结点最多有两个子结点的树，二叉搜索树（BST）是二叉树的一个特例。

二叉搜索树的特点

二叉搜索树是二叉树，其中每个结点的值（键）大于或等于其左子树中的所有值，并且小于其右子树中的所有值。因为二叉搜索树的特点，如果中序遍历这棵树，输出的序列就是所有关键字的正向排序。

时间复杂度

查找最小值：O(h) （h 为树的高度）

查找最大值：O(h)

出入数据：O(h)

删除数据：O(h)

搜索数据：O(h)

二叉搜索树的应用

二叉搜索树（BST）提供了一些很好的属性，可以轻松处理搜索。

动手试一试

（提示：点击交互式代码框右上角绿色三角按钮可运行代码）

下面是一个一个简单的树结点类。 它与链表结点非常相似，除了我们有两个指针指向结点的两个子结点（如果它是 None 则表示不存在）而不是单个下一个指针。

下面是一个简单的二叉搜索树的实现，先不要关心实现原理，亲自试一试各种操作吧

1. 创建一个二叉搜索树，实现出入数据，查找最大值，最小值

3. 可以根据二叉搜索树实现中对于删除元素的思路，在类 BinarySearchTree 中的 delete 函数中补充代码，实现该功能。