一共13篇文章
专题：第3期
-
红黑树与2-3树详解：性质、等价性与Python实现
红黑树与2-3树详解 一、红黑树与2-3树 1. 红黑树 R-B Tree，全称是Red-Black Tree，又称为"红黑树"，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。 红黑树的特性(算法导论): （1）每个节点或者是黑色，或者是红色。 （2）根节点是黑色。 （3）每个叶子节点（NIL）是黑色。 [注意：这里叶…...- 2
- 0
-
AVL平衡二叉树详解及实现（Python版）
AVL平衡二叉树详解 一、什么是平衡二叉树？ 1. 概念 平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入…...- 5
- 0
-
并查集详解与实现优化：从Quick Find到路径压缩的完整进化过程
并查集详解与实现优化 一、什么是并查集？ 1. 基本概念 并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉…...- 5
- 0
-
Trie字典树详解 – 基础原理与代码实现
Trie字典树详解 一、什么是Trie？ 1. 定义 在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。 …...- 4
- 0
-
线段树详解：原理、构建、区间查询与更新（Python 实现）
线段树详解教程 一、什么是线段树？ 线段树也叫区间树；线段树是一种二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点； 二、为什么要使用线段树？ 在解释这个问题先让我们看一个经典的问题，区间染色； 假设有一面墙，长度为n，每次选择一段墙来进行染色，如下图所示： 首先定义一端长度为n的墙； 然后将4-9这个区间染成黄色； 在将7-15染成绿色； 再将1-5染成蓝色； 再…...- 6
- 0
-
优先队列与堆（Heap）详解：概念、实现、Heapify 与应用
优先队列与堆数据结构详解 一、什么是优先队列？ 1. 优先队列的概念 优先队列其实就是队列的一种，不过优先队列是区别于普通队列的。普通队列是一种先进先出，后进后出的数据结构，优先队列和普通队列的区别就在于，出队的顺序和入队的顺序无关，是和优先级息息相关的。 在这个场景中，由于现在计算机都是多任务执行的，我们的操作系统会动态的选择优先级最高的任务执行；因为我们无法准确预估有多少的任务需要处理，所以我…...- 6
- 0
-
映射（Map）数据结构详解：链表与二分搜索树实现（含 Python 代码与性能对比）
一、什么是映射？ 借助关键码直接查找数据元素并对其进行操作的数据结构就是映射，映射中的数据是以(key, value)的形式进行存储的，其中 key 为关键码对象，value 为具体的数据对象。生活中有很多地方都使用这样的数据结构来存储数据，比如：字典、车牌号、身份证等。 二、基于链表的映射实现 1️⃣ 定义Map接口 from abc import ABC, abstractmethod cla…...- 7
- 0
-
Python集合Set实现详解：二分搜索树vs链表性能对比 | 数据结构教程
一、什么是集合和映射？ 集合是高级数据结构的一种，它们的底层可以用多种方式来实现，就像之前的栈和队列一样。集合就像一个容器一样，我们这里实现的集合里边存储的数据是不能重复的，这样的数据结构可以帮助我们更加快速的进行统计。讲到这里是不是发现和我们之前的二分搜索树非常相似，其实这一次我们就会使用二分搜索树作为集合的底层实现。 二、二分搜索树实现集合Set 1️⃣ 实现集合Set接口 from abc …...- 5
- 0
-
二分搜索树详解｜定义、原理、代码实现与操作解析
二分搜索树详解 一、为什么要研究树结构 树结构是计算机世界中非常高效的一种数据结构，也是应用非常广泛的数据结构。 1. 什么是树结构？ 2. 树结构的应用场景 以上这些应用场景都是树型结构的使用场景，树结构的特点就是层次清晰，高效。 3. 树结构常用的类型都有什么？ 二分搜索树、平衡二叉树、线段树、Trie等都是很常用的树型数据结构。 二、二分搜索树基础 二分搜索树是树型结构中的一种，要了解二分搜…...- 13
- 0
-
栈（Stack）详解：原理、实现方法与常见应用场景
一、概念描述 栈是一种线性的数据结构 相比数组栈操作的是数组的子集 只能从一端添加元素也只能从一端取出元素(这一端称为栈顶) 栈在计算机世界里对于程序逻辑有非常重要的作用 二、Stack 1、入栈 2、出栈 通过对比可以看出栈是一种后进先出的数据结构；也就是Last In First Out，缩写为LIFO。 三、栈相关的应用场景 1、无处不在的Undo操作（撤销） 2、程序调用所使用的系统栈 d…...- 11
- 0
-
数组队列与循环队列详解：原理、时间复杂度与 Python 实现
一、数组队列 1.1 队列特点 队列也是一种线性的数据结构 相比数组，队列操作的也是数组的子集 只能从一端添加元素(队尾)，从另一端取出元素(队首) 队列是一种先进先出的数据结构 First In First Out（FIFO） 1.2 队列图示 关于队列的理解可以结合生活中的实例，比如说排队： 定义一个空的队列 从队尾开始向队列中添加元素 从队首取出元素 1.3 数组队列的基本实现 1. 定义队…...- 10
- 0
-
链表详解教程：从基础概念到Python实现 | 动态数据结构完整指南
链表详解教程 一、链表概述 链表是一种线性表，实际上是由节点（Node）组成的，一个链表拥有不定数量的节点。其数据在内存中存储是不连续的，它存储的数据分散在内存中，每个结点只能也只有它能知道下一个结点的存储位置。由N各节点（Node）组成链表，每一个Node记录本Node的数据及下一个Node。向外暴露的只有一个头节点（Head），我们对链表的所有操作，都是直接或者间接地通过其头节点来进行的。 二…...- 10
- 0