数据结构与算法 树(B树,B+树,红黑树待完善)

简介: 数据结构与算法 树(B树,B+树,红黑树待完善)

二叉树的介绍

二叉树的节点代码
class TreeNode:
    def __init__(self, value) -> None:
        self.val = value
        self.left = None
        self.right = None
  • 节点的「深度 depth」:从根节点到该节点所经过的边的数量。
  • 节点的「高度 height」:从最远叶节点到该节点所经过的边的数量。
二叉树的类型
  • 「完美二叉树 perfect binary tree」除了最底层外,其余所有层的节点都被完全填满。在完美二叉树中,叶节点的度为 0 ,其余所有节点的度都为 2 ;若树高度为 ℎ ,则节点总数为 2n+1−1 ,呈现标准的指数级关系,反映了自然界中常见的细胞分裂现象。

  • 「完全二叉树 complete binary tree」只有最底层的节点未被填满,且最底层节点尽量靠左填充。

  • 「完满二叉树 full binary tree」除了叶节点之外,其余所有节点都有两个子节点。

  • 「平衡二叉树 balanced binary tree」中任意节点的左子树和右子树的高度之差的绝对值不超过 1 。

链表二叉树的遍历

层序遍历(广度优先遍历breadth‑first traversal) BFT/BFS

从顶部到底部逐层遍历二叉树,并在每一层按照从左到右的顺序访问节点。

from collections import deque
def level_order(root):
    queue = deque()
    queue.append(root)
  
    res = []
    while queue:
        node = queue.popleft()
        res.append(node.val)
        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)
    return res
前序、中序、后序遍历(深度优先遍历)DFT/DFS
  • 前序:访问优先级:根节点 -> 左子树 -> 右子树
  • 中序:访问优先级:左子树 -> 根节点 -> 右子树
  • 后序:访问优先级:左子树 -> 右子树 -> 根节点

class TreeOrder:
    def __init__(self) -> None:
        self.res = []
  
    def pre_order_need(self, root):
        if root is None:
            return None
        self.res.append(root.val)
        self.pre_order_need(root.left)
        self.pre_order_need(root.right)
  
    def pre_order(self, root):
        self.res = []
        self.pre_order_need(root)
  
    def in_order_need(self, root):
        if root is None:
            return None
        self.in_order_need(root.left)
        self.res.append(root.val)
        self.in_order_need(root.right)
  
    def in_order(self, root):
        self.res = []
        self.in_order_need(root)
  
    def post_order_need(self, root):
        if root is None:
            return None
        self.post_order_need(root.left)
        self.post_order_need(root.right)
        self.res.append(root.val)
  
    def post_order(self, root):
        self.res = []
        self.post_order_need(root)
复杂度分析
  • 时间复杂度 𝑂(𝑛) :所有节点被访问一次,使用 𝑂(𝑛) 时间。
  • 空间复杂度 𝑂(𝑛) :在最差情况下,即树退化为链表时,递归深度达到 𝑛 ,系统占用 𝑂(𝑛) 栈帧空间。

数组二叉树的构造

class ArrayTree:
    def __init__(self, arr) -> None:
        self.__tree = list(arr)
        self.res = []
  
    def size(self):
        return len(self.__tree)
    def val(self, ix):
        if ix < 0 or ix >= self.size():
            return None
        else:
            return self.__tree[ix]
    def left(self, ix):
        return 2*ix + 1
  
    def right(self, ix):
        return 2*ix + 2
    def parent(self, ix):
        return (ix -1)//2
    def level_order(self):
        self.res = []
        for i in range(self.size()):
            if self.val(i) is not None:
                self.res.append(self.val(i))
        return self.res
    def __dfs(self, ix, order):
        if self.val(ix) is None:
            return None
        if order == 'pre':
            self.res.append(self.val(ix))
        self.__dfs(self.left(ix), order)
        if order == 'in':
            self.res.append(self.val(ix))
        self.__dfs(self.right(ix), order)
        if order == 'post':
            self.res.append(self.val(ix))
  
    def pre_order(self):
        self.res = []
        self.__dfs(0, order='pre')
        return self.res
    def in_order(self):
        self.res = []
        self.__dfs(0, order='in')
        return self.res
    def post_order(self):
        self.res = []
        self.__dfs(0, order='post')
        return self.res
