• 二分搜索树是二叉树
  • 二分搜索树的每个节点的值都大于其左子树上所有节点的值，小于右子树所有节点的值
  • 存储的元素必须有可比较性
  • 每一个子树都是二分搜索树

image.png

添加元素

  1. class Node:
  2.     def __init__(self, key=None, value=None, left=None, right=None):
  3.         self.key = key
  4.         self.value = value
  5.         self.left = left
  6.         self.right = right
  8.     def new(self, key=None, value=None, left=None, right=None):
  9.         self.key = key
  10.         self.value = value
  11.         self.left = left
  12.         self.right = right
  15. class BST:
  16.     """
  17.     二分搜索树
  18.     """
  19.     def __init__(self):
  20.         # 根节点
  21.         self.root = None
  22.         # 树的大小
  23.         self.count = 0
  25.     def size(self):
  26.         # 返回树大小
  27.         return self.count
  29.     def is_empty(self):
  30.         # 是否为空树
  31.         return self.count == 0
  33.     # 添加元素
  34.     def insert_r(self, key, value):
  35.         # 递归实现
  36.         self.root = self.__insert_r(self.root, key=key, value=value)
  38.     def __insert_r(self, node: Node, key, value)->Node:
  39.         """
  40.         插入元素 不存在重复元素 如果插入的元素存在 替换即可
  41.         递归插入
  42.         :param node: 子树的根
  43.         :param key:  键
  44.         :param value: 值
  45.         :return: 当前树
  46.         """
  47.         if node is None:
  48.             # 上一个节点的子树为空 可以进行插入操作 OR Root
  49.             self.count += 1
  50.             return Node(key=key, value=value)
  51.         # 存在该键 替换值
  52.         if key == node.key:
  53.             node.value = value
  54.         elif key < node.key:
  55.             # 应该存储在当前节点的左子树分支
  56.             node.left = self.__insert_r(node.left, key, value)
  57.         else:
  58.             # 应该存储在当前节点的右子树分支
  59.             node.right = self.__insert_r(node.right, key, value)
  60.         # 返回这个节点
  61.         return node
  63.     def insert(self,key,value):
  64.         # 非递归实现
  65.         if self.root is None:
  66.             # 根节点
  67.             self.root = Node(key,value)
  68.         else:
  69.             # 当前遍历的节点
  70.             node = self.root
  71.             # 上一个节点
  72.             pre = self.root
  73.             is_break =False
  74.             while (node is not None):
  75.                 pre = node
  76.                 if key<node.key:
  77.                     # 应该插入到左子树
  78.                     node = node.left
  79.                 elif key>node.key:
  80.                     # 应该插入到右子树
  81.                     node = node.right
  82.                 else:
  83.                     # 替换值
  84.                     node.value = value
  85.                     is_break = tree
  86.                     break
  88.             if not is_break:
  89.                 if key<pre.value:
  90.                     pre.left = Node(key,value)
  91.                 else:
  92.                     pre.right = Node(key, value)
  94.     # 是否包含该元素
  95.     def contain(self, key):
  96.         return self.__contain(self.root, key)
  98.     def __contain(self, node: Node, key) -> bool:
  99.         # 没有节点则直接返回
  100.         if node is None:
  101.             return False
  103.         if key == node.key:
  104.             return True
  105.         elif key < node.key:
  106.             # 在左子树中查找
  107.             return self.__contain(node.left, key)
  108.         else:
  109.             # 在右子树中查找
  110.             return self.__contain(node.right, key)
  112.     # 查找元素
  113.     def search(self, key):
  114.         return self.__search(self.root, key)
  116.     def __search(self, node: Node, key):
  117.         if node is None:
  118.             return None
  120.         if key == node.key:
  121.             return node.value
  122.         elif key < node.key:
  123.             return self.__search(node.left, key)
  124.         else:
  125.             return self.__search(node.right, key)

二分搜索树的遍历

深度

image.png

  • 前序遍历

