数据布局入门：树（Tree）具体先容

什么是树

树是一种条理布局的数据布局，它由节点（也称为极点）构成，这些节点经过边互相毗连。在一个树布局中，任何两个节点之间只能有一条途径。树常常用于表现目标之间的条理干系，如文件体系、构造布局图等。

树的每个节点可以有零个或多个子节点，除了根节点外，每个节点都有一个父节点。根节点是树的起始点，没有父节点。树的一个基本特性是，从任何一个节点动身，沿着边，可以到达它的任何子节点。

树的属性

• 边的数目：树中的边是毗连两个节点的线。假如树有N个节点，那么它将有N-1条边。这本实质是由于在一个树中，除了根节点外，每个节点都有一个父节点，而根节点是唯一没有父节点的节点。因此，总节点数减去1即是边的数目。
• 节点的深度：节点的深度是从根节点到该节点的途径长度。每条边都市增远程径的长度1个单位。因此，节点的深度也可以界说为从树的根节点到该节点的途径中的边数。
• 节点的高度：一个节点的高度可以界说为从该节点到叶子节点的最远程径的长度。在树布局中，叶子节点是没有子节点的节点。
• 树的高度：树的高度是从树的根节点到叶子节点的最远程径的长度。
• 节点的度：附着在该节点上的子树的总数称为节点度。树的最大节点度是树中一切节点中的最大节点度。

树的分类

二叉树

二叉树每个节点最多有两个子节点，通常称为左子节点和右子节点。左子节点位于节点的右方，右子节点位于节点的右方。二叉树是一种十分常用的数据布局，常常用于种种算法和数据利用中，如二叉搜刮树、堆、前缀编码等。
二叉树特性如下：

• 二叉树允许每个节点最多有两个子节点。这是二叉树的基本界说。
• 根节点和叶子节点之间的最大边数决定了二叉树的高度。在二叉树中，叶子节点是没有子节点的节点，而根节点是树的出发点。从根节点到叶子节点的最远程径决定了树的高度。
• 二叉树在深度 d 处最多可以有

  个节点。这是由于每个节点要么是一个叶节点（没有子节点），要么有两个子节点，以是在给定的深度，总的节点数目有一个极限。

• 高度为 h 的二叉树最多可以有

  个节点。这是由于关于高度为 h 的二叉树，从根节点到叶子节点的最远程径长度为 h，而除了这条最远程径外的其他途径长度都最少为1，因此总的节点数目有一个极限。

• 在二叉树中，叶子节点数只能比内里节点数多一个。这是由于除了根节点外，每个非叶节点有两个子节点：一个左子节点和一个右子节点。因此，除了根节点外，总节点数减去1即是内里节点数（即非叶子节点数）。以是，叶子节点的数目总是比内里节点的数目多一个。

基于子节点个数的二叉树典范有：

• 满二叉树（Full Binary Tree）
• 退步二叉树（Degenerate Binary Tree）

而基于层完成度的二叉树典范有：

• 完全二叉树（Complete Binary Tree）
• 完善二叉树（Perfect Binary Tree）
• 均衡二叉树（Balanced Binary Tree）
  这些不同典范的二叉树具有不同的实质和使用场景。比如，满二叉树和完全二叉树具有精良的空间使用实质，退步二叉树在某些情况下可以表现为链表等。
  后续章节会对这些二叉树做具体先容。

三元树（Ternary Tree）

三元树（Ternary Tree）每个节点最多有三个子节点，通常称为“左”、“中”和“右”。这些子节点可以进一步被表明为其他信息或持续指向其他节点。
三元树（Ternary Tree）干系于其他树形布局有一些上风，比如，查询听从高，布局相对简便。但是，它们也具有一些缺陷，比如，假如树变得十分大，约莫会变得难以办理。
在三元树（Ternary Tree）中，每个节点都存储一个键（key）和三个子节点的引用。键用于将节点存储在准确的地点，而子节点的引用用于毗连到其他节点。
三元树（Ternary Tree）常常被用于种种不同的使用中，包含搜刮引擎索引、数据库索引、内存办理等。

