3.2 Data Structure Flashcards

Question 1

Q

什么是堆/Heap？

Answer

A

堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

Question 2

Q

什么是完全二叉树(Complete)？满二叉树(Full)？平衡二叉树？

Answer

A

完全二叉树:叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。

满二叉树（国内教程定义）:一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

平衡二叉树（Balanced BinaryTree）又被称为AVL树。它具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

Question 3

Q

什么是二叉查找树？

Answer

A

二叉查找树的特点:

Question 4

Q

什么是红黑树？

Answer

A

红黑树是一种自平衡的二叉查找树

红黑树特点:
1. 每个节点非红即黑;
2. 根节点总是黑色的;
3. 每个叶子节点都是黑色的空节点(NIL节点);
4. 如果节点是红色的，则它的子节点必须是黑色的(反之不一定);
5. 从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点(即相同的黑色高
度)。

插入节点时可能的操作

Ref:

Question 5

Q

什么是B树, B+树，B*树？

Answer

A

B-树(或B树)是一种平衡的多路查找(又称排序)树，在文件系统中有所应用。主要用作文件的索引。其中的B就表示平衡(Balance)

B+树和B树的区别：
（1）B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；

（2）B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；

（3）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。支持range-query(区间查询)非常方便，而B树不支持。这是数据库选用B+树的最主要原因

（4）非叶子节点的子节点数=关键字数

B*树是B+树的变种，相对于B+树他们的不同之处如下：

（1）首先是关键字个数限制问题，B+树初始化的关键字初始化个数是cei(m/2)，b树的初始化个数为（cei(2/3m)）

（2）B+树节点满时就会分裂，而B*树节点满时会检查兄弟节点是否满（因为每个节点都有指向兄弟的指针），如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来；

B*树分配新结点的概率比B+树要低，空间使用率更高

Question 6

Q

什么是LSM树

Answer

A

B+树最大的性能问题是会产生大量的随机IO 为了克服B+树的弱点，HBase引入了LSM树的概念，即Log-Structured Merge-Trees。

-ref：https://www.cnblogs.com/yanghuahui/p/3483754.html

Brainscape's Knowledge GenomeTM