二叉排序树(BST) |
您所在的位置：网站首页 › 二叉排序树充要条件 › 二叉排序树(BST) |
二叉排序树(BST)
|
定义
二叉排序树是一种特殊的二叉树，其中左子树中的所有节点都小于根节点，右子树中的所有节点都大于根节点（如下图所示）。
因此构造过程需要确保插入的元素能够按照这个规则被正确地插入到树中
1、如果初始状态是一个空树，则插入每个元素的时间复杂度是 O(log n)，其中 n 是树中节点的数量。这是因为每次插入元素时，都需要从根节点开始，按照比较规则找到合适的位置插入，而树的高度是 log n！ 2、如果初始状态的树不平衡，比如退化成链表，那么插入每个元素的时间复杂度可能接近 O(n)，于是便有平衡树的诞生！ 3、查找最小值，一直遍历左节点即可，反之则一直遍历右节点；若要查询元素x，可类比二分！ 代码实现 # 二叉排序树的构建（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): for x in a: self.insert_node(x) def insert_node(self, data): node = Node(data) if self.root.data == -1: self.root = node return head = self.root while 1: if data < 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 def delete_node(self, data): # 定位节点及其父节点的位置 cur = self.root left_flag = True pa = self.root while cur.data != data: if data |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |