Alg.12.数据结构-树

简单二叉树

二叉树遍历

• 先序(preOrder): 中-左-右
• 中序(inOrder): 左-中-右
• 后序(postOrder): 左-右-中

图来自 http://www.crystaltenn.com/2020/04/binary-trees-traversal-recursive-vs.html

➤ 先序遍历(递归):

public void preOrder(Node<T> n) {
    System.out.println(n.data);  // 先序

    if (n.left != null)
        preOrder(n.left);
    // System.out.println(n.data);  // 中序
    if (n.right != null)
        preOrder(n.right);
    // System.out.println(n.data);  // 后序
}

➤ 先序-非递归, 最简单的一种:

public void preOrder(Node root) {

    Stack s = new Stack();
    s.push(root);
    while(!s.isEmpty()) {
        Node n = s.pop(); // 刚开始就pop了, 这种只能用来做先序
        System.out.println(n.data); // 先序
        if(n.right != null) {
            s.push(n.right);
        }
        if(n.left != null) {
            s.push(n.left);
        }
    }
}

➤ 先序-非递归(方法 2), 使用栈模拟递归:

public void preOrder(Node root) {
    Stack s = new Stack();
    while(!s.isEmpty() || root != null) {
        if(root != null) {
            System.out.println(root.data); // 先序
            s.push(root);
            root = root.left;
        } else {
            root = s.pop();
            // System.out.println(root.data); // 中序
            root = root.right;
        }
    }
}

➤ 中序-非递归与上面类似

➤ 后序-非递归(需要辅助栈):

• Push 根结点到第一个栈 s1中。
• 从第一个栈 s1 中 Pop 出一个结点，并将其 Push 到第二个栈 output 中。
• 然后 Push 该结点的左孩子和右孩子到第一个栈 s 中。
• 重复过程 2 和 3 直到栈 s 为空。
• 完成后，所有结点已经 Push 到栈 output 中，且按照后序遍历的顺序存放，直接全部 Pop 出来即是二叉树后序遍历结果。

public void postOrder(Node root) {
    Stack s1 = new Stack();
    Stack s2 = new Stack();

    s1.push(root);
    while(!s1.isEmpty) {
        Node curr = s1.pop();
    
        s2.push(curr);
        if(curr.left !=null) {
            s1.push(curr.left);
        }
        if(curr.right !=null) {
            s1.push(curr.right);
        }
    }

    while(!s2.isEmpty()) {
        Node curr = s2.pop();
        System.out.println(cur.data);
    }

}

➤ 层序遍历（非递归算法）:
第一个队列 currentLevel 用于存储当前层的结点，第二个队列 nextLevel 用于存储下一层的结点。当前层 currentLevel 为空时，表示这一层已经遍历完成，可以打印换行符了。
然后将第一个空的队列 currentLevel 与队列 nextLevel 交换，然后重复该过程直到结束。
如果不需要打印\n区分层，那么只用一个队列即可实现

public void levelOrder(Node root) {
    Queue<Node> currentLevel = new Queue();
    Queue<Node> nextLevel = new Queue();

    currentLevel.offer(root);
    while(!currentLevel.isEmpty()) {
        currNode = currentLevel.poll();
        if(currNode) {
            print(currNode);
            nextLevel.offer(currNode.left);
            nextLevel.offer(currNode.right);
        }
        if(currentLevel.isEmpty()) {
            print("/n");
            swap(currentLevel, nextLevel);
        }
    }
}

https://blog.csdn.net/sgbfblog/article/details/7773103

节点删除/插入

• 数据结构（七）：二叉树的删除和应用举例

AVL 树

@ref:

• 平衡二叉树
• 代码实现平衡二叉树

AVL 树（Adelson-Velsky and Landis Tree，发明者名字）的产生是为了解决二叉排序树在插入时发生线性排列的现象。由于二叉排序树本身为有序，当插入一个有序程度十分高的序列时，生成的二叉排序树会持续在某个方向的字数上插入数据，导致最终的二叉排序树会退化为链表，从而使得二叉树的查询和插入效率恶化。

AVL 树的出现能够解决上述问题，但是在构造平衡二叉树时，却需要采用不同的调整方式，使得二叉树在插入数据后保持平衡。主要的四种调整方式有 LL（左旋）、RR（右旋）、LR（先左旋再右旋）、RL（先右旋再左旋）。

在插入一个结点后应该沿搜索路径将路径上的结点平衡因子进行修改，当平衡因子大于 1 时，就需要进行平衡化处理。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点，如果这三个结点在一条直线上，则采用单旋转进行平衡化，如果这三个结点位于一条折线上，则采用双旋转进行平衡化

