树

术语

  1. 节点的度：一个节点含有的子树的个数称为该节点的度；
  2. 树的度：一棵树中，最大的节点度称为树的度；
  3. 叶节点或终端节点：度为零的节点；
  4. 非终端节点或分支节点：度不为零的节点；
  5. 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
  6. 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
  7. 兄弟节点：具有相同父节点的节点互称为兄弟节点；
  8. 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
  9. 深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
  10. 高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；
  11. 堂兄弟节点：父节点在同一层的节点互为堂兄弟；
  12. 节点的祖先：从根到该节点所经分支上的所有节点；
  13. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
  14. 森林：由m（m>=0）棵互不相交的树的集合称为森林；

分类

平衡树

平衡树

二叉树

二叉树 |
堆 |
哈夫曼树 |
线段树 |

二叉搜索树

二叉搜索树BST |
AVL树 |
红黑树 |

多叉树

字典树/前缀树

多叉平衡树

B树 |
R树 |
2-3Tree

其它

树状数组 |
并查集

资料

树的遍历解题模板

树 wikipedia

数据结构与算法(3)——树（二叉、二叉搜索树）

分类

分类名称
二叉树二叉查找树（BST） 笛卡尔树 MVP树 Top tree T树
自平衡二叉查找树AA树 AVL树 左倾红黑树 红黑树 替罪羊树 伸展树 树堆 加权平衡树
B树B+树 B*树 Bx树 UB树 2-3树 2-3-4树 (a,b)-树 Dancing tree H树
堆二叉堆 二项堆 斐波那契堆 左偏树 配对堆 斜堆 Van Emde Boas tree
Trie后缀树 基数树 三叉查找树 X-快速前缀树 Y-快速前缀树 AC自动机
二叉空间分割（BSP）四叉树 八叉树 k-d树 隐式k-d树 VP树
非二叉树指数树 融合树 区间树 PQ树Range tree SPQR树
空间数据分割树线段树 R树 R*树 R+树 X树 M树 可持久化线段树 希尔伯特R树 优先R树
其他树树状数组 散列日历 散列树 Finger tree 顺序统计树 Metric tree Cover tree BK树 Doubly chained tree iDistance Link-cut tree Log-structured merge-tree 树状数组 哈希树

平衡树

平衡树

二叉数

二叉树

二叉搜索树 BST

二叉搜索树

平衡二叉树

基础类

  1. 二叉搜索树
  2. 哈夫曼树(最优二叉树)
  3. 二叉堆
  4. 线索二叉树

平衡树类

  1. AVL树
  2. 红黑树
  3. 2-3树
  4. 2-3-4树
  5. B树
  6. B+树
  7. B-树
  8. treap
  9. SBT

优先队列类

  1. 左高树(左偏树，可并堆，斜堆)
  2. 双端堆
  3. 斐波那契堆

集合类

  1. 并查集

区间树类

  1. 线段树
  2. 树状数组
  3. 划分树
  4. 归并树

字母树类

  1. 前缀树(字典树)
  2. 后缀树
  3. AC自动机算法

动态树类

  1. 伸展树

图论类

  1. 最小生成树
  2. 无根树

计算几何类

  1. KD-tree（块状树）
  2. 4叉树

RMQ转LCA

  1. 笛卡尔树

其它

  1. 失败树
  2. 博弈树

二叉树、平衡二叉树、B- tree、B+ tree 基本概念

https://blog.csdn.net/u014209205/article/details/81043002

1.红黑树和自平衡二叉(查找)树区别 2.红黑树与B树的区别

1.红黑树和自平衡二叉(查找)树区别

1、红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。 2、平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。

AVL树是最早出现的自平衡二叉(查找)树 红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。 红黑树和AVL树的区别在于它使用颜色来标识结点的高度，它所追求的是局部平衡而不是AVL树中的非常严格的平衡。

红黑树是牺牲了严格的高度平衡的优越条件为代价红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。 此外，由于它的设计，任何不平衡都会在三次旋转之内解决。 当然，还有一些更好的，但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。 红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高.

2.红黑树与B树的区别

(B-树，即为B树。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为B-树是一种树，而B树又是一种一种树。而事实上是，B-tree就是指的B树。特此说明。)

B树又叫平衡多路查找树。B树是为了磁盘或其它存储设备而设计的一种多叉（下面你会看到，相对于二叉，B树每个内结点有多个分支，即多叉）平衡查找树。与红黑树很相似，但在降低磁盘I/0操作方面要更好一些。 许多数据库系统都一般使用B树或者B树的各种变形结构，如下文即将要介绍的B+树，B*树来存储信息。

红黑树与B树的区别在于，B树的结点可以有许多子女，从几个到几千个。那为什么又说B树与红黑树很相似呢?因为与红黑树一样，一棵含n个结点的 B树的高度也为O（lgn） ，但可能比一棵红黑树的高度小许多，应为它的分支因子比较大。所以， B树可以在O（logn）时间内，实现各种如插入（insert），删除（delete）等动态集合操作

数据结构--树、二叉树、满二叉树、完全二叉树的性质

https://blog.csdn.net/weixin_44675377/article/details/89362909

AVL树，红黑树，B树，B+树，Trie树都分别应用在哪些现实场景中？

https://www.zhihu.com/question/30527705

并查集 union&find 是一种树形的数据结构，用于处理一些不交集（disjoint sets）的合并及查询问题

find：确定元素属于哪一个子集，它可以被用来确定两个元素是否属于同一子集。

union：讲两个子集合并成同一个集合。

二叉树

斜树 满二叉树 全美二叉树 完全二叉树

遍历  先序遍历 中序遍历 后序遍历 层次遍历

插入 删除

动态查找树

二叉查找树 BST

平衡二叉树 AVL

红黑树 
    JDK ConcurrentHashMap实现
    JDK TreeMap实现
    C++ STL ：map & set 
    linux进程调度 Completely Fair Scheduler 用红黑树管理进程控制块
    epol在内核中的实现，用红黑树管理事件块
    nginx中，用红里树管理 timer等

哈夫曼树  哈夫曼编码

多路查找树 8-树 文件磁盘系统 B+树 MySQL索引系统 B*树 R树

堆

二叉堆
左倾堆
斜堆
二项堆
斐波那契堆
最近更新：:
Contributors: luokaiwen