数据结构综合

1. 红黑树的理解

        红黑树是一棵平衡的二叉树，但是又不是一棵完美的二叉树，我们希望所有查找都能在比较logN次内结束，但是这样的动态插入保持树的完美性代价太高，这时我们就需要一种更好的数据结构，即红黑树。

红黑树满足以下5条性质：

1. 节点是红色或者是黑色
2. 根节点是黑色
3. 每个叶子节点（NIL或空节点）是黑色的
4. 每个红色节点的两个子节点都是黑色的（也就是说不存在两个连续的红色节点）
5. 从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点

参考：红黑树理解 - 程序员大本营

2.栈的使用场景

1. 函数调用
2. 表达式求值
3. 括号匹配
4. 浏览器的前进和后退功能
5. 子程序的调用
6. 处理递归的调用
7. 二叉树的遍历

3.队列的使用场景

1. 异步处理
2. 应用解耦（订单系统调用库存系统的接口）
3. 流量削峰（秒杀或团抢活动）
4. 日志处理（Kafka应用解决大量日志传输问题）
5. 消息通讯（实现点对点消息队列、聊天室）

4.树的使用场景

1. xml、html等，编写其解析器的时候会用到树的结构
2. 文件系统的目录结构（Linux系统）
3. MySQL数据库的索引
4. 路由协议也用到了树的算法
5. 文件的压缩（哈夫曼树即最优二叉树）
6. 电讯通信业务（哈夫曼编码）
7. 深度优先搜索算法
8. 红黑树（Linux中进程的调度就是用的红黑树）
9. C4.5算法（基于信息增益率实现的决策树算法）
10. CART算法（基于基尼指数实现的决策树算法）

5.数组和链表的区别？

数组和链表是两种基本的数据结构，他们在内存存储上的表现是不一样的，各有各的特点。

数组的特点：

1. 在内存中，数组是一块连续的区域；
2. 数组需要预留空间，在使用前要先申请占用内存的大小，可能会浪费内存空间；
3. 插入数据和删除数据时效率是比较低的，插入数据时，这个位置后面的数据在内存中都要向后移动，删除数据时，这个数据后面的数据都要向前移动；
4. 随机读取效率是很高的，因为数组是连续的，知道每个数组的内存地址，可以直接找到该地址的数据；
5. 不利于扩展，数组定义的空间不够时要重新定义数组。

链表的特点：

1. 在内存中可以存在任何地方，不要求连续；
2. 每一个数据都保存了下一个数据的内存地址，通过这个地址找到下一个数据；
3. 增加数据和删除数据很容易；
4. 查找数据时效率是比较低的，因为不具有随机访问性，所以访问某个位置的数据都要从第一个数据开始访问，然后根据第一个数据保存到下一个数据的地址找到第二个数据，以此类推；
5. 不指定大小，扩展方便。链表大小不用定义，数据随意增删。

数组的优点：

• 随机访问性强
• 查找速度快

数组的缺点：

• 插入和删除的效率低
• 可能浪费内存
• 内存空间要求高，必须有足够的连续的内存空间
• 数组大小固定，不能动态拓展

链表的优点：

• 插入和删除速度快
• 内存利用率高，不浪费内存
• 大小没有固定，拓展很灵活

链表的缺点：

• 不能随机查找，必须从第一个开始遍历，查找效率低

6.解决哈希冲突的方案有哪些？

1.开放地址法

        线性探测：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

        二次探测：冲突发生时，在表的左右进行跳跃式探测，比较灵活。

        伪随机探测：di=伪随机数序列

2.拉链法：采用链表的数据结构来去存取发生哈希冲突的输入域的关键字

3.再散列法：再使用哈希函数去散列一个输入的时候，输出是同一个位置就再次散列，直至不发生冲突位置