树
一、 树
树(Tree)是元素的集合，每棵树由多个节点（node）组成，用以储存元素。某些节点之间存在着一定的关系，用连线表示，连线称为边（edge）或者链接。边的上端点称为父节点，下端称为子节点。每个节点可以有多个子节点，而该节点则是相应子节点的父节点。但是每个节点只能有一个父节点（只有一个例外，也就是根节点，它没有父节点），如图中第一棵树的 S 节点即为根节点。而没有子节点的节点则称为叶子节点或叶节点，如上图中第一棵树的 A、R、X 节点。E、X 的父节点是一个节点，所以它们被称为兄弟节点。
特性
1树是元素的集合
2该集合可以为空。此时树中没有元素，称之为空树（empty tree）。
3如果该集合不为空，那么该集合至少含有一个根节点以及 0 个或多个子树。根节点与它的子树的根节点用一个边（edge）或链接相连。
节点n的高度 : n节点到叶子节点所有路径上包含节点个数的最大值。叶子节点的高度为1，往上节点的高度依次递增。
节点n的深度 : 从根节点到节点n唯一的路径的长，根节点深度为1
层数：根节点为第一层，往下一次递增。
阶数：m阶为一节点至多有m棵子树 ，也就是说B树上的结点最多只能有m棵子树
二、 二叉树
1 定义
二叉树是一种特殊的数据结构，顾名思义，二叉树只有两个叉，也就是两个子节点：左子节点和右子节点。其中，左子节点是左子树的根节点，右子节点是右子树的根节点。当然，这并不是说，二叉树一定要求每个节点都必须有两个子节点，有的节点只有左子节点，而有的节点只有右子节点。
编号 2 和 3 的这两个。其中，编号 2 的二叉树中，叶节点全都在最底层，除了叶节点之外，每个节点都于左右两个子节点，这种二叉树就叫满二叉树。而编号为 3 的二叉树中，叶子结点在最底下两层，其中，最后一层的节点都靠左排列，并且，除了最后一层，其他层的节点数都要达到最大，这种二叉树叫做完全二叉树。
1 满二叉树
满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值，所有叶子结点必须在同一层上。
满二叉树的性质：
1) 一颗树深度为h，最大层数为k，深度与最大层数相同，k=h;
2) 叶子数为2h;
3) 第k层的结点数是：2k-1;
4) 总结点数是：2k-1，且总节点数一定是奇数。
2 完全二叉树
若设二叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树
注：完全二叉树是效率很高的数据结构，堆是一种完全二叉树或者近似完全二叉树，所以效率极高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化，二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全二叉树。
二叉树的性质：
1) 在非空二叉树中，第i层的结点总数不超过2i-1, i>=1;
2) 深度为h的二叉树最多有2h-1个结点(h>=1)，最少有h个结点;
3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1;
4) 具有n个结点的完全二叉树的深度为log2(n+1);
5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
若I为结点编号则 如果I>1，则其父结点的编号为I/2；
如果2I<=N，则其左儿子（即左子树的根结点）的编号为2I；若2I>N，则无左儿子；
如果2I+1<=N，则其右儿子的结点编号为2I+1；若2I+1>N，则无右儿子。
6)给定N个节点，能构成h(N)种不同的二叉树，其中h(N)为卡特兰数的第N项，h(n)=C(2*n, n)/(n+1)。
7)设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i。
2 二叉树的三种遍历方法
前序遍历（也叫先序遍历）：若二叉树为空，则空操作，否则，对于二叉树中的任意节点，先访问这个节点，然后再访问它的左子树，最后打印它的右子树。
中序遍历：若二叉树为空，则空操作，否则，对于二叉树中的任意节点，先访问它的左子树，然后再访问这个节点本身，最后访问它的右子树。
后序遍历：若二叉树为空，则空操作，否则，对于二叉树中的任意节点，先访问它的左子树，然后访问它的右子树，最后访问这个节点本身。
3二叉查找树（二叉排序树）
二叉查找树（Binary Search Tree，BST）是一种特殊的二叉树，一棵二叉搜索树（BST）是一棵二叉树，其中，每个节点的值都要大于其左子树中任意节点的值而小于右子树中任意节点的值。
二叉查找树的性质：对二叉查找树进行中序遍历，即可得到有序的数列。
二叉查找树的时间复杂度：它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。
我们追求的是在最坏的情况下仍然有较好的时间复杂度，这就是平衡查找树设计的初衷。
二叉查找树的高度决定了二叉查找树的查找效率。
1 二叉查找树的插入过程如下：
1) 若当前的二叉查找树为空，则插入的元素为根节点;
2) 若插入的元素值小于根节点值，则将元素插入到左子树中;
3) 若插入的元素值不小于根节点值，则将元素插入到右子树中。
2二叉查找树的删除，分三种情况进行处理：
1) p为叶子节点，直接删除该节点，再修改其父节点的指针（注意分是根节点和不是根节点），如图a;
2) p为单支节点（即只有左子树或右子树）。让p的子树与p的父亲节点相连，删除p即可（注意分是根节点和不是根节点），如图b;
3) p的左子树和右子树均不空。找到p的后继y，因为y一定没有左子树，所以可以删除y，并让y的父亲节点成为y的右子树的父亲节点，并用y的值代替p的值；或者方法二是找到p的前驱x，x一定没有右子树，所以可以删除x，并让x的父亲节点成为y的左子树的父亲节点。如图c。
4 平衡二叉树（AVL树）
我们知道，对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度O(log2n)同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况，但是在进行了多次的操作之后，由于在删除时，我们总是选择将待删除节点的后继代替它本身，这样就会造成总是右边的节点数目减少，以至于树向左偏沉。这同时也会造成树的平衡性受到破坏，提高它的操作的时间复杂度。于是就有了我们下边介绍的平衡二叉树。
1 平衡二叉树简介
平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用算法有红黑树、AVL树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O(log2n)，大大降低了操作的时间复杂度。
（1）要么是棵空树，要么其根节点左右子树的深度之差的绝对值不超过1；
（2）其左右子树也都是平衡二叉树；
（3）二叉树节点的平衡因子定义为该节点的左子树的深度减去右子树的深度。则平衡二叉树的所有节点的平衡因子只可能是-1,0,1。
2 红黑树
它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(logn)时间内做查找，插入和删除，这里的n是树中元素的数目。
它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(logn)时间内做查找，插入和删除，这里的n是树中元素的数目。
红黑树是一种自平衡二叉树，在平衡二叉树的基础上每个节点又增加了一个颜色的属性，节点的颜色只能是红色或黑色。具有以下性质：
（1）根节点只能是黑色；
（2）红黑树中所有的叶子节点后面再接上左右两个空节点，这样可以保持算法的一致性，而且所有的空节点都是黑色；
（3）其他的节点要么是红色，要么是黑色，红色节点的父节点和左右孩子节点都是黑色，及黑红相间；
（4）在任何一棵子树中，从根节点向下走到空节点的路径上所经过的黑节点的数目相同，红黑树确保没有一条路径会比其他路径长出两倍，因而近乎平衡的。
三 B B+树
1 B-树
B树也是一种用于查找的平衡树，但是它不是二叉树。
B树的定义：B树（B-tree）是一种树状数据结构，能够用来存储排序后的数据。这种数据结构能够让查找数据、循序存取、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树，可以拥有多于2个子节点。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。这种数据结构常被应用在数据库和文件系统的实作上。
- 树中每个节点至多有m棵子树；
- 若根节点不是叶子节点，则至少有2棵子树；
- 除根节点之外的所有非终端节点至少有
棵子树
- 每个节点中的信息结构为（A0,K1,A1,K2......Kn,An），其中n表示关键字个数，Ki为关键字，Ai为指针；且Ai-1所指子树中所有结点的关键字均小于Ki，An所指子树中所有结点的关键字均大于Kn；
- 所有的叶子节点都出现在同一层次上，且不带任何信息，也是为了保持算法的一致性。
2 B+树
定义：一颗m阶的B+树与m阶的B-树的区别是：
（1）一个节点的关键字树和子树数相等；
（2）所有的叶子节点包含了全部的关键字信息。及指向含这些关键字记录的指针，且叶子节点本身依据关键字的大小由小到大排列。
（3）所有非终端节点可以看成是索引部分，节点中仅包含其子树中最大（或最小）的关键字。
3 B-树与B+树作为索引的区别：
（1）B+树索引更加稳定，均需索引至叶子节点为止：因为B+树的所有叶子节点包含全部的关键字信息；
（2）在文件系统中进行索引时，速度快：因为B+树的非终端节点不包含卫星数据，因此每个磁盘页能够存储更多的关键字，减少了IO次数，大大提高检索效率；
（3）进行范围查找时，B+树具有更高的效率：因为B+树的的所有叶子节点依据关键字的大小排列，并以链表形式连接，只要找到范围的下限，顺着链表就能找到该范围内的所有数据。
四 字典树
字典树是一种以树形结构保存大量字符串。以便于字符串的统计和查找，经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。
(1）根节点为空；
（2）除根节点外，每个节点包含一个字符；
（3）从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
（4）每个字符串在建立字典树的过程中都要加上一个区分的结束符，避免某个短字符串正好是某个长字符串的前缀而淹没。
优点：
可以最大限度地减少无谓的字符串比较，故可以用于词频统计和大量字符串排序。
跟哈希表比较：
1，最坏情况时间复杂度比hash表好
2，没有冲突，除非一个key对应多个值（除key外的其他信息）
3，自带排序功能（类似Radix Sort），中序遍历trie可以得到排序。
缺点：
1，虽然不同单词共享前缀，但其实trie是一个以空间换时间的算法。其每一个字符都可能包含至多字符集大小数目的指针（不包含卫星数据）。
每个结点的子树的根节点的组织方式有几种。1>如果默认包含所有字符集，则查找速度快但浪费空间（特别是靠近树底部叶子）。2>如果用链接法(如左儿子右兄弟)，则节省空间但查找需顺序（部分）遍历链表。3>alphabet reduction: 减少字符宽度以减少字母集个数。,4>对字符集使用bitmap，再配合链接法。
2，如果数据存储在外部存储器等较慢位置，Trie会较hash速度慢（hash访问O(1)次外存，Trie访问O(树高)）。
3，长的浮点数等会让链变得很长。可用bitwise trie改进。
参考链接
https://blog.csdn.net/dreamzuora/article/details/88029949
https://blog.csdn.net/weixin_39778570/article/details/81990417
京公网安备 11010502036488号