二叉排序树(二叉查找树)

二叉排序树的特点

一棵空树，或者是具有下列性质的二叉树：

1. 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 左、右子树也分别为二叉排序树；
4. 没有键值相等的结点。

二叉排序树的结点

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

    def __str__(self):
        return str(self.data)

二叉排序树的API

• 初始化
• 获取当前结点个数
• 插入
• 根据key查询结点
• 根据key删除结点，删除后结点后的树仍然是一棵二叉排序树

	# 二叉查找树
	class BinarySearchTree:
	    def __init__(self, key, value):
	        self.__N = 0
	        self.root = self.put(key=key, value=value)
	
	    def get_size(self):
	        return self.__N
	
	    # 插入
	    def put(self, node=None, key=None, value=None):
	        # 如果树为空
	        if node is None:
	            self.__N += 1
	            return Node(key, value)
	        # 如果树不为空
	        # key与node的key比较，小于则放在左子树，大于放在右子树,等于则替换value
	        if key < node.key:
	            node.left = self.put(node.left, key, value)
	            return node
	        elif key > node.key:
	            node.right = self.put(node.right, key, value)
	            return node
	        else:
	            node.value = value
	            return node
	
	    # 根据key查询
	    def get(self, node, key):
	        if node is None:
	            return None
	        if key < node.key:
	            return self.get(node.left, key)
	        elif key > node.key:
	            return self.get(node.right, key)
	        else:
	            return node.value
	
	    # 根据key删除节点
	    def delete(self, node, key):
	        if node is None:
	            return None
	        if key < node.key:
	            node.left = self.delete(node.left, key)
	        elif key > node.key:
	            node.right = self.delete(node.right, key)
	        else:
	            # 删除节点就是需要将右子树的最小节点替换删除节点、
	            if node.right is None:
	                self.__N -= 1
	                return node.left
	            elif node.left is None:
	                self.__N -= 1
	                return node.right
	            else:
	                min_node = node.right
	                # 遍历右子树的最小节点
	                while min_node.left is not None:
	                    min_node = min_node.left
	                # 删除最小节点
	                d = node.right
	                while d.left is not None:
	                    if d.left.left is None:
	                        d.left = None
	                    else:
	                        d = d.left
	                # node节点的左子树成为min_node左子树
	                min_node.left = node.left
	                # node节点的右子树成为min_node右子树
	                min_node.right = node.right
	                # node父节点指向min_node
	                node = min_node
	            	self.__N -= 1
	            	return node
	            

2-3树

红黑树

B树和B+树

平衡二叉树(AVL)

哈夫曼树

并查集