树
-
概念
它是由n（n>0）个有限节点组成一个具有层次关系的集合。 -
特点
-
每个节点有零个或多个子节点；
-
没有父节点的节点称为根节点；
-
每一个非根节点有且只有一个父节点；
-
除了根节点外，每个子节点可以分为多个不相交的子树；
-
有序树和无序树
-
无序树
树中任意节点的子节点之间没有顺序关系，也称自由树； -
有序树
树中任意节点的子节点之间有顺序关系 -
相关术语
节点的度：一个节点含有的子树的个数称为该节点的度；
树的度：一棵树中，最大的节点的度称为树的度；
叶节点或终端节点：度为零的节点；
非终端节点或分支节点：度不为零的节点；
父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
兄弟节点：具有相同父节点的节点互称为兄弟节点；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次；
堂兄弟节点：父节点在同一层的节点互为堂兄弟；
节点的祖先：从根到该节点所经分支上的所有节点；
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
森林：由m（m>=0）棵互不相交的树的集合称为森林；
二叉树
二叉树是一种特殊的有序树：每个节点至多有两个分支（子节点），分支具有左右次序，不能颠倒。
两种特殊的二叉树：
完全二叉树：除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点（注意是右边，而不能是左边缺少）。
满二叉树：每一层都是满的（除了最后一层，这里的最后一层是指叶节点）。
二叉搜索（查找）树
二叉查找树（英语：Binary Search Tree，简写为BST），也称二叉搜索树、有序二叉树（英语：ordered binary tree），排序二叉树（英语：sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
a.若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
b.若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
c.任意节点的左、右子树也分别为二叉查找树；
d.没有键值相等的节点。
简单的说就是：各节点值不同，并且对于任意一个子树：左<根<右。
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低，期望O(log n)，最坏为O(n)。
查找效率与树的高度成反比，关键在于减小二叉查找树的高度为O(log n)。
平衡树
平衡树是一种改进的二叉查找树，一般的二叉查找树的查询复杂度是跟目标结点到树根的距离（即深度）有关，因此当结点的深度普遍较大时，查询的均摊复杂度会上升，为了更高效的查询，平衡树应运而生了。
在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。朴素的理解：普通二叉查找树，在新增/删除等操作后，会变得又高又瘦，会让查找/新增/删除操作的时间复杂度变大，而平衡二叉树在新增/删除等操作后依然会保持矮矮胖胖的形态，使树的高度维持在log n附近。这种形态就是平衡，会使查找速度更快。为什么能够保持这种好身材呢？通过在新增/删除时的旋转（左旋和右旋）。
常见的平衡树：
AVL树、Treap、伸展树、红黑树、加权平衡树、2-3树、AA树、替罪羊树、节点大小平衡树
红黑树
红黑树（英语：Red–black tree）是一种自平衡二叉查找树。
它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。
- 红黑树的性质
- 节点是红色或黑色。
- 根是黑色。
- 所有叶子都是黑色（叶子是NIL节点）。
- 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
红黑树.png
B树
B树（英语：B-tree）是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树（binary search tree），可以拥有多于2个子节点。与自平衡二叉查找树不同，B树为系统大块数据的读写操作做了优化。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。
概括关键词：自平衡，可以拥有多于2个子节点，适用于数据库和文件系统。
待续。。。
网友评论
待续。。。
没了？