数据结构 红黑树(基于2-3树等价) (1).每一个节点或者是黑色,或者是红色 (2).根节点是黑色 (3).每一个叶子节点是黑色 (4).若是一个节点是红色的,则它的子节点必须是黑色的 (5).从任意一个节点到叶子节点,通过的黑色节点是同样多的 2022-06-28 浏览(247) 评论(0) 阅读全文
数据结构 2-3查找树 2-结点,含有一个键(及其对应的值)和两条链接,左链接指向的2-3树中的键都小于该结点,右链接指向的2-3树中的键都大于该结点。3-结点,含有两个键(及其对应的值)和三条链接,左链接指向的2-3树中的键都小于该结点,中链接指向的2-3树中的键都位于该结点的两个键之间,右链接指向的2-3树中的键都大于该结点。... 2022-06-24 浏览(179) 评论(0) 阅读全文
数据结构 AVL平衡二叉搜索树 AVL树定义如下:是平衡二叉树或者是一棵空树,或者是具有以下性质的二叉排序树:1.每个节点的平衡因子只可能是1、0、-1(绝对值≤1,如果超过1,称之为“失衡”)2.每个节点的左右子树高度差不超过13.因为每个结点的高度差不超过1,AVL树搜索、添加、删除的时间复杂度是O(logn)...... 2022-06-24 浏览(269) 评论(0) 阅读全文
数据结构 字典树(Tire) 字典树,又称单词查找树,Tire树,是一种树形结构,是一种的哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串) 2022-06-17 浏览(276) 评论(0) 阅读全文
数据结构 最大索引堆(IndexMaxHeap) 索引堆是对堆这种数据结构的优化,是利用真正元素的索引值来组成一个堆,可以映射出一个最大堆或者最小堆,索引堆可分为最大索引堆(IndexMaxHeap)和最小索引堆(IndexMinHeap)。 2022-06-11 浏览(173) 评论(0) 阅读全文
数据结构 线段树(SegmentTree) 线段树(segmenttree)顾名思义,是用来存放给定区间(segmentorinterval)内对应信息的一种数据结构。 2022-06-11 浏览(313) 评论(0) 阅读全文
数据结构 优先队列和堆 优先队列也是一种队列,只不过不同的是,优先队列的出队顺序是按照优先级来的;在有些情况下,可能需要找到元素集合中的最小或者最大元素,可以利用优先队列ADT(Abstract Data Type)来完成操作 2021-08-03 浏览(499) 评论(0) 阅读全文
数据结构 二叉树与二叉搜索树 二叉树也是一种动态的数据结构。每个节点只有两个叉,也就是两个孩子节点,分别叫做左孩子,右孩子,而没有一个孩子的节点叫做叶子节点。每个节点最多有一个父亲节点,最多有两个孩子节点(也可以没有孩子节点或者只有一个孩子节点)。 2021-07-15 浏览(548) 评论(0) 阅读全文
数据结构 最基础的动态数据结构:链表 链表是一种线性结构,也是最基础的动态数据结构。我们在实现动态数组、栈以及队列时,底层都是依托的静态数组,靠resize来解决固定容量的问题,而链表是真正的动态数据结构。 2021-07-13 浏览(457) 评论(0) 阅读全文