二叉排序树(BST)

定义

二叉排序树是一种特殊的二叉树，其中左子树中的所有节点都小于根节点，右子树中的所有节点都大于根节点（如下图所示）。
因此构造过程需要确保插入的元素能够按照这个规则被正确地插入到树中

性质

1、如果初始状态是一个空树，则插入每个元素的时间复杂度是 O(log n)，其中 n 是树中节点的数量。这是因为每次插入元素时，都需要从根节点开始，按照比较规则找到合适的位置插入，而树的高度是 log n！
2、如果初始状态的树不平衡，比如退化成链表，那么插入每个元素的时间复杂度可能接近 O(n)，于是便有平衡树的诞生！
3、查找最小值，一直遍历左节点即可，反之则一直遍历右节点；若要查询元素x，可类比二分！
4、如果要删除节点的话。有两种情况：①若node有左子树，找到左子树的的最右边叶子节点r，把node的右子树作为r的右子树，用node的左孩子代替node;②若node没有左子树直接用node的右孩子代替node！

代码实现

# 二叉排序树的构建（BST）

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


class Tree:
    def __init__(self, root):
        self.root = root

    def create_bst(self, a):
        def dfs(x):
            node = Node(x)
            if self.root.data == -1:
                self.root = node
                return
            head = self.root
            while 1:
                if x < head.data:
                    if not head.left:
                        head.left = node
                        return
                    else:
                        head = head.left
                else:
                    if not head.right:
                        head.right = node
                        return
                    else:
                        head = head.right

        for x in a:
            dfs(x)

    def printf(self):
        def dfs(root):
            if not root:
                return
            dfs(root.left)
            print(root.data)
            dfs(root.right)

        dfs(self.root)


a = [9,8,7,6,5,4,3,2,1]
mytree = Tree(Node(-1))
mytree.create_bst(a)
mytree.printf()