lst = [1,2,3,4,None,6,7,8,9,None,None,12,None,None,15]
tree = ArrayTree(lst)
tree.level_order()
tree.pre_order()
tree.in_order()
tree.post_order()
数组二叉树的优缺点

二叉树的数组表示主要有以下优点。

  • 数组存储在连续的内存空间中,对缓存友好,访问与遍历速度较快。
  • 不需要存储指针,比较节省空间。
  • 允许随机访问节点。
    然而,数组表示也存在一些局限性。
  • 数组存储需要连续内存空间,因此不适合存储数据量过大的树。
  • 增删节点需要通过数组插入与删除操作实现,效率较低。
  • 当二叉树中存在大量 None 时,数组中包含的节点数据比重较低,空间利用率较低。

二叉搜索树

「二叉搜索树 binary search tree」满足以下条件:

  1. 对于根节点,左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值。
  2. 任意节点的左、右子树也是二叉搜索树,即同样满足条件 1. 。
二叉搜索树的构造

二叉搜索树的中序遍历序列是升序的。在二叉搜索树中获取有序数据仅需 𝑂(𝑛)时间

class binary_search_tree:
    def __init__(self, root) -> None:
        self.__root = root
        self.res = []
    def search(self, num):
        cur = self.__root
        while cur is not None:
            if cur.val == num:
                return cur
            elif cur.val < num:
                cur = cur.right
            elif cur.val > num:
                cur = cur.left
        else:
            return None
    def insert(self, num):
        node = TreeNode(num)
        if self.__root is None:
            self.__root = node
        pre = None
        cur = self.__root
        while cur is not None:
            if cur.val == num:
                return ValueError('值重复')
            elif cur.val < num:
                pre = cur
                cur = cur.right
            elif cur.val > num:
                pre = cur
                cur = cur.left
        if pre.val < num:
            pre.right = node
        else:
            pre.left = node
  
    def remove(self, num):
        cur = self.__root
        pre = None
        while cur is not None:
            if cur.val == num:
                break
            elif cur.val < num:
                pre = cur
                cur = cur.right
            elif cur.val > num:
                pre = cur
                cur = cur.left
        else:
            raise ValueError('没有这个值')
        if cur.left is None or cur.right is None:
            child = cur.left or cur.right
            if pre is None:
                self.__root = None
            if pre.left == cur:
                pre.left = child
            elif pre.right == cur:
                pre.right = child
        else:
            tem = cur.left
            while tem.right is not None:
                tem = tem.right
            self.remove(tem.val)
            cur.val = tem.val
  
  
  
    def __dfs(self, node, order):
        if node is None:
            return None
        if order == 'pre':
            self.res.append(node.val)
        self.__dfs(node.left, order)
        if order == 'in':
            self.res.append(node.val)
        self.__dfs(node.right, order)
        if order == 'post':
            self.res.append(node.val)
  
    def pre_order(self):
        self.res = []
        self.__dfs(self.__root, 'pre')
        return self.res
    def in_order(self):
        self.res = []
        self.__dfs(self.__root, 'in')
        return self.res
    def post_order(self):
        self.res = []
        self.__dfs(self.__root, 'post')
        return self.res
node_1 = TreeNode(8)
node_2 = TreeNode(4)
node_3 = TreeNode(12)
node_4 = TreeNode(3)
node_5 = TreeNode(6)
node_6 = TreeNode(10)
node_7 = TreeNode(14)
  
node_1.left = node_2
node_1.right = node_3
node_2.left = node_4
node_2.right = node_5
node_3.left = node_6
node_3.right = node_7
二叉搜索树的效率

给定一组数据,我们考虑使用数组或二叉搜索树存储。观察表 7‑2 ,二叉搜索树的各项操作的时间复杂度都是对数阶,具有稳定且高效的性能表现。只有在高频添加、低频查找删除的数据适用场景下,数组比二叉搜索树的效率更高。在理想情况下,二叉搜索树是“平衡”的,这样就可以在 log 𝑛 轮循环内查找任意节点。然而,如果我们在二叉搜索树中不断地插入和删除节点,可能导致二叉树退化为图 7‑23 所示的链表,这时各种操作的时间复杂度也会退化为 𝑂(𝑛) 。

AVL树

