认识达内从这里开始

随着互联网的不断发展，越来越多的人都在学习Java编程开发语言等技术，而本文我们就通过案例分析来简单了解一下，Java编程程序员常用数据结构都有哪些类型。

一、图表(Graphs)

图是表示一对两个集合的非线性数据结构：G={V,E}，其中V是顶点(节点)的集合，而E是边(箭头)的集合。节点是由边互连的值-描述两个节点之间的依赖关系(有时与成本/距离相关联)的线。

图有两种主要类型：有向图和无向图。在无向图中，边(x,y)在两个方向上都可用：(x,y)和(y,x)。在有向图中，边(x,y)称为箭头，方向由其名称中顶点的顺序给出：箭头(x,y)与箭头(y,x)不同。

它们是做什么用的?

图是各种类型网络的基础：社交网络(如weixin、csdn、weibo)，甚至是城市街道网络。社交媒体平台的每个用户都是一个包含他/她的所有个人数据的结构——它代表网络的一个节点。weixin上的好友关系是无向图中的边(因为它是互惠的)，而在CSDN或weibo上，帐户与其关注者/关注帐户之间的关系是有向图中的箭头(非互惠)。

特性

图论是一个广阔的领域，但我们将重点介绍一些知名的概念：

无向图中节点的度数是它的关联边数;

有向图中节点的内部/外部度数是指向/来自该节点的箭头的数量;

从节点x到节点y的链是相邻边的连续，x是它的左端，y是它的右边;

一个循环是一个链，其中x=y;图可以是循环/非循环的;如果V的任意两个节点之间存在链，则图是连通的;

可以使用广度优先搜索(BFS)或深度优先搜索(DFS)遍历和处理图，两者都在O(|V|+|E|)中完成，其中|S|是集合S的基数;查看下面的链接，了解图论中的其他基本信息。

二、树(Trees)

一棵树是一个无向图，在连通性方面小(如果我们消除一条边，图将不再连接)和在无环方面大(如果我们添加一条边，图将不再是无环的).所以任何无环连通无向图都是一棵树，但为了简单起见，我们将有根树称为树。

根是一个固定节点，它确定树中边的方向，所以这就是一切“开始”的地方。叶子是树的终端节点——这就是一切“结束”的地方。

一个顶点的孩子是它下面的事件顶点。一个顶点可以有多个子节点。一个顶点的父节点是它上面的事件顶点——它是的。

它们是做什么用的?

我们在任何需要描绘层次结构的时候都使用树。我们自己的家谱树就是一个完美的例子。你古老的祖先是树的根。年轻的一代代表叶子的集合。

树也可以代表你工作的公司中的上下级关系。这样您就可以找出谁是您的上级以及您应该管理谁。

特性

根没有父级;

叶子没有孩子;

根和节点x之间的链的长度表示x所在的级别;

一棵树的高度是它的高层(在我们的例子中是3);

常用的遍历树的方法是O(|V|+|E|)中的DFS，但我们也可以使用BFS;使用DFS在任何图中遍历的节点的顺序形成DFS树，指示我们访问节点的时间。

三、二叉树(BinaryTrees)和二叉搜索树(BinarySearchTrees)

二叉树是一种特殊类型的树：每个顶点多可以有两个子节点。在严格二叉树中，除了叶子之外，每个节点都有两个孩子。具有n层的完整二叉树具有所有2ⁿ-1个可能的节点。

二叉搜索树是一棵二叉树，其中节点的值属于一个完全有序的集合——任何任意选择的节点的值都大于左子树中的所有值，而小于右子树中的所有值。

它们是做什么用的?

BT的一项重要应用是逻辑表达式的表示和评估。每个表达式都可以分解为变量/常量和运算符。这种表达式书写方法称为逆波兰表示法(RPN)。这样，它们就可以形成一个二叉树，其中内部节点是运算符，叶子是变量/常量——它被称为抽象语法树(AST)。

BST经常使用，因为它们可以快速搜索键属性。AVL树、红黑树、有序集和映射是使用BST实现的。

特性

BST有三种类型的DFS遍历：

先序(根、左、右);

中序(左、根、右);

后序(左、右、根);全部在O(n)时间内完成;

中序遍历以升序为我们提供了树中的所有节点;

左边的节点是BST中的小值，右边的节点是大值;

注意RPN是AST的中序遍历;

BST具有排序数组的优点，但有对数插入的缺点——它的所有操作都在O(logn)时间内完成。

四、AVL树(Adelson-VelskyandLandisTrees)

所有这些类型的树都是自平衡二叉搜索树。不同之处在于它们以对数时间平衡高度的方式。

AVL树在每次插入/删除后都是自平衡的，因为节点的左子树和右子树的高度之间的模块差异大为1。AVL以其发明者的名字命名：Adelson-Velsky和Landis。

在红黑树中，每个节点存储一个额外的代表颜色的位，用于确保每次插入/删除操作后的平衡。

在Splay树中，近访问的节点可以快速再次访问，因此任何操作的摊销时间复杂度仍然是O(logn)。

它们是做什么用的?

AVL似乎是数据库理论中好的数据结构。

RBT(红黑树)用于组织可比较的数据片段，例如文本片段或数字。在Java8版本中，HashMap是使用RBT实现的。计算几何和函数式编程中的数据结构也是用RBT构建的。

在WindowsNT中(在虚拟内存、网络和文件系统代码中)，Splay树用于缓存、内存分配器、垃圾收集器、数据压缩、绳索(替换用于长文本字符串的字符串)。

特性

ANY自平衡BST中ANY操作的摊销时间复杂度为O(logn);

在坏的情况下，AVL的大高度是1.44*log2n(为什么?==提示==：考虑所有级别都已满的AVL的情况，除了后一个只有一个元素);

AVLs在实践中搜索元素是快的，但是为了自平衡而旋转子树的成本很高;

同时，由于没有旋转，RBT提供了更快的插入和删除;

展开树不需要存储任何簿记数据。

【免责声明】本文系本网编辑部分转载，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与管理员联系，我们会予以更改或删除相关文章，以保证您的权益!更多内容请加danei456学习了解。欢迎关注“达内在线”参与分销，赚更多好礼。