视频上传网站如何做,网站设计排名网站,网络设计工程师是干什么的,提高网站转化率目录 典型数据结构列举
栈/队列/链表
树
二叉树
线索二叉树
二叉排序树
平衡二叉树#xff08;AVL树#xff09;
红黑树
其它树种和应用介绍 典型数据结构列举
栈/队列/链表
描述略。
一些基本的简单实现参考/数据结构简单实现/文件夹里面。
线性表详解#xff…目录 典型数据结构列举
栈/队列/链表
树
二叉树
线索二叉树
二叉排序树
平衡二叉树AVL树
红黑树
其它树种和应用介绍 典型数据结构列举
栈/队列/链表
描述略。
一些基本的简单实现参考/数据结构简单实现/文件夹里面。
线性表详解数据结构线性表10分钟入门 (biancheng.net)。栈(Stack)和队列(Queue)详解 (biancheng.net)。
树
以下为树的基本概念定义、基本操作、性质、存储结构等、二叉树定义、基本操作、存储、遍历等、平衡二叉树、红黑树等。 引自树及二叉树的基本概念_青萍之末的博客-CSDN博客。 树是由一个或一个以上的节点node组成存在一个特殊节点称为树根root它是nn0个节点的有限集。n0时称为空树。n0时有限集的元素构成一个具有层次感的数据结构。 树的一些概念 节点的度一个节点拥有子树的数目。例如A的度为2B的度为1C的度为3。树的高度也称为树的深度树中节点的最大层次。有序树树中节点各子树之间的次序是重要的不可以随意交换位置。无序树树种节点各子树之间的次序是不重要的。可以随意交换位置。森林0或多棵互不相交的树的集合。 引自《数据结构教程》。 树的一些性质 非空树的节点总数等于树中所有节点的度之和加1。度为 k 的非空树的第 i 层最多有 k^(i-1) 个节点i ≥ 1。深度为 h 的 k 叉树最多有 (k^h - 1)/(k - 1) 个节点。具有 n 个节点的 k 叉树的最小深度为 log_k(n*(k - 1)) 1。包含 n 个结点的二叉树的高度至少为 log_2(n) 1。 树的基本操作 建立一棵空树 T。求结点 x 所在树的根节点。或求树 T 的根节点。求树 T 中结点 x 的双亲结点。求树 T 中节点 x 的第 i 个孩子节点。求树 T 中节点 x 右边 的兄弟节点。把以 S 为根结点的树插入到 树 T 的 节点 x 的第 i 个子节点位置上。删除树 T 中 节点 x 的第 i 棵树。对一棵树进行遍历按照某种次序遍历树所有节点并得到一个由所有节点组成的序列。 树的存储 采用链式存储方式居多。除了储存节点本身的数据信息之外还必须做到把树中各个节点之间的连接关系反映在存储结构中。 多重链表表示法分为 定长链接数目 和 不定长链接数目。 前者 后者 三重链表表示法 二叉树
树及二叉树的基本概念_青萍之末的博客-CSDN博客。 引自《数据结构教程》。 二叉树结构被广泛用来解决计算机领域中的各种实际问题。例如在排序、检索、数据库管理系统以及人工智能等许多方面二叉树都提供了强而有效的支持。 … 每一个节点最多只有两颗子树。在二叉树中严格区分节点的左、右子树其次序不能随意颠倒。因此二叉树是有序树。 二叉树又可以分为满二叉树和完全二叉树。 二叉树的基本操作 二叉树的存储结构 顺序存储结构顺序存储结构固有一些缺陷使得二叉树的插入、删除等操作不方便而且效率比较低线性表的固有缺点。 链式存储结构更适合更广泛。两种二叉链表结构 和 三叉链表结构。 二叉链表结构链表中每一个链接点由三个域组成分别为数据域和两个指针域后者分别给出该节点的左、右节点的存储地址。 三叉链表结构相比于二叉链表结构多增加一个用来指向双亲节点的指针域这样在查找二叉树中某个节点的双亲节点时候不用遍历整个二叉树。就是空间换时间如查找的时间等。 二叉树与树的遍历 有关二叉树的许多操作几乎都是建立在二叉树的遍历之上。二叉树是一种非线性结构因此需要寻找一种规律使得二叉树中的所有节点能够排列在一个线性序列中这就叫遍历。 若以符号 D、L 和 R 分别表示访问根节点、遍历根结点的左子树 和 遍历根结点的右子树 三个过程并且限定先左后右的顺序则通常采用三种遍历方式DLR、LDR、LRD分别称之为 前序遍历、中序遍历、后续遍历。还有 按层次 的遍历顺序。 遍历可以用递归的方式对于很大的树容易栈溢出。非递归方法通常利用一个栈结构。 下面举例按照 中序遍历 顺序遍历的程序。 按照层次遍历或叫 广度优先遍历 即 若被遍历的二叉树非空则依次访问二叉树的第1层、第2层……直到最后一层对每一层的访问按照从左到右的顺序进行。 该方法通常用一个队列实现。下面举例程序。 由遍历序列恢复二叉树 三步 线索二叉树 在二叉树的结点上加上线索的二叉树称为线索二叉树。对于n个结点的二叉树在二叉链存储结构中有n1个空链域利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针这些指针称为线索加上线索的二叉树称为线索二叉树。 彻底理解线索二叉树_ Walk the horizon-CSDN博客 _线索二叉树的作用。线索二叉树的理解_ huangwei18351的博客-CSDN博客 _线索二叉树。
二叉排序树 引自《数据结构教程》。 二叉排序树用于排序、查找/检索可以大大提高查找的时间效率在一般情况下查询效率比链表结构要高。二叉排序树又叫二叉查找树。有人说当需要完成的功能是插入、删除和检索二叉排序树具有比迄今为止研究过的任何数据结构都有更好的性能。 引自二叉排序树二叉查找树及C语言实现 (biancheng.net)。 二叉排序树要么是空二叉树要么具有如下特点 二叉排序树中如果其根结点有左子树那么左子树上所有结点的值都小于根结点的值二叉排序树中如果其根结点有右子树那么右子树上所有结点的值都大小根结点的值二叉排序树的左右子树也要求都是二叉排序树 如下图所示就是一个二叉排序树。 引自《数据结构教程》。 二叉排序树中插入数据同样需要按照二叉排序树的原则进行。每次将一个新的元素插入到二叉排序树中该元素对应的节点都是插在叶节点位置插入的过程没有移动二叉树中其他节点。一个数据元素序列不一定按照值的大小进行排列但当对其构造成为一棵二叉排序树以后对该二叉排序树进行中序遍历得到的序列是一个按值大小排列的序列。 二叉排序树二叉查找树及C语言实现 (biancheng.net)。二叉排序树_百度百科 (baidu.com)。二叉查找树BST及二叉树的遍历_ 青萍之末的博客-CSDN博客 _二叉搜索树的遍历。二分搜索树 | 菜鸟教程 (runoob.com)。
平衡二叉树AVL树 引自平衡二叉树AVL树及C语言实现 (biancheng.net)。 平衡二叉树又称为 AVL 树。实际上就是遵循以下两个特点的二叉树 每棵子树中的左子树和右子树的深度差不能超过 1二叉树中每棵子树都要求是平衡二叉树 其实就是在二叉树的基础上若树中每棵子树都满足其左子树和右子树的深度差都不超过 1则这棵二叉树就是平衡二叉树。 把二叉树中每个节点的左子树深度与右子树深度之差定义为该节点的平衡因子因此平衡二叉树中每个节点的平衡因子只能是 1、0 或 -1。 引自《数据结构教程》。 二叉排序树的形态事先无法预料随意性很大得到的往往是一颗很不 “平衡” 的二叉树深度差越大其运算时间也越长丧失了其优势。为了克服二叉排序树的这个缺陷需要在插入和删除节点的同时对二叉树的形态结构进行必要的调整使二叉排序树始终处于一种平衡状态。 … 理论上已经证明具有 n 个节点的平衡树的深度在任何情况下都不会比具有相同节点数目的理想平衡数的深度高出 45% 以上。因此再平衡树上进行查找操作虽然比理想平衡树要慢一些但通常比任意生成的二叉排序树中进行查找要快得多其时间复杂度的数量级仍为O(Log_2(n))。 平衡二叉树AVL树及C语言实现 (biancheng.net)。AVL树平衡二叉树_ 青萍之末的博客-CSDN博客 _avl树是平衡二叉树吗。
红黑树 引自 红黑树RB-Tree_青萍之末的博客-CSDN博客。 红黑树是一种二叉查找树。 红黑树与AVL树的对比 如果插入一个节点引起了树的不平衡AVL和RB-Tree都是最多只需要2次旋转操作即两者都是O(1)但是在删除节点引起树的不平衡时最坏情况下AVL需要维护从被删节点到根节点这条路径上所有节点的平衡性因此需要旋转的量级O(logN)而RB-Tree最多只需3次旋转只需要O(1)的复杂度但是由于红黑树没有AVL树那么高度平衡所以红黑树的查找性能相比AVL树要差一些查找上的这一点性能差相比数据的插入和删除时的旋转性能是值得的这就是为什么很多场合是用的红黑树而不是AVL树例如STL中的map和set。因此RB-Tree在需要大量插入和删除节点的场景下效率更高。自然由于AVL高度平衡因此AVL的查找效率更高。 红黑树和AVL树的实现与比较—–算法导论 - 希隆囚徒 - 博客园 (cnblogs.com)。红黑树RB-tree比AVL树的优势在哪_mmshixing的博客-CSDN博客_红黑树的优点。动画红黑树旋转的艺术 - 知乎 (zhihu.com)。
其它树种和应用介绍
B树和B树_青萍之末的博客-CSDN博客 B树是对二叉查找树的改进B树大量应用在数据库和文件系统当中。浅谈二叉查找树、AVL树、红黑树、B树、B树的原理及应用_青萍之末的博客-CSDN博客。还有哈夫曼树、字典树等等树种。。
