首页
学习
活动
专区
圈层
工具
发布

数据结构图解(递归,二分,AVL,红黑树,伸展树,哈希表,字典树,B树,B+树)

递归反转 二分查找 AVL树 AVL简单的理解,如图所示,底部节点为1,不断往上到根节点,数字不断累加。...观察每个节点数字,随意选个节点A,会发现A节点的左子树节点或右子树节点末尾,数到A节点距离之差不会超过1 一旦添加一个数,使得二叉树结构,存在节点两边子树差大于1,若是右子树大,则左旋;左子树大,则右旋...旋转规则关键节点就是这个A节点,右子树大,则A节点变为左子树,右子节点替代A节点位置并指向A 红黑树 节点是红色或黑色。 根节点是黑色。 每个叶子节点都是黑色的空节点(NIL节点)。...每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点) 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。...伸展树是一种自调整形式的二叉查找树,它会沿着从某个节点到树根之间的路径,通过一系列的旋转把这个节点搬移到树根去。

1.3K30

数据结构里的一棵树

高度是啥,就是从下往上到最顶端,从叶节点到根节点。 从每个叶节点开始,一个节点一个节点往上数,数到根节点,最长的那个数就是数的高度。叶节点起始为0. 上面这个树的高度是4。...2、深度 深度,顾名思义,就是从上往下到最低端,从根节点到叶节点。 从根开始,一个节点一个节点往下数,数到每个叶子节点,最长的那个数就是数的深度。根节点的起始为0. 上面这个树的深度是4。...通过【对任何一条从根到叶子节点的简单路径上的各个节点颜色进行约束】来确保【没有一路径会比其它路径长2倍】。...红黑树的特点: a)【节点要么红,要么黑】 b)【根节点是黑的】 c)【叶节点是黑的】 d)【如果一个节点是红色的,那么它的子节点是黑色的】 e)【对任何一个节点,从该节点到其所有后代叶节点的简单路径上的黑节点数据是相同的...黑高:从某个节点到达其叶节点的【任何一个(参考e】简单路径上的黑色节点个数称之为黑高。红黑树的黑高即为其根节点的黑高。

60010
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    数据结构(四):树

    特性: 没有儿子的节点称为树叶(leaf) 具有相同父亲的节点为兄弟(sibling) 在一棵树中从根到每个节点恰好存在一条路径,这条路径上边的条数称为路径的长 从根到任意节点 n 的唯一路径的长称为该节点...完满二叉树:如果二叉树的所有节点中,除叶节点外都有两个儿子,这样的二叉树称为完满二叉树 完美二叉树:如果完满二叉树的叶节点都在同一层,这样的二叉树称为完美二叉树 完全二叉树:如果二叉树从根节点到倒数第二层满足完美二叉树...delete:删除节点 插入节点的思路分析:二叉查找树节点的插入是一个沿着树的根节点递归向下查找插入位置的过程,即如果插入节点的值大于根结点,则从根结点的右儿子中查找;如果插入节点的值小于根结点,则从根结点的左儿子中查找...下面分别分析: 插入操作:可能(因为树节点的高度由左、右两个儿子中高度较大的那个决定)会改变根结点到插入节点路径上所有节点的高度;插入后要计算自身的高度和深度 删除操作:可能会改变根结点到删除节点路径上所有节点的高度...# 两步走:1.顶替节点的所有子节点深度减1; 140 # 2.如果顶替节点的父节点的高度发生变化,则更新从根到父节点路径上所有节点的高度 141 del_node =

    72030

    二叉树~之高度与深度

    我特别喜欢一个博主,大家都叫他Carl 用Carl的话说,高度与深度的区别为: 二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数。...二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数。 好了,知识点到此结束。 当然不是!接下来我用两道题,来带大家入门 二叉树的最小深度 问题:给定一个二叉树,找出其最小深度。...最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明:叶子节点是指没有子节点的节点。 /** * Definition for a binary tree node....,对以后面试也有帮助,望大家掌握 收获: 二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数。...二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数。

    46310

    文心一言 VS 讯飞星火 VS chatgpt (192)-- 算法导论14.2 2题

    红黑树的每个节点都应该包含一个颜色字段,表示节点的颜色,以及一个可能的黑高字段,表示从该节点到最底层叶子节点的路径上黑色节点的数量。...维护节点的深度相对直接,节点的深度就是从根节点到该节点的边数。在插入节点时,新节点的深度等于其父节点的深度加1。在删除节点时,需要考虑节点删除后对树结构的影响,相应地更新其他节点的深度。...5.对于每个节点,从该节点到其后代叶子节点的简单路径上,均包含相同数目的黑色节点(即具有相同的黑高)。...在插入操作中,我们计算并更新新插入节点的黑高。由于插入操作本身需要遍历树,这个过程不会增加额外的时间开销。 同样的方法也可以用来维护节点的深度。在红黑树中,节点的深度就是从根节点到该节点的路径长度。...depth 参数,它表示从根节点到插入位置的路径长度。

    75620

    整理得吐血了,二叉树、红黑树、B&B+树超齐全,快速搞定数据结构

    ,只需改变节点中的指针指向 缺点:存储空间利用率低,需通过指针维护节点间的逻辑关系;查找效率比顺序存储慢 度:当前节点下的子节点个数 二叉树 二叉树是每个节点最多有两个子树的树结构,左侧子树节点称为...image 规律总结: 失衡节点到其最底部叶子节点的高度不会超过4 失衡节点哪里不平衡就会往哪里的反向旋转 添加的节点到失衡节点的路径如果是一条直线(即LL或RR),则只需对失衡节点u进行反向旋转 添加的节点到失衡节点的路径如果是一条曲线...Tree) 红黑树是一种自平衡二叉搜索树(BST),且红黑树节点遵循以下规则: 每个节点只能是红色或黑色 根节点总是黑色的 红色节点的父或子节点都必然是黑色的(两个红色的节点不会相连) 任一节点到其所有后代...,效率自然更慢 以上也是Java 8的HashMap中树节点实现结构采用红黑树而不是AVL树的原因 删除节点 删除节点主要违反的规则是子树中黑色高度的更改,导致根节点到叶子路径的黑色高度降低。...双黑概念指当删除黑色节点后使用了另一个黑色节点替代删除节点的位置(也可以当成有两个null的黑色叶子节点因删除重叠成1个),这也意味着根节点到替代节点的原路径上少了一个黑色节点导致违反了到任一叶子节点路径上含相同的黑色节点数的节点规则

    3.9K21

    数据结构 | 树的秘密

    基本术语: 节点:树的基本组成单位 根节点:没有父节点的节点 叶子节点:没有子节点的节点 深度:从根节点到当前节点的路径长度 高度:从当前节点到最远叶子节点的路径长度 树的特点: 每个节点有零个或多个子节点...有且仅有一个根节点 除根节点外,每个节点有且仅有一个父节点 二、二叉树的实现 二叉树是最常用的树结构,每个节点最多有两个子节点(左子树和右子树)。...节点结构定义 首先,我们需要定义二叉树节点的结构。每个节点包含数据域和两个指针域,分别指向左子节点和右子节点。...创建节点:createNode函数负责为新节点分配内存并初始化。 插入操作:按照二叉搜索树的规则插入节点,即左子树的值小于根节点,右子树的值大于根节点。...,最后访问根节点 删除操作:删除节点需要考虑三种情况: 叶子节点:直接删除 只有一个子节点:用子节点替代当前节点 有两个子节点:用中序后继(右子树的最小值节点)替代当前节点 其他操作:实现了查找

    34710

    我的思念像满二叉树般疯长,每个空指针都指向你的方向——全程动画可视化数据结构算法之二叉树

    ; 操作必须从根开始 中序线索二叉树: ​ 线索二叉树的存储结构: ​ 线索二叉树的存储结构代码初始化: 先/中/后序线索二叉树同理 // 定义二叉树节点结构,采用链式存储,这种结构也被称为二叉链表...查找成功,返回结点指针; 查找失败返回NULL 递归实现的最坏空间复杂度为O(h),普通实现的最坏空间复杂度为O(1) BST的查找指定key值代码及存储结构初始化实现: // 定义二叉排序树节点结构体...查找路径上的所有结点都有可能受到影响 从插入点往回找到第一个不平衡结点,调整以该结点为根的子树 每次调整的对象都是“最小不平衡子树”在插入操作中,只要将最小不平衡子树调整平衡,则其他祖先结点都会恢复平衡...O(log2n) 哈夫曼树 带权路径长度: 结点的权:有某种现实含义的数值(如:表示结点的重要性等) 结点的带权路径长度:从树的根到该结点的路径长度(经过的边数)与该结点上权值的乘积...每个初始结点最终都成为叶结点,且权值越小的结点到根结点的路径长度越大 哈夫曼树的结点总数为2n − 1 哈夫曼树中不存在度为1的结点。

    99500

    字典树概念与题型解析

    通过之前的描述,你可以看到,其实我们每次在寻找的是一个个字符,将这个字符和之前找到过的所有字符拼接在一起就成了下一个前缀,每个字典树节点里面其实可以存放字符,然后一条由根节点往下的路径把路径上所有的节点串起来...,在树中,边其实是有方向性的,就是 parent -> child,因为除根节点外,每个节点只会有一个 parent 节点,那么就是说从根节点到树上的任意节点,只可能存在唯一的一条路径。...这条路径可以唯一地代表一个单词。 你可以看到,根节点是我们的起始点,终点可能是树中的任意节点,那么问题来了,刚刚的例子中,hel 也是一个从根节点到树中某节点的路径,但是 hel 不是单词啊。...(); boolean isWordOrNot = false; } 另外就是之前提到的一个变量,isWordOrNot,用来确定从根节点到当前节点的这条路径能不能代表一个单词。...理由也很简单,我们并不是孤立地去看待每个节点,不管是寻找单词,还是寻找前缀,我们都是从上往下去找的,children 数组的下标就已经表示下一层节点的字符了,比如我们从根节点去找 hello 的第一个字符

    69710

    字典树概念与题型解析

    通过之前的描述,你可以看到,其实我们每次在寻找的是一个个字符,将这个字符和之前找到过的所有字符拼接在一起就成了下一个前缀,每个字典树节点里面其实可以存放字符,然后一条由根节点往下的路径把路径上所有的节点串起来...,在树中,边其实是有方向性的,就是 parent -> child,因为除根节点外,每个节点只会有一个 parent 节点,那么就是说从根节点到树上的任意节点,只可能存在唯一的一条路径。...这条路径可以唯一地代表一个单词。 你可以看到,根节点是我们的起始点,终点可能是树中的任意节点,那么问题来了,刚刚的例子中,hel 也是一个从根节点到树中某节点的路径,但是 hel 不是单词啊。...(); boolean isWordOrNot = false; } 另外就是之前提到的一个变量,isWordOrNot,用来确定从根节点到当前节点的这条路径能不能代表一个单词。...理由也很简单,我们并不是孤立地去看待每个节点,不管是寻找单词,还是寻找前缀,我们都是从上往下去找的,children 数组的下标就已经表示下一层节点的字符了,比如我们从根节点去找 hello 的第一个字符

    1K20

    字典树概念与题型解析

    通过之前的描述,你可以看到,其实我们每次在寻找的是一个个字符,将这个字符和之前找到过的所有字符拼接在一起就成了下一个前缀,每个字典树节点里面其实可以存放字符,然后一条由根节点往下的路径把路径上所有的节点串起来...,在树中,边其实是有方向性的,就是 parent -> child,因为除根节点外,每个节点只会有一个 parent 节点,那么就是说从根节点到树上的任意节点,只可能存在唯一的一条路径。...这条路径可以唯一地代表一个单词。 你可以看到,根节点是我们的起始点,终点可能是树中的任意节点,那么问题来了,刚刚的例子中,hel 也是一个从根节点到树中某节点的路径,但是 hel 不是单词啊。...(); boolean isWordOrNot = false; } 另外就是之前提到的一个变量,isWordOrNot,用来确定从根节点到当前节点的这条路径能不能代表一个单词。...理由也很简单,我们并不是孤立地去看待每个节点,不管是寻找单词,还是寻找前缀,我们都是从上往下去找的,children 数组的下标就已经表示下一层节点的字符了,比如我们从根节点去找 hello 的第一个字符

    89610

    【数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】

    相关知识 为了完成本关任务,你需要掌握: 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 假设二叉树节点结构体定义如下: // 二叉树节点结构体定义 struct TreeNode...查找结点 可以通过递归的方式在二叉树中查找指定值的节点,遍历二叉树的每个节点,比较节点值与目标值是否相等。...// 在二叉树中查找指定值的节点函数 TreeNode* findNode(TreeNode* root, int target) { if (root == NULL) return NULL...接着比较根节点的值与目标值,如果相等则返回根节点指针。 如果根节点值不等于目标值,就先递归地在左子树中查找,若在左子树中找到了(返回的指针不为 NULL),则直接返回找到的节点指针。...求二叉树的高度 二叉树的高度定义为根节点到叶节点最长路径上的节点数,可以通过递归计算左子树高度和右子树高度,取较大值再加 1(根节点这一层)来得到整棵树的高度。

    52710

    图解:数据结构中的6种「树」,大鹏问你心中有数吗?

    ❞ 深度是从根节点开始「自顶向下」逐层累加的路径长度,根的深度为1(有些书上也说是 0,问题不大) 小技巧:高度和深度,一个从下往上数,一个从上往下数。...每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。) 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。...这些性质有兴趣可以自行研究,不过,现在你只需要知道,这些约束确保了红黑树的关键特性:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。 ?...利用字符串前缀来查找指定的字符串,缩短查找时间提高查询效率,主要用于字符串的快速查找和匹配。 为什么要称其为字典树呢?...定义 Trie的核心思想是空间换时间,有 3 个基本性质: 根节点不包含字符,除根节点外每一个节点都只包含一个字符。 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。

    2.3K51

    探秘二叉树:高效操作与遍历技巧大揭秘

    二叉树结构创建 // 定义二叉树节点存储的数据类型 typedef int BTDataType; // 二叉树节点结构体 typedef struct BinaryTreeNode { BTDataType...从概念中可以看出,二叉树定义是递归式的,因此后序基本操作中基本都是按照该概念实现的。 二叉树的遍历 前序、中序以及后序遍历 学习二叉树结构,最简单的方式就是遍历。...计算二叉树高度 树的高度:从根节点到最深叶子节点的最长路径长度 // 计算二叉树的高度 int TreeHeight(BTNode* root) { // 空树高度为0 if(root...查找指定值节点 // 在二叉树中查找值为x的节点 BTNode* TreeFind(BTNode* root, BTDataType x) { // 空树或查找结束 if(root ==...return 0; // 当前节点 + 左子树节点数 + 右子树节点数 return 1 + TreeNodeCount(root->left) +

    39710

    二叉树中和为某一值的路径

    一、题目给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。叶子节点 是指没有子节点的节点。...[0, 5000]• -1000 从根路径到叶子节点的路径,并要求满足该路径节点之和等于...targetSum;既然涉及到二叉树节点遍历,常用的就是深度优先算法和广度优先算法,那么由于本题涉及从根路径到叶子节点的路径,那么我们可以采用深度优先算法+ 前序遍历对这道题进行解答。...那么当我们从根节点遍历到叶子节点之后,会有如下两种情况:【情况1】所有节点总和正好等于targetSum,那么我们通过复制path,然后保存到result中即可。...如果还有其他树节点需要遍历,逐一回溯path末尾节点val值。【情况2】所有节点总和不等于targetSum,如果还有其他树节点需要遍历,逐一回溯path末尾节点val值。

    43330

    数据结构——二叉树

    边(Edge):连接两个节点的有向连接,一棵树有N个节点,就有N-1条边 路径(Path):从树中一个节点到另一个节点的一系列边。 深度(Depth):从根节点到特定节点的路径长度。...高度(Height):从特定节点到最远叶节点的路径长度。 节点的度:一个节点含有的子树或者节点的个数,如上图:A的度为6。 兄弟节点:具有相同的父节点的节点,如上图:B、D是兄弟节点。...树的度:一棵树中,具有最多子节点的节点的度,如上图:树的度为6。 节点的层次:从根节点开始,根为第一层,根的子节点为第二层,以此类推。 树的高度:树中节点的最大层次,如上图:树的高度为4....单层递归处理逻辑 返回1 + 左子树节点的个数 + 右子树节点的个数 // 二叉树节点个数 int BinaryTreeSize(BTNode* root) { return root == NULL...叶子节点的个数 终止情况 节点为空返回0;节点的左右子树为空返回1。 单层递归处理逻辑 返回左子树的叶子节点个数和右子树节点个数。

    44710
    领券