旋转

AVL 树在插入/删除节点后, 需要用旋转的操作重新平衡;

概念: 「节点的平衡因子」 每个结点的平衡因子就是该结点的左子树的高度减去右子树的高度，平衡二叉树的每个结点的平衡因子的绝对值不会超过 2

左旋：将当前结点 S 的左孩子旋转为当前结点父结点 E 的右孩子，同时将父结点 E 旋转为当前结点 S 的左孩子。可用动画表示：

右旋：将当前结点 S 的左孩子 E 的右孩子旋转为当前结点 S 的左孩子，同时将当前结点 S 旋转为左孩子 E 的右孩子。可用动画表示：

以下图表以 4 列表示 4 种需要重新做平衡的情况, Root 是失去平衡树的根节点(左右子树高度差大于 1)

• 左左（LL）: 失衡节点 root 的左子树更高, root 左子树的左子树更高
• 右右（RR）:
• 左右（LR）: 失衡节点 root 的左子树更高, root 左子树的右子树更高
• 右左（RL）:

图: 四种情况的旋转(Root 是失去平衡树的根节点，Pivot 是旋转后重新平衡树的根节点),
可以看到需要1~2 次旋转即可使不平衡节点重新平衡:

删除的情况

AVL 树删除一个节点，最坏情况下需要 logN 次旋转 才能恢复平衡性质（需要回溯到根节点）。
插入节点是子树高度加1，旋转会将子树高度减1，因此一次旋转即可恢复平衡；
删除节点是子树高度减1，旋转可能会将高度再次减1，这可能会触发再次旋转。

删除节点 X 之后，R4的平衡因子变为 -2，R4 左旋；
R3 的平衡因子变为 2，R3 右旋；
R2 的平衡因子变为 -2， R2左旋；
R1的平衡因子变为2，R1 右旋……
当从根节点至待删除节点的父节点平衡因子交替为 -1 和 +1，删除该节点一旦触发旋转就需要 logn 次旋转 （回溯至根节点）。

@ref: 二叉树04.深度分析AVL树的实现与优化 - 极客志 - OSCHINA - 中文开源技术交流社区

复杂度分析

• 查找: 可以像普通二叉查找树一样的进行，所以耗费 O(log n)时间，因为 AVL 树总是保持平衡的

• 插入: 向 AVL 树插入，可以透过如同它是未平衡的二叉查找树一样，把给定的值插入树中，接着自底往上向根节点折回，于在插入期间成为不平衡的所有节点(平衡因子>1, 即左右子树高度差)上进行旋转来完成。上面分析了四种情况, 旋转1~2次即可完成, 所以也是 O(log n)

• 删除:
  • 先看二叉查找树(BST)的删除操作: 当删除一个结点 P，首先需要定位到这个结点 P，这个过程需要一个查找的代价。然后稍微改变一下树的形态。如果被删除结点的左、右子树只有一个存在，则改变形态的代价仅为 O(1)。如果被删除结点的左、右子树均存在，只需要将当 P 的左孩子的右孩子的右孩子的…的右叶子结点与 P 互换(左的右右右, 也即比 P 小但是 P 最大的孩子 )，再改变一些左右子树即可。因此删除操作的时间复杂度最大不会超过 O(logN)。
  • 如果从 AVL 树中删除，AVL 删除结点的算法可以参见上面 BST 的删除结点，但是删除之后必须检查从删除结点开始到根结点路径上的所有结点的平衡因子。因此删除的代价稍微要大一些。每一次删除操作最多需要 O(logN)次旋转。因此，删除操作的时间复杂度最大为 O(2logN)

红黑树

红黑树的 5 个性质:

• 每个结点要么是红的要么是黑的。
• 根结点是黑的。
• 每个叶结点（叶结点即指树尾端 NIL 指针或 NULL 结点）都是黑的。
• 如果一个结点是红的，那么它的两个儿子都是黑的。
• 对于任意结点而言，其到叶结点树尾端 NIL 指针的每条路径都包含相同数目的黑结点。

正是红黑树的这 5 条性质，使一棵 n 个结点的红黑树始终保持了 logn 的高度，从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为 O(log n)”这一结论成立的原因。

红黑树通过将结点进行红黑着色，使得原本高度平衡的树结构被稍微打乱，平衡程度降低。红黑树不追求完全平衡，只要求达到部分平衡。这是一种折中的方案，大大提高了结点删除和插入的效率。C++中的 STL 就常用到红黑树作为底层的数据结构。

下图中，”叶结点” 或着叫”NULL 结点”，它不包含数据而只充当树在此结束的指示，这些节点在绘图中经常被省略

插入和删除

