非线性数据结构有哪些：分类与选型

非线性数据结构有哪些，常见类型包含树、二叉树、堆、图、哈希表、字典树、红黑树、B树，这类结构的数据元素之间存在一对多或多对多的关联关系，内存存储位置不连续，不能用简单顺序遍历访问全部节点，适合处理层级关系、网络关联、动态查找场景，线性数据结构的顺序遍历算法无法直接套用，适用边界为数据存在分支关联，若数据元素仅一对一依次排列，优先选用数组、链表这类线性结构。

非线性数据结构基础类型解析

树，一对多关系的非线性结构，单个根节点向下延伸多个子节点，子节点还能继续分出下层节点，文件系统目录就是典型树结构，树没有环，任意两个节点之间只存在唯一一条路径。二叉树属于树的子集，每个节点最多只能分出两个子节点，分为左子节点与右子节点，左右顺序不可随意调换。堆是基于完全二叉树实现的结构，分为大顶堆、小顶堆，用来快速获取集合里最大值或者最小值，常用于任务优先级调度。

图，多对多关系的非线性结构，由顶点和连接顶点的边构成，边可以携带权重，社交好友关系、城市交通路网都采用图模型。图可以存在环路，遍历需要标记已访问顶点，避免循环死锁，分为有向图与无向图，有向图的边存在方向约束，无向图的边双向连通。

字典树也叫Trie树，专门处理字符串前缀匹配的非线性结构，节点不存储完整单词，仅保存单个字符，适合搜索引擎输入联想、单词拼写校验，在短字符串批量检索场景效率较高。

红黑树、B树属于平衡查找树，红黑树通过颜色规则维持树平衡，减少树的深度，广泛用于JavaTreeMap；B树是多路平衡查找树，一个节点可以包含多个关键字，多用于数据库索引，降低磁盘IO次数。

非线性数据结构选型对比

哈希表部分场景会被归类为非线性结构，键值对之间不存在固定先后顺序，依靠哈希函数定位存储位置，平均情况下读写速度较快，哈希冲突会降低查询性能，冲突严重时查询耗时会明显上涨。

非线性结构遍历复杂度更高。

线性遍历方式无法遍历图和普通树，必须使用深度优先遍历或者广度优先遍历，深度优先遍历沿着一条分支一直向下直到末端，再回溯访问其他分支；广度优先遍历按照层级逐层访问节点，先访问同层所有节点，再进入下一层。树结构遍历还额外包含前序、中序、后序遍历三种方式，三种方式区别在于根节点、左子树、右子树的访问顺序。

当数据没有分支、层级、网络关联，只需要顺序存取，不要选用非线性数据结构。比如连续日志记录，元素只需要依次追加读取，数组性能优于树和图，额外的节点指针会增加内存开销，算法编写复杂度也会上升。

非线性结构增删节点时，部分结构需要执行平衡调整操作。红黑树新增或者删除节点，会触发旋转、变色操作维持平衡，单次操作会带来少量额外计算开销，频繁随机增删海量数据时，要评估平衡操作带来的性能损耗。