应届生面试要点总结（9）数据结构相关

Bertha 。 2022-03-25 16:42 243阅读 0赞

平衡二叉树：一个空树或者左右两个子树高度差绝对值不超过1，并且左右子树都是平衡二叉树。

建堆O(n)，调整堆O(logn)，对应一颗完全二叉树，优先级队列。

知道中序，且知道前序或者后续中任何一个就可以确定一个二叉树。

为什么要B树

磁盘中有两个机械运动的部分，分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟，而磁盘移动则是在盘片旋转到指定位置以后，移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程，而定位是磁盘的存取中花费时间比较大的一块，毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候，显然定位是一个非常花费时间的过程，但是我们可以通过B树进行优化，提高磁盘读取时定位的效率。

为什么B类树可以进行优化呢？我们可以根据B类树的特点，构造一个多阶的B类树，然后在尽量多的在结点上存储相关的信息，保证层数尽量的少，以便后面我们可以更快的找到信息，磁盘的I/O操作也少一些，而且B类树是平衡树，每个结点到叶子结点的高度都是相同，这也保证了每个查询是稳定的。

这里的B树，也就是英文中的B-Tree，一个 m 阶的B树满足以下条件：每个结点至多拥有m棵子树；根结点至少拥有两颗子树（存在子树的情况下）；除了根结点以外，其余每个分支结点至少拥有 m/2 棵子树；所有的叶结点都在同一层上；有 k 棵子树的分支结点则存在 k-1 个关键码，关键码按照递增次序进行排列；关键字数量需要满足ceil(m/2)-1 <= n <= m-1；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NFVVNVTkpN_size_16_color_FFFFFF_t_70][]

B树上大部分的操作所需要的磁盘存取次数和B树的高度是成正比的，在B树中可以检查多个子结点，由于在一棵树中检查任意一个结点都需要一次磁盘访问，所以B树避免了大量的磁盘访问。

由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引，而B树则常用于文件索引。

同样的，以一个m阶树为例：根结点只有一个，分支数量范围为\[2，m\]；分支结点，每个结点包含分支数范围为\[ceil(m/2), m\]；分支结点的关键字数量等于其子分支的数量减一，关键字的数量范围为\[ceil(m/2)-1, m-1\]，关键字顺序递增；所有叶子结点都在同一层；树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。

这都是由于B+树和B具有这不同的存储结构所造成的区别，以一个m阶树为例。

关键字的数量不同；B+树中分支结点有m个关键字，其叶子结点也有m个，其关键字只是起到了一个索引的作用，但是B树虽然也有m个子结点，但是其只拥有m-1个关键字。

存储的位置不同；B+树中的数据都存储在叶子结点上，也就是其所有叶子结点的数据组合起来就是完整的数据，但是B树的数据存储在每一个结点中，并不仅仅存储在叶子结点上。

分支结点的构造不同；B+树的分支结点仅仅存储着关键字信息和儿子的指针（这里的指针指的是磁盘块的偏移量），也就是说内部结点仅仅包含着索引信息。

查询不同；B树在找到具体的数值以后，则结束，而B+树则需要通过索引找到叶子结点中的数据才结束，也就是说B+树的搜索过程中走了一条从根结点到叶子结点的路径。

满二叉树：除叶子节点外所有节点均有两个子节点，叶子节点数达到最大，所有叶子节点都在同一层。

完全二叉树：满是完全的特例。

哈夫曼树：每个节点要么没有子节点，要么两个子节点。

单调栈：单调栈的维护是O(n)时间复杂度。所有元素只会进栈一次，并且出栈后再不会进栈。性质：单调栈里的元素有单调性。元素加入栈之前，会在栈顶把破坏单调性的元素删除。使用单调栈可以找到元素向左遍历第一个比它小的元素，也可找到元素向左遍历第一个比他大的元素。

存储结构分为四种：随机存取：可以随机直接存取任何一个元素，可以通过下标直接存取任意一个元素，如数组，内存，可以通过地址直接访问任何一个空间。顺序存取：只能从前往后逐个访问，如链表。索引存取：为某个关键字建立索引，从索引表中得到地址，再直接访问。散列存取：建立散列表。

一个包含n个节点的四叉树，每个节点都有4个指向孩子的指针，这个四叉树有多少个空指针？n个节点，一共4n个指针，除了root外，所有节点都用了一个指针，父节点指向它的，用了n-1个，剩下的就是3n+1个。

trie树，又称单词查找树，字典树，是一种树形结构，是一种hash树的变种，是一种用于快速检索的多叉树结构。其核心思想是：空间换时间。利用字符串的公共前缀来降低查询开销以达到提高效率的目的。tire树的性质：根节点不包含字符，除根外每个节点包含一个字符。从根到某个节点，路径经过的字符连起来，为该节点对应的字符串。每个节点的所有子节点包含的字符串不同。

红黑树是在普通二叉树上，对没个节点添加一个颜色属性形成的，同时整个红黑二叉树需要同时满足一下五条性质 ：

性质一：节点是红色或者是黑色；性质二：根节点是黑色；性质三：每个叶节点（NIL或空节点）是黑色；性质四：每个红色节点的两个子节点都是黑色的（也就是说不存在两个连续的红色节点）；性质五：从任一节点到其没个叶节点的所有路径都包含相同数目的黑色节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NFVVNVTkpN_size_16_color_FFFFFF_t_70 1][]

[https://blog.csdn.net/sun\_tttt/article/details/65445754][https_blog.csdn.net_sun_tttt_article_details_65445754]

二叉查找树BST添加节点

public void addNode(int num) \{

if (num < this.val) \{

if (this.left != null) \{

this.left.addNode(num);

\} else \{

this.left = new TreeNode(num);

if (this.right != null) \{

this.right.addNode(num);

\} else \{

this.right = new TreeNode(num);

哈夫曼编码

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NFVVNVTkpN_size_16_color_FFFFFF_t_70 2][]

WPL = 1x45+3x(13+12+16)+4x(5+9)=224

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NFVVNVTkpN_size_16_color_FFFFFF_t_70]: /images/20220325/cbf7648db02242638f6b1604a7c76318.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NFVVNVTkpN_size_16_color_FFFFFF_t_70 1]: /images/20220325/d873d3b3a80044238242cc699d83245d.png
[https_blog.csdn.net_sun_tttt_article_details_65445754]: https://blog.csdn.net/sun_tttt/article/details/65445754
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1NFVVNVTkpN_size_16_color_FFFFFF_t_70 2]: /images/20220325/5fa4a21a23414a8bae8fe633b91f3e5e.png