@ref: https://github.com/julycoding/The-Art-Of-Programming-By-July-2nd/blob/master/ebook/zh/03.01.md

复杂度分析

正是红黑树的这5条性质，使得一棵 n 个结点是红黑树始终保持了logn 的高度，从而也就解释了上面我们所说的“红黑树的查找、插入、删除的时间复杂度最坏为 O(log n)”这一结论的原因

B 树 & B+树

[[../32.Database/MySQL-02b-BTree索引原理]]

比较几种二叉树的复杂度

➤ 二叉查找树 (Binary Search Tree) 的操作代价分析：

• (1) 查找代价： 任何一个数据的查找过程都需要从根结点出发，沿某一个路径朝叶子结点前进。因此查找中数据比较次数与树的形态密切相关。

  当树中每个结点左右子树高度大致相同时，树高为 logN。则平均查找长度与 logN 成正比，查找的平均时间复杂度在 O(logN)数量级上。

  当先后插入的关键字有序时，BST 退化成单支树结构。此时树高 n。平均查找长度为(n+1)/2，查找的平均时间复杂度在 O(N)数量级上。

• (2) 插入代价： 新结点插入到树的叶子上，完全不需要改变树中原有结点的组织结构。插入一个结点的代价与查找一个不存在的数据的代价完全相同。

• (3) 删除代价： 当删除一个结点 P，首先需要定位到这个结点 P，这个过程需要一个查找的代价。然后稍微改变一下树的形态：如果被删除结点的左、右子树只有一个存在，则改变形态的代价仅为 O(1)。如果被删除结点的左、右子树均存在，只需要将当 P 的左孩子的右孩子的右孩子的…的右叶子结点与 P 互换，在改变一些左右子树即可。因此删除操作的时间复杂度最大不会超过 O(logN)。

BST 效率总结 :

• 查找最好时间复杂度 O(logN)，最坏时间复杂度 O(N)。
• 插入删除操作算法简单，时间复杂度与查找差不多

➤ AVL（带平衡条件的 BST） 的操作代价分析：

• (1) 查找代价： AVL 是严格平衡的 BST（平衡因子不超过 1）。那么查找过程与 BST 一样，只是 AVL 不会出现最差情况的 BST(单支树)。因此查找效率最好、最坏情况都是 O(logN)数量级的。

• (2) 插入代价： AVL 必须要保证严格平衡(|bf|<=1)，那么每一次插入数据使得 AVL 中某些结点的平衡因子超过 1 就必须进行旋转操作。事实上，AVL 的每一次插入结点操作最多只需要旋转 1 次(单旋转或双旋转)。因此，总体上插入操作的代价仍然在 O(logN)级别上(插入结点需要首先查找插入的位置)。

• (3) 删除代价：AVL 删除结点的算法可以参见 BST 的删除结点，但是删除之后必须检查从删除结点开始到根结点路径上的所有结点的平衡因子。因此删除的代价稍微要大一些。每一次删除操作最多需要 O(logN)次旋转。因此，删除操作的时间复杂度为 O(logN)+O(logN)=O(2logN)

AVL 效率总结 :

• 查找的时间复杂度维持在 O(logN)，不会出现最差情况
• AVL 树在执行每个插入操作时最多需要 1 次旋转，其时间复杂度在 O(logN)左右。
• AVL 树在执行删除时代价稍大，执行每个删除操作的时间复杂度需要 O(2logN)。

➤ 红黑树 (Red-Black Tree)：

二叉平衡树的严格平衡策略，以牺牲插入、删除操作的代价，换来了稳定的 O(logN) 的查找时间复杂度。但是这样做是否值得呢？ 能不能找一种折中策略，即不牺牲太大的建立查找结构的代价，也能保证稳定高效的查找效率呢？ 答案就是：红黑树。

RBT 的操作代价分析：

• (1) 查找代价：由于红黑树的性质(最长路径长度不超过最短路径长度的 2 倍)，可以说明红黑树虽然不像 AVL 一样是严格平衡的，但平衡性能还是要比 BST 要好。其查找代价基本维持在 O(logN)左右，但在最差情况下(最长路径是最短路径的 2 倍少 1)，比 AVL 要略逊色一点。

• (2) 插入代价：RBT 插入结点时，需要旋转操作和变色操作。但由于只需要保证 RBT 基本平衡就可以了。因此插入结点最多只需要 2 次旋转，这一点和 AVL 的插入操作一样。虽然变色操作需要 O(logN)，但是变色操作十分简单，代价很小。

• (3) 删除代价：RBT 的删除操作代价要比 AVL 要好的多，删除一个结点最多只需要 3 次旋转操作。