Ternary Search Tree（三元搜刮树）是一种特别的数据布局，它团结了Trie（也称为前缀树）和 Binary Search Tree（二叉搜刮树）的特性。在 Trie 中，每个节点通常有 26 个子节点，分散对应 26 个英笔墨母。而在 Ternary Search Tree中，每个节点仅有三个子节点：一个左子节点，一此中子节点，以及一个右子节点。这三个子节点的分列排序依照二叉搜刮树的端正，即左子节点的值小于如今节点的值，中子节点的值即是如今节点的值，右子节点的值大于如今节点的值。这种数据布局的主要优点是它可以更高效地存储和搜刮字符串数据集。由于每个节点有三个指针，而不是26个，以是它可以节流多量空间。别的，由于它团结了二叉搜刮树的特性，以是它可以更快地搜刮和插进新的键值对。

N叉树（N-ary Tree）

N叉树（N-ary Tree）是一种树形数据布局，它允许每个节点有多达n个子节点，与标准的二叉树不同，后者只允许每个节点最多有2个子节点。下图是一个N-ary Tree的示例：

泛树（Generic Tree）是由节点构成的聚集，每个节点是一个数据布局，包含纪录和指向其子节点的引用列表（不允许反复引用）。与链表不同，每个节点存储多个节点的地点。每个节点存储其子节点的地点，第一个节点的地点将存储在名为根的单独指针中。泛树是N-ary Tree的一种，具有以下特性：

• 每个节点有多个子节点。
• 每个节点的节点数事前不晓得。

依据节点值的不同，树可以分为很多特别典范。以下是一些稀有的典范：

二叉搜刮树（Binary Search Tree）：在二叉搜刮树中，关于每个节点，其左子树中的一切节点的值都小于该节点的值，而其右子树中的一切节点的值都大于该节点的值。这种布局使得查找、插进和删除利用的时间繁复度可以到达O(log n)。但是，假如树不是均衡的，最坏情况下的时间繁复度约莫会到达O(n)。

AVL树：AVL树是一种自均衡二叉搜刮树。在AVL树中，任何节点的两个子树的高度差都不会凌驾1。

红黑树（Red-Black Tree）：它是一种自均衡二叉搜刮树，此中每个节点都有一个颜色属性，通常为赤色或玄色。且满意以下实质：

• 节点是赤色或玄色。
• 根是玄色。
• 一切叶子都是玄色（叶子是NIL节点）。
• 每个赤色节点必需有两个玄色的子节点。
• 从任一节点到其每个叶子的一切简便途径都包含相反数目标玄色节点（简称黑高）。
• 红黑树的插进和删除利用干系于二叉查找树要繁复，必要举行调停，以满意红黑树的实质。红黑树的使用十分广泛，好比 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map 均是基于红黑树布局完成的。

B树（B-Tree）：它是一种自均衡的搜刮树，用于存储关联数组和排序数据。它是一种多叉树，每个节点可以具有多个子节点。这种数据布局可以让查找数据、排序拜候、插进数据及删除的举措，都在对数时间内完成。

B+树（B+ Tree）：通常用于数据库和利用体系的文件体系中。它是一种n叉排序树，每个节点通常有多个孩子，一棵B+树包含根节点、内里节点和叶子节点。根节点约莫是一个叶子节点，也约莫是一个包含两个或两个以上孩子节点的节点。 B+树的特点是可以坚持数据安定有序，其插进与修正拥有较安定的对数时间繁复度。B+树元素自底向上插进。在B+树中，一切的叶子节点中包含了全部紧张字的信息，及指向含这些紧张字纪录的指针，且叶子节点本身依紧张字的轻重自小而大排序链接。一切的非终端节点可以当作是索引局部，节点中仅含其子树（根节点）中的最大（或最小）紧张字。

Segment Tree是一种用于处理区间成绩的二叉树数据布局，它可以看作是一棵均衡二叉树。每个节点都对应一个区间[l,r]，叶子节点对应的是一个单位区间，即l==r。关于一个非叶子节点[l,r]，它的左儿子所表现的区间为[l,(l+r)/2]，右儿子表现的区间为[(l+r)/2+1,r]。

假如有劳绩，点个眷注支持一下，谢谢！

#文章首发挑唆赛#