树基本概念

文章字数：891,阅读全文大约需要3分钟

树是由一个根节点延伸到若干节点，再由这些若干节点向外延伸的数据结构。

概念

树

1. 节点: 构成树的基本单位。
2. 树: 是节点的有限集，当节点为空时成为空树。树只有一个根节点，多棵树之间无交互。
3. 度: 节点拥有的子树（即子节点，子节点组成的数为子树）数量。
4. 节点关系: 节点的下级节点成为该节点的孩子节点，节点是下级节点的双亲节点，节点下级节点之间互为兄弟节点。
5. 节点层次: 根节点为第一层，根节点的子节点为第二次，再往下为第三层…以此类推。
6. 深度: 数节点的最大层次，成为改树的深度/高度。

二叉树

1. 二叉树: 在树的定义之上增加子节点只有两个的限制，两个节点称为左节点和右节点。左右节点次序不可以颠倒，只有一个节点也要区分左右节点。
2. 斜树: 所有节点都只有左节点的二叉树称为左斜树，所有节点都只有右节点的二叉树称为右斜树。
3. 满二叉树: 二叉树上所有的分支节点都有左右节点，并且叶子节点处于同一层。即当前深度的二叉树中节点最多的结构。所有的层都是满的。
4. 完全二叉树: 和满二叉树类型，只是最后一层不满，并且所有的空缺都在右边（先填满左节点再右节点）
5. 二叉查找树: 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。[搜索,插入,删除的复杂度等于树高，O(log(n))]
6. 红黑树: 一种自平衡的二叉查找树，解决了二叉查找树可能出现树不平衡的情况（全部在左边或者全部在右边等情况）

性质1. 节点是红色或黑色。
性质2. 根节点是黑色。(叶子节点null也是黑色的)
性质3 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树性质4保证了最长路径和最短路径差距不会超过两倍

---