5 3 6 8 4 2 

  1.     # 前序遍历
  2.     def pre_order_r(self):
  3.         # 递归实现遍历
  4.         self.__pre_order(self.root)
  6.     def __pre_order(self, node: Node):
  7.         if node is not None:
  8.             # 先打印当前节点的值
  9.             print(node.key)
  10.             # 后遍历左子树的值
  11.             self.__pre_order(node.left)
  12.             # 再遍历右子树的值
  13.             self.__pre_order(node.right)
  15.     def pre_order(self):
  16.         # 非递归前序遍历
  17.         stacks = [self.root]
  18.         while len(stacks) >0:
  19.             cur_node = stacks.pop()
  20.             print(cur_node.value)
  21.             if cur_node.right is not None:
  22.                 stacks.append(cur_node.right)
  23.             if cur_node.left is not None:
  24.                 stacks.append(cur_node.left)

  • 中序遍历

    1. # 中序遍历
    2.   def in_order_r(self):
    3.       # 递归实现
    4.       self.__in_order_r(self.root)
    6.   def __in_order_r(self, node: Node):
    7.       if node is not None:
    8.           self.__in_order_r(node.left)
    9.           print(str(node.key) + " ", end="")
    10.           self.__in_order_r(node.right)
    12.   def in_order(self):
    13.       stacks = []
    14.       cur_node = self.root
    16.       while cur_node is not None or len(stacks) > 0:
    17.           if cur_node is not None:
    18.               # 如果是有左边
    19.               stacks.append(cur_node)
    20.               cur_node = cur_node.left
    21.           else:
    22.               # 左子树为空 出
    23.               pop_node = stacks.pop()
    24.               print(pop_node.value, end=" ")
    25.               cur_node = pop_node.right

  • 后序遍历

    1. # 后序遍历递归
    2.   def post_order_r(self):
    3.       self.__post_order_r(self.root)
    5.   def __post_order_r(self, node: Node):
    6.       if node is not None:
    7.           self.__post_order_r(node.left)
    8.           self.__post_order_r(node.right)
    9.           print(node.key, end=" ")

    广度

    1.   def level_order(self):
    2.       qlist = Queue(maxsize=100)
    3.       qlist.put(self.root)
    4.       while (not qlist.empty()):
    5.           node = qlist.get()
    6.           print(node.key)
    7.           if node.left is not None:
    8.               qlist.put(node.left)
    9.           if node.right is not None:
    10.               qlist.put(node.right)

    查询以及删除

    1.   #  查找最小值 最小值一定在左子树最左面
    2.   def mininum(self):
    3.       assert self.count > 0, "tree mast has value"
    4.       mininode = self.__mininum(self.root)
    5.       return mininode.key
    7.   def __mininum(self, node: Node):
    8.       if node.left is None:
    9.           return node
    11.       return self.__mininum(node.left)
    13.   #  查找最大值 最大值一定是在右子树最右面
    14.   def maxnum(self):
    15.       assert self.count > 0, "tree mast has value"
    16.       maxinode = self.__maxinum(self.root)
    17.       return maxinode.key
    19.   def __maxinum(self, node: Node):
    20.       if node.right is None:
    21.           return node
    23.       return self.__maxinum(node.right)
    25.   # 删除最小值
    26.   def removeMin(self):
    27.       if self.root is not None:
    28.           self.root = self.__removeMin(self.root)
    30.   def __removeMin(self, node: Node):
    31.       # 已经是最小值
    32.       if node.left is None:
    33.           # 可能存在左子树
    34.           right_node = node.right
    35.           del node
    36.           self.count -= 1
    37.           return right_node
    38.       # 删除后 最小节点的子树肯定是小于当前节点 故放left
    39.       node.left = self.__removeMin(node.left)
    40.       return node
    42.   # 删除最大值
    43.   def removeMax(self):
    44.       if self.root is not None:
    45.           self.root = self.__removeMax(self.root)
    47.   def __removeMax(self, node: Node):
    48.       # 已经是大小值
    49.       if node.right is None:
    50.           left_node = node.left
    51.           del node
    52.           self.count -= 1
    53.           return left_node
    54.       # 删除后 最大节点的子树肯定是大于当前节点 故放right
    55.       node.right = self.__removeMax(node.right)
    56.       return node
    58.   """
    59.   删除任意节点
    60.       删除左右都有孩子的节点 d
    61.       找到后继即d右节点的最小值(并删除) 代替当前节点d
    63.   """
    65.   def removeNode(self, key):
    66.       self.__removeNode(self.root, key)
    68.   def __removeNode(self, node: Node, key):
    69.       if node is None:
    70.           return None
    72.       if key < node.key:
    73.           # 继续从左子树中查找
    74.           node.left = self.__removeNode(node.left, key)
    75.           return node
    76.       elif key > node.key:
    77.           # 继续从右子树中查找
    78.           node.right = self.__removeNode(node.right, key)
    79.           return node
    80.       else:
    81.           # 找到了要删除的点
    82.           if node.left is None:
    83.               right_node = node.right
    84.               del node
    85.               self.count -= 1
    86.               return right_node
    88.           if node.right is None:
    89.               left_node = node.left
    90.               del node
    91.               self.count -= 1
    92.               return left_node
    94.               #  左右子树都不为空
    95.           if node.left is not None and node.right is not None:
    96.               # 找到当前节点下二叉树的最小值 要替换到当前位置
    97.               minNode = self.__mininum(node.right)
    98.               minNode.right = self.__removeMin(node.right)
    99.               minNode.left = node.left
    100.               del node
    101.               self.count -= 1
    102.               return minNode

    基于二分搜索树和链表实现集合

    ```python from binary_tree import BST from linked_list import LinkedList

使用二分搜索树实现Set 集合

class SetTree:

  1. # 基于二分搜索树的集合实现
  2. def __init__(self):
  3.     self.bst = BST()
  5. def add(self, key, value):
  6.     self.bst.insert_r(key,value)
  8. def delete(self, key):
  9.     self.bst.removeNode(key)
  11. def get_size(self):
  12.     return self.bst.size()
  14. def is_empty(self):
  15.     return self.bst.is_empty()
  17. def c(self,key):
  18.     return self.bst.contain(key)

class SetLinked:

  1. # 基于链表的集合实现
  2. def __init__(self):
  3.     self.list = LinkedList()
  5. def add(self, key):
  6.     if not self.contains(key):
  7.         self.list.add_first(key)
  9. def delete(self, key):
  10.     self.list.remove(key)
  12. def get_size(self):
  13.     return self.list.get_size()
  15. def is_empty(self):
  16.     return self.list.is_empty()
  18. def contains(self,key):
  19.     return self.list.contains(key)

``` 在集合中是没有重复元素的,集合中常见的操作就是添加，删除，查找，其时间复杂度分析如下：

  • 二分搜索树实现的集合

新增O(h） h 表示层数
删除O(h) h 表示层数
查找O(h) h 表示层数
其中h和节点个数的关系（满二叉树为例） h = log2(n+1) 所以整体复杂度为O(log2n)

  • 链表实现集合

新增O(n） 确保元素没有重复，需要在添加之前遍历查找是否存在。
删除O(n)
查找O(n）