class AVL:
    def __init__(self, root) -> None:
        self.root = root
        self.res = []
  
  
    def height(self, node):
        if node is not None:
            return node.height
        else:
            return -1
    def __update_height(self, node):
        node.height = max(node.left.height, node.right.height) + 1
  
    def balance_factor(self, node):
        if node is None:
            return 0
        else:
            return self.height(node.left) - self.height(node.right)
    def __right_rotate(self, node):
        child = node.left
        grand_child = child.right
  
        child.right = node
        node.left = grand_child
  
        self.__update_height(node)
        self.__update_height(child)
        return child
    def __left_rotate(self, node):
        child = node.right
        grand_child = child.left
  
        child.left = node
        node.right = grand_child
  
        self.__update_height(node)
        self.__update_height(child)
        return child
    def __rotate(self, node):
        balance_factor = self.balance_factor(node)
        if balance_factor > 1:
            if self.balance_factor(node.left) >= 0:
                return self.__right_rotate(node)
            else:
                node.left = self.__left_rotate(node.left)
                return self.__right_rotate(node)
        elif balance_factor < -1:
            if self.balance_factor(node.right) <= 0:
                return self.__left_rotate(node)
            else:
                node.right = self.__right_rotate(node.right)
                return self.__left_rotate(node)
        return node
    def __insert_helper(self, node, val):
        if node is None:
            return TreeNode(val)
        if val < node.val:
            node.left = self.__insert_helper(node.left, val)
        elif val > node.val:
            node.right = self.__insert_helper(node.right, val)
        else:
            return node
        self.__update_height(node)
        return self.__rotate(node)
    def insert(self, val):
        self.root = self.__insert_helper(self.root, val)
  
    def __remove_helper(self, node, val):
        if node is None:
            return None
        if val < node.val:
            node.left = self.__remove_helper(node.left, val)
        elif val > node.val:
            node.right = self.__remove_helper(node.right, val)
        else:
            if node.left is None or node.right is None:
                child = node.left or node.right
                if child is None:
                    return None
                else:
                    node = child
            else:
                temp = node.left
                while temp.right:
                    temp = temp.right
                node.left = self.__remove_helper(node.left, temp.val)
                node.val = temp.val
        self.__update_height(node)
        return self.__rotate(node)
    def remove(self, val):
        self.root = self.__remove_helper(self.root, val)
  
    def __dfs(self, node, order):
        if node is None:
            return None
        if order == 'pre':
            self.res.append(node.val)
        self.__dfs(node.left, order)
        if order == 'in':
            self.res.append(node.val)
        self.__dfs(node.right, order)
        if order == 'post':
            self.res.append(node.val)
  
    def pre_order(self):
        self.res = []
        self.__dfs(self.root, 'pre')
        return self.res
    def in_order(self):
        self.res = []
        self.__dfs(self.root, 'in')
        return self.res
    def post_order(self):
        self.res = []
        self.__dfs(self.root, 'post')
        return self.res
    def search(self, value):
        cur = self.root
        while cur:
            if cur.val == value:
                break
            elif cur.val < value:
                cur = cur.right
            elif cur.val > value:
                cur = cur.left
        else:
            raise ValueError('这个值不存在')
        return cur

重点回顾

  • 二叉树是一种非线性数据结构,体现“一分为二”的分治逻辑。每个二叉树节点包含一个值以及两个指针,分别指向其左子节点和右子节点。
  • 对于二叉树中的某个节点,其左(右)子节点及其以下形成的树被称为该节点的左(右)子树。
  • 二叉树的相关术语包括根节点、叶节点、层、度、边、高度和深度等。
  • 二叉树的初始化、节点插入和节点删除操作与链表操作方法类似。
  • 常见的二叉树类型有完美二叉树、完全二叉树、满二叉树和平衡二叉树。完美二叉树是最理想的状态,而链表是退化后的最差状态。
  • 二叉树可以用数组表示,方法是将节点值和空位按层序遍历顺序排列,并根据父节点与子节点之间的索引映射关系来实现指针。
  • 二叉树的层序遍历是一种广度优先搜索方法,它体现了“一圈一圈向外”的分层遍历方式,通常通过队列来实现。
  • 前序、中序、后序遍历皆属于深度优先搜索,它们体现了“走到尽头,再回头继续”的回溯遍历方式,通常使用递归来实现。
  • 二叉搜索树是一种高效的元素查找数据结构,其查找、插入和删除操作的时间复杂度均为 𝑂(log 𝑛) 。
  • 当二叉搜索树退化为链表时,各项时间复杂度会劣化至 𝑂(𝑛) 。
  • AVL 树,也称为平衡二叉搜索树,它通过旋转操作,确保在不断插入和删除节点后,树仍然保持平衡。
  • AVL 树的旋转操作包括右旋、左旋、先右旋再左旋、先左旋再右旋。在插入或删除节点后,AVL 树会从底向顶执行旋转操作,使树重新恢复平衡。