RBT 效率总结 :

• 查找效率最好情况下时间复杂度为 O(logN)，但在最坏情况下比 AVL 要差一些，但也远远好于 BST。
• 插入和删除操作改变树的平衡性的概率要远远小于 AVL（RBT 不是严格高度平衡的）。因此需要的旋转操作的可能性要小，而且一旦需要旋转，插入一个结点最多只需要旋转 2 次，删除最多只需要旋转 3 次(小于 AVL 的删除操作所需要的旋转次数)。虽然变色操作的时间复杂度在 O(logN)，但是实际上这种操作由于简单所需要的代价很小。

➤ B 树/B+树 (B-Tree) ：

对于在内存中的查找结构而言，红黑树的效率已经非常好了(实际上很多实际应用还对 RBT 进行了优化)。但是如果是数据量非常大的查找呢？将这些数据全部放入内存组织成 RBT 结构显然是不实际的。
在磁盘中组织查找结构，从任何一个结点指向其他结点都有可能读取一次磁盘数据，再将数据写入内存进行比较。显而易见，所有的二叉树的查找结构在磁盘中都是低效的。因此， B-Tree 很好的解决了这一个问题。

B-Tree 的操作代价分析：

B-Tree 查找代价 = $O\log_M N$，M是度数 @link [[../32.Database/MySQL-02b-BTree索引原理]]

• (1) 查找代价： B-Tree 作为一个平衡多路查找树(m叉)。B 树的查找分成两种：一种是从一个结点查找另一结点的地址的时候，需要定位磁盘地址(查找地址)，查找代价极高。另一种是将结点中的有序关键字序列放入内存，进行优化查找(可以用折半)，相比查找代价极低。而 B 树的高度很小，因此在这一背景下，B 树比任何二叉结构查找树的效率都要高很多。

• (2)插入代价： B-Tree 的插入会发生结点的分裂操作。当插入操作引起了 s 个节点的分裂时，磁盘访问的次数为 h(读取搜索路径上的节点)＋2s(回写两个分裂出的新节点)＋1（回写新的根节点或插入后没有导致分裂的节点）。因此，所需要的磁盘访问次数是 h+2s+1，最多可达到 3h+1。因此插入的代价是很大的。

• (3)删除代价：B-Tree 的删除会发生结点合并操作。最坏情况下磁盘访问次数是 3h＝（找到包含被删除元素需要 h 次读访问）+（获取第 2 至 h 层的最相邻兄弟需要 h-1 次读访问）+（在第 3 至 h 层的合并需要 h-2次写
  访问）+（对修改过的根节点和第 2 层的两个节点进行 3 次写访问）

B-Tree 效率总结： 由于考虑磁盘储存结构，B 树的查找、删除、插入的代价都远远要小于任何二叉结构树(读写磁盘次数的降低)。

@ref: https://blog.csdn.net/keda8997110/article/details/45057081

字典树（Trie）

字典树的构建：

• 节点包含一个 size=26 的数组，下标对应 az，值是指向后续字符的指针，此外节点还有一个 flag 标识字符串是否结束（可选）
• 根节点不表示任何字符，但根节点的数组是指向子节点的；
• 每个子节点表示一个字符（有空间的浪费），改进方案是一个节点可以存储多个字符（压缩）

下图是一个字典树：

复杂度分析：

• 空间：O(n)
• 增/删/查：O(n)

使用场景：

• 一堆字符串的最长公共前缀（节点指向下层的指针=1，此节点即为公共前缀中的一个字母）；
• 统计词频：需要对 Node 的定义做一下修改，增加 freq 属性；

typedef struct node
{
    int value;// ASCII码
    int frequecy;//c出现的频率
    struct node* child[R]; //有R个孩子，初始为NULL
}Node;

问题实例：

1、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，给出时间复杂度分析

• 构建 Trie tree
• 用 Trie tree 统计每个词出现的次数，时间复杂度是 O(n*le)（le 表示单词的平均长度），然后是找出出现最频繁的前10个词。

2、寻找热门查询关键词： 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复读比较高，虽然总数是1千万，但是如果去除重复和，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。

提示：利用trie树，关键字域存该查询串出现的次数，没有出现为0。最后用10个元素的最小推来对出现频率进行排序。

@ref:

• 算法 - 用Trie树统计词频。 - hack - SegmentFault 思否
• 6.9 Trie树| 编程之法：面试和算法心得

线段树

@todo： 数据结构：线段树

优先队列(堆)

二叉堆就结构性质上来说就是一个完全填满的二叉树，满足树的结构性和堆序性。堆序性指的是：父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

• 数据结构：堆
• 堆排序和PriorityQueue源码解析