树

1. Dotcpp
2. 树

手指树的基本结构

一、简介手指树（FingerTree）是一种纯函数式数据结构，由RalfHinze和RossPaterson提出。二、为什么需要手指树？在函数式编程中，列表是十分常见的数据类型。对于基于序列的操作，包括在两端添加和删除元素（双端队列操作），在任意节点插入、连接、删除，

数据结构 2022年05月22日 142 点赞 0 评论 66507 浏览

简述霍夫曼树

1.树的带权路径长度设二叉树具有n个带权叶结点，从根结点到各叶结点的路径长度与相应叶节点权值的乘积之和称为树的带权路径长度（WeightedPathLengthofTree，WPL）。设为二叉树第i个叶结点的权值，为从根结点到第i个叶结点的路径长度，

数据结构 2022年02月03日 64 点赞 0 评论 102899 浏览

什么是Prufer序列？

Prufer序列可以将一个带标号n个结点的树用[1,n]中的n-2个整数表示。你也可以把它理解为完全图的生成树与数列之间的双射。显然你不会想不开拿这玩意儿去维护树结构。这玩意儿常用组合计数问题上。HeinzPrufer于1918年发明这个序列来证明凯莱定理。

图论 2022年02月11日 102 点赞 0 评论 102958 浏览

简述最小树形图

一、什么是最小树形图？就是指有向图上的最小生成树，英文是DirectedMinimumSpanningTree。常用的算法是朱刘算法（也称Edmonds算法），可以在O(nm)时间内解决最小树形图问题。（1）过程对于每个点，选择它入度最小的那条边如果没有环，

图论 2022年03月27日 222 点赞 0 评论 96712 浏览

斯坦纳树的应用

斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小。1.什么是斯坦纳树？斯坦纳树问题是组合优化学科中的一个问题。

图论 2022年02月01日 209 点赞 0 评论 88249 浏览

最小生成树图文解析

最小生成树英文是MinimumSpanningTree，对于最小生成树大家应该都不陌生，当然还有最大生成树，首先就简单总结一下算法里的生成树。一、什么是生成树？Spanning有跨越的意思，生成树一般来说每个节点都能访问到别的节点，是一个连通树。

图论 2022年05月06日 193 点赞 0 评论 123144 浏览

简述矩阵树定理

Kirchhoff矩阵树定理可以简称矩阵树定理，可以解决了一张图的生成树个数计数问题。本篇中的图，无论无向还是有向，都允许重边，但是不允许自环。一、概况1.无向图情况设G是一个有n个顶点的无向图。定义度数矩阵D(G)为：设为点i与点j相连的边数，

图论 2022年05月27日 160 点赞 0 评论 93130 浏览

什么是树上随机游走？

什么是树上随机游走？我们可以假设给定一棵树，树的某个结点上有一个硬币，在某一时刻硬币会等概率地移动到邻接结点上，问硬币移动到邻接结点上的期望距离。1.树上随机游走用到的定义：●所讨论的树●结点的度数●结点与v结点之间的边的边权●结点的父结点●结点的子结点集合●结点的兄弟结点集合2.向父结点走的期望距离

图论 2022年03月22日 88 点赞 0 评论 65712 浏览

树哈希常用的方式

树哈希，顾名思义，对树进行哈希，经常判断两个树是否同构。一下均为对有根树的算法，而无根树只需要找重心。我们有时需要判断一些树是否同构。这时，选择恰当的哈希方式来将树映射成一个便于储存的哈希值（一般是32位或64位整数）是一个优秀的方案。树哈希有很多种哈希方式，下面将选出几种较为常用的方式来加以介绍。

图论 2022年03月28日 143 点赞 0 评论 65100 浏览

什么是虚树？

当我们遇到一类频繁询问关键点信息的题目时，往往数据范围颇大，而对关键点总和有一定限制，此时我们可以建立虚树，将问题规模转化为关键点总和级别的。一、定义什么是虚树？当我们在树上有部分结点是无用的或用处不大的时，我们可以将其在树上删去，仅仅保留关键点和连接关键点的边。

图论 2022年01月16日 194 点赞 0 评论 78648 浏览