红黑树红黑树的定义 每个节点要么是红色，要么是黑色。 根节点是黑色。 每个叶子节点（NIL节点，即空节点）是黑色。 如果一个节点是红色，则它的两个子节点都是黑色。 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点（即，从根节点到叶子节点的所有路径上的黑色节点数目相同，这也是保证树的平衡性的关键规则）。 这些规则确保了红黑树具有以下特征： 任意节点到其后代节

平衡二叉树平衡二叉树的定义 对于任意一个节点，其左子树和右子树的高度差的绝对值不超过1。 其左子树和右子树都是平衡二叉树。 换句话说，平衡二叉树是一棵高度平衡的二叉搜索树，保证了树的左右子树的高度差不超过1，从而提供了较快的搜索、插入和删除操作的平均时间复杂度。 在平衡二叉树中，每个节点都有一个平衡因子（Balance Factor），它表示该节点的左子树高度减去右子树高度的值。当平衡因子的绝对值

二叉排序树二叉排序树的定义 若左子树非空，则左子树上所有结点的值均小于根结点的值。 若右子树非空，则右子树上所有结点的值均大于根结点的值 左、右子树也分别是一颗二叉排序树。 二叉排序树的查找二叉排序树中查找某关键字时，查找过程类似于次优二叉树，在二叉排序树不为空树的前提下，首先将被查找值同树的根结点进行比较，会有 3 种不同的结果： 如果相等，查找成功； 如果比较结果为根结点的关键字值较大，则

分块查找算法思想 特点：块内无序、块间有序。 块内的元素可以无序，但块间的元素是有序的，即第一个块中的最大关键字小于第二个块中的所有记录的关键字，第二个块中的最大关键字小于第三个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。 分块查找的过程分为两步： 第一步是在索引表中确定待查记录所在的块，可以顺序查找

折半查找 折半查找，又称“二分查找”，仅适用于有序的顺序表。—>因为顺序表拥有随机访问的特性，链表没有。 算法的思想 折半查找的基本思想：首先将给定值key与表中中间位置的元素（mid的指向元素）比较。mid=low+high/2（向下取整） 若key与中间元素相等，则查找成功，返回该元素的存储位置，即mid； 若key与中间元素不相等，则所需查找的元素只能在中间元素以

顺序查找算法思想 顺序查找又称线性查找，它对顺序表和链表都是适用的。对于顺序表，可通过数组下标递增来顺序扫描每个元素；对于链表，可通过指针next来依次扫描每个元素。顺序查找通常分为对一般的无序线性表的顺序查找和对按关键字有序的线性表的顺序查找。 顺序查找的实现 顺序查找的实现(带哨兵) 优点：无需判断是否越界，效率更高 查找效率分析 顺序查找的优化(对有序表) 若在查找之前就已经知道表是关

查找的基本概念查找在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找的结果一般分为两种：一是查找成功，即在数据集合中找到了满足条件的数据元素；二是查找失败 查找表（查找结构）用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成，可以是一个数组或链表等数据类型。对查找表经常进行的操作一般有4种： 查询某个特定的数据元素是否在查找表中。 检索满足条件的某个特定的数据元素的各种属

习题总结 磁盘是可共享设备（分时共享），是指某段时间内可以有多个用户进行访问。但某一时刻只能有一个作业可以访问。 顺序访问按从前到后的顺序对数据进行读写操作，如磁带。直接访问或随机访问，则可以按任意的次序对数据进行读写操作，如光盘、磁盘、U盘等。 磁盘调度的目的是缩短找道时间。磁盘调度是对访问磁道次序的调度，若没有合适的磁盘调度，则寻找时间会大大增加。 文件以块为单位存放于磁盘中，文件的读写也以块

习题总结 设备独立性是指用户编程时使用的设备与实际使用的设备无关。 为了使并发进程能有效地进行输入和输出，最好采用缓冲池结构的缓冲技术 输入井和输出井是在磁盘上开辟的存储空间，而输入/输出缓冲区则是在内存中开辟的，因为CPU速度比I/O设备高很多，缓冲池通常在主存中建立。 缓冲区管理着重要考虑的问题是实现进程访问缓冲区的同步 设备的分配方式主要由独享分配、共享分配和虚拟分配 提

缓冲区管理什么是缓冲区？有什么作用？ 缓冲区有什么作用？ 单缓冲 双缓冲 使用单/双缓冲在通信时的区别 循环缓冲区 缓冲池 总结