alin的学习之路：面试题 数据结构相关
alin的学习之路：面试题 数据结构相关
-
hash处理冲突的方法
- 再散列：H（key）+ di ，指定di的值，再进行计算得出一个下标
- 再哈希：重新指定一个哈希函数
- 链地址法：哈希表的每一个位置都是一个指针，指向一个链表
- 建立公共溢出区
-
二分查找及其变种
- left和right，找mid。
int mid = left+(right-left)/2; - 查找第一个与key相等的元素，也就是说等于查找key值的元素有很多，返回这些元素最左边的元素的下标。
- 查找最后一个与key相等的元素，也就是等于查找key值的元素有好多个，返回这些元素最右边元素的下标。
- 二分查找注意中间比较时的符号即可
- left和right，找mid。
-
数组与链表的区别
- 数组在内存中时连续存储的
- 链表在底层是跳跃存储的
-
红黑树比平衡二叉树有哪些优点
- 红黑树能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作。此外,任何不平衡都会在3次旋转之内解决。这一点是AVL所不具备的。
- 区别：AVL树是高度平衡的，频繁的插入和删除，会引起频繁的rebalance，导致效率下降；红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。
-
二叉树，b+树，hash，二叉查找树，B-树区别
-
二叉树仅仅是每一个节点最多有两个子节点，这就叫做二叉树
-
B+树
-
根节点至少有两个子女，可以有很多个
-
每一个父节点的元素都出现在子节点中，作为最大或最小元素。根节点的最大元素是整个树的最大元素
-
每一个叶子节点都带有指向下一个叶子节点的指针，形成了一个有序链表
-
在B+树中，只有叶子节点带有卫星数据，其余中间节点仅仅是索引，没有任何数据关联。（卫星数据：指的是索引元素所指向的数据记录）
-
B+树的好处在于查询性能上，B+树的查询较稳定，而且查询多个数据的时候，可以在链表上进行遍历。单一节点存储更多的元素，使得查询的IO次数更少。
-
-
hash树
- hash树的查找更加方便，仅用质数作为因数进行分辨
- 每一层上的数据都是对应数字对2 3 5取余剩下的数相同即放在对应的位置
- 图解：有一组元素，按照顺序向hash树中插入元素，取余找位置插入。我们以下图中的 “68” 为例子，68先对2取余得0，但是0位置上有人了，继续对3取余得2，2得位置上也有人了，那就继续对5取余得3，3得位置上没有人则插入 到3的位置。
-
B-树（不读B减树，读作B树）
-
根结点至少有两个子女。
-
每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
-
每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
-
所有的叶子结点都位于同一层。
-
每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
- -
-
-
二叉查找树
- 根节点大于左子节点大于右子节点
-
-
说说红黑树的特性
- 每个节点只能是红色或者黑色。
- 根节点必须是黑色。
- 红色的节点，它的叶节点只能是黑色。
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
- 特性：从根基节点到最远叶节点的路径（最远路径）肯定不会大于根基节点到最近节点的路径（最短路径）的两倍长。这是因为性质3保证了没有相连的红色节点，性质4保证了从这个节点出发的不管是哪一条路径必须有相同数目的黑色节点，这也保证了有一条路径不能比其他任意一条路径的两倍还要长
-
各种树，排序的时间复杂度
-
为何数据库要使用树的结构
- 为了减少磁盘IO的次数，磁盘IO的次数影响查询磁盘内容的效率，树的高度越高，磁盘IO的次数越多
-
为何数据库要使用树的结构
- 为了减少磁盘IO的次数，磁盘IO的次数影响查询磁盘内容的效率，树的高度越高，磁盘IO的次数越多
-
AC自动机时间复杂度