二叉排序树(Binary Sort Tree),也称为二叉查找树，它是一种特殊结构的二叉树。特点如下：

1.若左子树非空，则左子树上所有的节点的值都小于其根节点的值；

2.若右子树非空，则右子树上所有的节点的值都大于其根节点的值；

3.左右子树都是二叉排序树。

特点:

1.最好情况下的算法时间复杂度为O(1)，最坏情况下的算法时间复杂度为O(n)；

2.二叉排序树的中序遍历非递减序列；

3.查找，删除，插入的效率比较高

代码:

class Node:
    def __init__(self, data):
        self.data = data
        self.lchild = None
        self.rchild = None


class BST:
    def __init__(self, node_list):
        self.root = Node(node_list[0])
        for data in node_list[1:]:
            self.insert(data)

    # 搜素
    def search(self, node, parent, data):
        if node is None:
            return False, node, parent
        if node.data == data:
            return True, node, parent
        if node.data > data:
            return self.search(node.lchild, node, data)
        else:
            return self.search(node.rchild, node, data)

    # 插入数据
    def insert(self, data):
        flag, n, p = self.search(self.root, self.root, data)
        if not flag:
            new_node = Node(data)
            if data > p.data:
                p.rchild = new_node
            else:
                p.lchild = new_node

    # 删除
    def __delete__(self, root, data):
        flag, n, p = self.search(self.root, self.root, data)
        if flag is False:
            print('删除失败')
        else:
            if n.lchild is None:
                if n == p.lchild:
                    p.lchild = n.rchild
                else:
                    p.rchild = n.rchild
                del p
            elif n.rchild is None:
                if n == p.lchild:
                    p.lchild = n.lchild
                else:
                    p.rchild = n.lchild
                del p
            else:  # 左右子树都不为空
                pre = n.rchild
                if pre.lchild is None:
                    n.data = pre.data
                    n.rchild = pre.rchild
                    del pre
                else:
                    next = pre.lchild
                    while next.lchild is not None:
                        pre = next
                        next = next.lchild
                    n.data = next.data
                    pre.lchild = next.rchild
                    del p



    # 中序遍历方式实现排序
    def inOrder(self, node):
        if node is not None:
            self.inOrder(node.lchild)
            print(node.data, end=' ')
            self.inOrder(node.rchild)

if __name__ == '__main__':
    a = [49, 38, 65, 97, 60, 76, 13, 27, 5, 1]
    bst = BST(a)
    print('排序之前:')
    for i in a:
        print(i,end=' ')
    print('
排序之后:')
    bst.inOrder(bst.root)
    print('
删除一个节点:')
    bst.__delete__(bst.root,65)
    bst.inOrder(bst.root)
    print('
插入元素:')
    bst.insert(77)
    bst.inOrder(bst.root)

运行结果:

排序之前:
49 38 65 97 60 76 13 27 5 1 
排序之后:
1 5 13 27 38 49 60 65 76 97 
删除一个节点:
1 5 13 27 38 49 60 76 97 
插入元素:
1 5 13 27 38 49 60 76 77 97