数据结构与算法总结（持续更新~）

柔光的暖阳◎ 2024-04-17 05:56 33阅读 0赞

# 以下题目总结于：[牛客网][Link 1] #

## **相关总结：** ##

> ### [C/C++面试题总结][C_C] ###
> 
> ### [计算机网络面试题总结][Link 2] ###
> 
> ### [操作系统面试题总结][Link 3] ###
> 
> ### [设计模式面试题总结][Link 4] ###
> 
> ### [数据库面试总结][Link 5] ###

## 一、树 ##

### 1、请你来说一说红黑树和 AVL  树的定义，特点，以及二者区别？ ###

参考答案：

① 平衡二叉树（AVL 树）

平衡二叉树又称为 AVL 树，是一种特殊的**[二叉排序树][Link 6]**。其左右子树都是平衡二叉树，且左右子树高度之差的绝对值不超过 1。

一句话表述为：以树中所有结点为根的树的左右子树高度之差的绝对值不超过 1。

将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子 BF，那么平衡二叉树上的所有结点的平衡因子只可能是-1、  
0 和 1。只要二叉树上有一个结点的平衡因子的绝对值大于 1，则该二叉树就是不平衡的。

② 红黑树（RBTree）

红黑树是一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树，相对于要求严格的 AVL 树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，通常使用红黑树。

性质：

*  每个节点非红即黑；
 *  根节点是黑的；
 *  每个叶节点（叶节点即树尾端 NULL 指针或 NULL 节点）都是黑的；
 *  如果一个节点是红色的，则它的子节点必须是黑色的；
 *  对于任意节点而言，其到叶子点树 NULL 指针的每条路径都包含相同数目的黑节点；

③ 区别

AVL 树是高度平衡的，频繁的插入和删除，会引起频繁的 rebalance，导致效率下降；红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。

### 2、请你回答一下 map 底层为什么使用红黑树实现？ ###

参考答案：

红黑树是一种弱平衡二叉树，相对于要求严格的 AVL 树来说，它的旋转次数少，所以对于搜索，插入，  
删除操作较多的情况下，通常使用红黑树。

### 3、请你说一说 map 和 和 unordered\_map 的底层实现？ ###

参考答案：

map 底层是基于红黑树实现的，因此 map 内部元素排列是有序的。而 unordered\_map 底层则是基于哈希表实  
现的，因此其元素的排列顺序是杂乱无序的。

### 4、请你回答一下 map 和 和 unordered\_map  优点和缺点。 ###

参考答案：

**① 对于 map，其底层是基于红黑树实现的。**

**优点如下：**

1)有序性，这是 map 结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作。

2)map 的查找、删除、增加等一系列操作时间复杂度稳定，都为 logn。

**缺点如下：**  
1）查找、删除、增加等操作平均时间复杂度较慢，与 n 相关

**② 对于 unordered\_map 来说，其底层是一个哈希表**

优点如下：

查找、删除、添加的速度快，时间复杂度为常数级 O(c)

缺点如下：  
因为 unordered\_map 内部基于哈希表，以（key,value）对的形式存储，因此空间占用率高。

unordered\_map 的查找、删除、添加的时间复杂度不稳定，平均为 O(c)，取决于哈希函数。极端情况下可能为O(n)

### 5、  请你回答一下 epoll 。 ###

参考答案：

Linux **epoll 机制**是通过**红黑树**和**双向链表**实现的。

首先通过 **epoll\_create()**系统调用在内核中创建一个eventpoll 类型的句柄，其中包括**红黑树根节点**和**双向链表头节点**。

然后通过 **epoll\_ctl()**系统调用，向 epoll 对象的红黑树结构中添加、删除、修改感兴趣的事件，成功返回0， 失败返回-1。

最后通过 **epoll\_wait()**系统调用判断双向链表是否为空，如果为空则阻塞。当文件描述符状态改变，fd 上的回调函数被调用，该函数将 fd 加入到双向链表中，此时 epoll\_wait 函数被唤醒，返回就绪好的事件。

[Link 1]: https://www.nowcoder.com/ta/review-c
[C_C]: https://blog.csdn.net/qq_26079093/article/details/100045170
[Link 2]: https://blog.csdn.net/qq_26079093/article/details/100023882
[Link 3]: https://blog.csdn.net/qq_26079093/article/details/100046606
[Link 4]: https://blog.csdn.net/qq_26079093/article/details/100060547
[Link 5]: https://blog.csdn.net/qq_26079093/article/details/100060114
[Link 6]: https://blog.csdn.net/isunbin/article/details/81703762