文章目录数据结构-树树特点平衡二叉树二叉查找树AVL树红黑树红黑树和AVL树的比较b-树(注 读作b树不是b减树没有减号这个概念)b树是二叉树吗?b树的特点二叉树可以简称读作b树吗?b树和红黑树的区别b树和b树的区别什么叫自平衡树?菜单数据库设计什么结构便于使用获取树的方法递归调用获取树一个节点是树吗?正向树和反向树结合确定调用链图和二叉树最大的区别是什么拓扑结构(topological)拓扑结构和循环遍历树的区别拓扑结构和循环遍历树哪个更好呢?树是一个非常大的课题光是概念就能弄的人头昏脑胀。 但是如果掌握了是有点小小的成就感的。树结构是应用非常广泛的结构甚至可以说无处不在。电脑里的文件夹是不是树结构省市区县镇乡村是不是树结构菜单是不是树结构军队是不是树结构职位是不是树结构。。。太多了数都数不过来。但是从数据库或代码的层面实现里面的东西就太多了。数据结构-树树特点1、一个节点即只有根节点也可以是一棵树2、其中任何一个节点与下面所有节点构成的树成为子树3、根节点没有父节点而叶子节点没有子节点4、除根节点外任何节点有且仅有一个父节点5、任何节点可以有0n个字节点。平衡二叉树1、树的左右高度差不能超过12、任何往下递归的左子树和右子树必须符合第一条性质3、没有任何节点的空树或只有根节点的树也是平衡二叉树。二叉查找树1、在任何递归子树中左节点一定在右节点之前遍历2、前序中序后序仅指根节点在遍历的位置顺序AVL树一种平衡二叉查找树增加和删除节点后通过通过旋转重新达到平衡。红黑树1、节点只能是红色或者黑色2、根节点必须是黑色3、所有NIL节点都是黑色4、一条路径上不能出现相邻的两个红色节点5、在任何递归子树内根节点到叶子节点的所有路径上包含相同数目的黑色节点。红黑树和AVL树的比较黑深度当前节点到NIL途径的黑色节点个数。b-树(注 读作b树不是b减树没有减号这个概念)b-树 就是 b树。B树也翻译为B-树(是一种多路搜索树 并不是二叉的)1、定义任意非叶子结点最多只有M个儿子且M22、根结点的儿子数为[2, M]3、除根结点以外的非叶子结点的儿子数为[M/2, M]4、每个结点存放至少M/2-1取上整和至多M-1个关键字至少2个关键字5、非叶子结点的关键字个数指向儿子的指针个数-16、非叶子结点的关键字K[1], K[2], …, K[M-1]且K[i] K[i1]7、非叶子结点的指针P[1], P[2], …, P[M]其中P[1]指向关键字小于K[1]的子树P[M]指向关键字大于K[M-1]的子树其它P[i]指向关键字属于(K[i-1], K[i])的子树8、所有叶子结点位于同一层b树是二叉树吗?b树不是二叉树因为二叉树每个节点最多有两个子节点但是b树可以有多个子节点。但是百度文档第一行居然是b树是二叉树。。。(感觉是写错了)b树的特点相对于B树B树有四点不同1、B树中非叶子节点不存放数据存的是索引它的叶子节点才存放数据而B树中所有节点都存放数据2、B树相邻的叶子节点之间通过链表指针连接起来而B树没有3、查找过程中B树在找到具体的数据以后就结束而B树则需要通过索引找到叶子节点中数据才结束4、B树任何一个关键字只出现在一个节点中而B树可以出现多次。因此相对于B树B树有以下优点1、非叶子节点不存放数据单一节点存储更多的元素磁盘IO次数更少2、查询都要找到叶子节点查询性能稳定3、所有叶子节点形成有序链表便于范围查询查询效率更高。b树应用在哪些场景呢?mysql数据库。B树还是B树别再傻傻分不清了 # 这篇文章不错二叉树可以简称读作b树吗?不能按照习惯英文开头大写字母抽出来读是可以的但是这里不行。二叉树(binary tree)平衡树(balance tree) # b树二叉查找树(binary search tree) # bstb树表示的是平衡树。所以二叉树只有两种叫法二叉树或binary tree。b树和红黑树的区别特性红黑树B树基本结构二叉搜索树每个节点最多2个子节点多路搜索树每个节点可有多于2个子节点平衡方式通过颜色约束和旋转保持近似平衡通过节点分裂/合并保持严格平衡高度较高O(log n)较矮O(log_m n)m为阶数典型应用内存数据结构如C STL map/set磁盘/数据库索引如文件系统、数据库节点存储存储键值对通常每个节点存一个键存储键值对每个节点可存多个键b树和b树的区别特性B树B树数据存储位置所有节点均可存储数据仅叶子节点存储数据内部节点只存键索引叶子节点结构叶子节点独立无链表连接叶子节点通过指针串联成有序链表查询稳定性不稳定数据可能在中间节点找到稳定必须到叶子节点范围查询效率较低需中序遍历极高链表顺序访问内部节点结构存储键数据指针仅存储键索引空间利用率相对较低更高键更密集总结1、b树非叶子节点只存储索引叶子节点只存储数据。 # 遍历时好遍历只需遍历叶子节点2、b树叶子节点间有链表 # 便于范围查询什么叫自平衡树?菜单数据库设计菜单结构主要的就是id,pid,type(菜单类型)。关键就在怎么拾掇这堆id,pid上。什么结构便于使用正常来说查出的结构一定是个map完美的展现层级结构。但是发现没有map结构虽然全面但是如果我想要查询某个按钮?是不是不好查估计要解map了太费劲。易于展现的结构不一定易于查询。所以这里换个思路还是map结构但是以末级节点作为key上级节点的集合以数组的形式顺序存放。如{crm:{8888:[100,130,139],9999:[100,130,914]}}这样用起来就非常方便了。获取树的方法方法太多了百度上代码一堆。递归调用获取树实测可用没看懂这段代码什么意思。 递归不好把控执行流程。后来加了日志大概明白了先循环匹配到id从list中删除剩余list中以当前id作为pid继续递归。递归完毕后resultList再统一添加。publicstaticListResourcegetTree(ListResourceresources,Longid){if(StrUtils.isEmptyList(resources)){returnnull;}ListResourcelistnewArrayList();ListResourcelistContinuenewArrayList(resources);for(Resourceitem:resources){if(item.getPid().equals(id)){listContinue.remove(item);item.setChildren(getTree(listContinue,item.getId()));list.add(item);}}if(CollectionUtils.isEmpty(list)){returnnull;}else{returnlist;}}一个节点是树吗?可以是树树可以只有一个节点。正向树和反向树结合确定调用链是这样某个功能在哪些位置被调用以及有哪些下级功能。类似于idea的下级及引用。实际上实现起来并不难用两棵树就可以实现。注这里树比超链接强大多了例如多个子级excel就做不到或者需要多行即使实现了也不太优雅。图和二叉树最大的区别是什么树的上级节点是唯一的最多有一个。图的顶点(图没有节点的概念)是多对多的关系并且所有顶点都是平等的无所谓谁是父谁是子。拓扑结构(topological)代码importjava.util.*;publicclassKahnAlgorithm{/** * Kahn 算法核心逻辑 * param numNodes 节点总数 * param adjacencyList 邻接表 (记录每个节点的下游依赖) * param inDegrees 入度数组 (记录每个节点的前置依赖数量) * return 拓扑排序后的节点列表若存在环则返回空列表 */publicstaticListIntegertopologicalSort(intnumNodes,ListListIntegeradjacencyList,int[]inDegrees){// 1. 将所有入度为 0 的节点无前置依赖加入队列QueueIntegerqueuenewLinkedList();for(inti0;inumNodes;i){if(inDegrees[i]0){queue.offer(i);}}ListIntegerresultnewArrayList();// 2. 循环处理队列中的节点while(!queue.isEmpty()){intcurrentNodequeue.poll();result.add(currentNode);// 将当前节点加入最终排序结果// 3. 遍历当前节点的所有下游节点将它们的入度减 1for(intneighbor:adjacencyList.get(currentNode)){inDegrees[neighbor]--;// 4. 如果某个下游节点的入度变成了 0说明它的前置条件已全部满足加入队列if(inDegrees[neighbor]0){queue.offer(neighbor);}}}// 5. 环检测如果结果列表的大小不等于节点总数说明图中存在环if(result.size()!numNodes){System.err.println(错误检测到循环依赖无法完成拓扑排序);returnCollections.emptyList();}returnresult;}publicstaticvoidmain(String[]args){// 模拟主数据同步依赖0-部门, 1-员工, 2-薪酬, 3-绩效// 依赖关系部门(0) - 员工(1) - 薪酬(2)// 部门(0) - 员工(1) - 绩效(3)intnumNodes4;// 构建邻接表ListListIntegeradjacencyListnewArrayList();for(inti0;inumNodes;i){adjacencyList.add(newArrayList());}adjacencyList.get(0).add(1);// 0 - 1adjacencyList.get(1).add(2);// 1 - 2adjacencyList.get(1).add(3);// 1 - 3// 构建入度数组 (0:部门, 1:员工, 2:薪酬, 3:绩效)int[]inDegrees{0,1,1,1};// 执行拓扑排序ListIntegersortedOrdertopologicalSort(numNodes,adjacencyList,inDegrees);// 打印结果if(!sortedOrder.isEmpty()){System.out.println(主数据同步推荐执行顺序:);for(inti0;isortedOrder.size();i){System.out.print(sortedOrder.get(i));if(isortedOrder.size()-1)System.out.print( - );}System.out.println();}}}拓扑结构和循环遍历树的区别对比维度你提供的代码(递归构建树)拓扑排序(Topological Sort)核心目的将扁平数据组装成父子层级结构(Tree)将依赖关系解析成线性执行序列(List)适用场景前端渲染菜单、部门树、分类导航主数据同步、ETL任务调度、工程工序数据结构必须是无环的树(Tree)有向无环图(DAG允许一个节点有多个父节点)输出结果嵌套的 JSON 对象(包含 children)扁平的、有先后顺序的列表拓扑结构和循环遍历树哪个更好呢?他们不是竞争的关系而是相辅相成的关系。在主数据同步的完整链路中这两个算法并不是二选一的竞争对手而是上下游配合的搭档。简单来说拓扑排序是总指挥递归/Map构建树是包装工。1、拓扑排序决定什么时候同步(调度层)在主数据同步的调度层必须使用拓扑排序。作用它负责解析你系统中所有主数据实体(如国家、省份、城市、公司、部门、员工)之间的依赖关系排出一个绝对安全的执行队列。场景确保在同步员工之前部门一定已经同步完毕在同步部门之前公司一定已经同步完毕。为什么必须用它如果不用拓扑排序一旦下游系统收到员工数据时部门还没落库就会因为外键约束导致同步大批量报错。2、递归/Map构建树决定同步过去长什么样(数据组装层)当拓扑排序决定了现在轮到同步部门了在数据组装层就需要用到构建树的逻辑。作用将数据库里扁平的部门数据组装成下游系统需要的层级结构。场景场景 A(下游需要扁平数据)如果下游是普通业务表直接同步扁平的 List 即可不需要构建树。场景 B(下游需要树形数据)如果下游是 OA 系统、钉钉或者前端需要渲染组织架构菜单你就必须把扁平数据组装成带有 children 的树形 JSON此时才需要调用构建树的逻辑。