树结构

二叉排序树，缺陷：在极端情况下，一个有序序列会退化成链表

所以，要使用平衡树来进行调节

为什么要保证树的平衡？ 因为树的查询效率取决于树的高度，让树尽可能的平衡，就是为了减少树的高度。

那B树的作用是什么？

B树又叫多路查找树，每个结点可以拥有多于两个孩子结点。m路B树最多就可以拥有m个孩子结点

image-20220925162730234

这是棵三路B树。为什么要设计成多路？就是为了进一步降低树的高度。路数越多，树就越低。那路数无限大，不就更好？

为什么文件系统的索引使用B树，而不使用红黑树或者是有序数组？

文件系统或者数据库的索引是存储在硬盘上的，如果数据量越大，就不能一次性的加载到内存。这时候，能够体现B树的多路存储作用，每次加载B树的一个结点，然后一步一步往下找。

image-20220925163551755

假设内存一次性只能加载两个树，这时候有序数组【25，25，30，40，43，45，50，59，65，77，85】是不能够一次性加载到内存的，所以，可以构建三路B树，每个结点至多有两个数。

那B+树有什么作用？

image-20220925164941429

这是一棵4路B+树，数据都在叶子结点，并且通过链表相连。

使用场景：比如select查询多条数据，B树可能需要做中序遍历，跨层访问，而B+树所有的数据都在叶子结点，同时拥有链表结构，只需要找到首尾，就可以把所有数据取出来。

mysql存储索引使用的是B+树。

B+树查询效率与树的高度有关，O(logn),而hash查询索引效率O(1),hash比B+树更快，为什么要用B+树，而不用hash?

1.只查询一个数据，确实是hash更快，单数据库经常查询的是多条数据，这时候B+树索引有序，又有链表相连，查询效率要比hash快很多。2.前面提到，数据库索引一般存储在磁盘，如果数据量大，一次可能无法装入内存，B+树可以分批加载，树的高度越低，可以提高查询效率。

N叉树如何遍历

1
2
3
4
5
6
7
8
9
class TreeNode {
    int val;
    TreeNode[] children;
}

void traverse(TreeNode root) {
    for (TreeNode child : root.children)
        traverse(child);
}

341. 扁平化嵌套列表迭代器

实际考察的就是N叉树的遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class NestedInteger{
    private Integer value;
    private List<NestedInteger> list;
    public NestedInteger(Integer value,List<NestedInteger> list){
        this.value=value;
        this.list = list;
    }
    public boolean isInteger(){
        return value != null;
    }
    public Integer getInteger(){
        return this.value;
    }
    public List<NestedInteger> getList(){
        return this.list;
    }
}

其数据结构其实就是一棵N叉树（好好感受）

解法：将所有叶子节点的值都放到一个res集合中，next()和hasNext()在res做迭代【这种方法，消耗内存大，需要获得所有的叶子节点值】

一般的迭代器求值应该是惰性的，也就是说，如果你要一个结果，我就算一个（或是一小部分）结果出来，而不是一次把所有结果都算出来

思路：调用 hasNext时，如果 nestedList 的第一个元素是列表类型，则不断展开这个元素，直到第一个元素是整数类型