目录
相关文章
|
存储 算法 C++
Windows共享文件:探秘C++实现的B树索引算法奇境
在数字化时代,Windows共享文件的高效管理至关重要。B树算法以其自平衡多路搜索特性,在文件索引与存储优化中表现出色。本文探讨B树在Windows共享文件中的应用,通过C++实现具体代码,展示其构建文件索引、优化数据存储的能力,提升文件检索效率。B树通过减少磁盘I/O操作,确保查询高效,为企业和个人提供流畅的文件共享体验。
|
存储 机器学习/深度学习 监控
网络管理监控软件的 C# 区间树性能阈值查询算法
针对网络管理监控软件的高效区间查询需求,本文提出基于区间树的优化方案。传统线性遍历效率低,10万条数据查询超800ms,难以满足实时性要求。区间树以平衡二叉搜索树结构,结合节点最大值剪枝策略,将查询复杂度从O(N)降至O(logN+K),显著提升性能。通过C#实现,支持按指标类型分组建树、增量插入与多维度联合查询,在10万记录下查询耗时仅约2.8ms,内存占用降低35%。测试表明,该方案有效解决高负载场景下的响应延迟问题,助力管理员快速定位异常设备,提升运维效率与系统稳定性。
562 4
|
存储 机器学习/深度学习 算法
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty 敏感词
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty 敏感词
KMP、Trie树 、AC自动机‌ ,三大算法实现 优雅 过滤 netty  敏感词
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
945 1
|
监控 算法 安全
基于 C# 基数树算法的网络屏幕监控敏感词检测技术研究
随着数字化办公和网络交互迅猛发展,网络屏幕监控成为信息安全的关键。基数树(Trie Tree)凭借高效的字符串处理能力,在敏感词检测中表现出色。结合C#语言,可构建高时效、高准确率的敏感词识别模块,提升网络安全防护能力。
465 2
|
监控 算法 数据处理
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用,通过C++实现其构建与查询功能,显著提升多维数据处理效率。KD树作为一种二叉空间划分结构,适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法,基于KD树的方案检索效率提升2-3个数量级,但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
415 17
|
人工智能 算法 语音技术
Video-T1:视频生成实时手术刀!清华腾讯「帧树算法」终结闪烁抖动
清华大学与腾讯联合推出的Video-T1技术,通过测试时扩展(TTS)和Tree-of-Frames方法,显著提升视频生成的连贯性与文本匹配度,为影视制作、游戏开发等领域带来突破性解决方案。
691 4
Video-T1:视频生成实时手术刀!清华腾讯「帧树算法」终结闪烁抖动
|
存储 监控 算法
局域网上网记录监控的 C# 基数树算法高效检索方案研究
在企业网络管理与信息安全领域,局域网上网记录监控是维护网络安全、规范网络行为的关键举措。随着企业网络数据量呈指数级增长,如何高效存储和检索上网记录数据成为亟待解决的核心问题。基数树(Trie 树)作为一种独特的数据结构,凭借其在字符串处理方面的卓越性能,为局域网上网记录监控提供了创新的解决方案。本文将深入剖析基数树算法的原理,并通过 C# 语言实现的代码示例,阐述其在局域网上网记录监控场景中的具体应用。
353 7
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
577 3
 算法系列之数据结构-Huffman树
|
机器学习/深度学习 算法 搜索推荐
决策树算法如何读懂你的购物心理?一文看懂背后的科学
"你为什么总能收到刚好符合需求的商品推荐?你有没有好奇过,为什么刚浏览过的商品就出现了折扣通知?
473 0

热门文章

最新文章