《算法的乐趣》第八节

本节介绍几种常用数据结构。树是表达层次关系的结构，每个节点只有一个父节点，按子节点大小分为有序树与无序树，按子节点数量分为二叉树与多叉树。

本节介绍几种常用数据结构。树是表达层次关系的结构，每个节点只有一个父节点，按子节点大小分为有序树与无序树，按子节点数量分为二叉树与多叉树。二叉查找树左子树的值小于根、右子树的值大于根，查找效率为O(lgn)，但按有序序列插入会退化成链表，故应优先使用能自平衡的AVL树和红黑树。多叉树的代表是B树及其变形B+树，常用于文件管理和数据库系统。区间树、线段树以区间为元素，用于区间重叠判断和统计查询；堆是完全树，父节点值恒大于（或小于）子节点，可用于堆排序和求最值；字典树以公共前缀节省存储，用于字符串查找与词频统计。集合具有无序、互异、确定三个特征，支持增删、判定及交并差运算。哈希表与映射都通过关键字直接访问值，哈希表靠哈希函数定位，查找时间固定不随数据量增长，优于有序表的O(lgn)。图由顶点和边组成，可按方向、连通性、边权等分类，用二元组或三元组定义，存储方式有邻接矩阵和邻接表，遍历常用深度优先和广度优先两种策略。