算法 - 树的定义和性质

树是代表各个元素或节点之间的层次关系的离散结构。 父级不超过两个子级的树称为二叉树。

树及其属性

定义-树是一个连通的无环无向图。G中的每对顶点之间都有一条唯一的路径。顶点数为N的树包含(N-1)个边。0度的顶点称为树的根。1度顶点称为树的叶节点,内部节点的度至少为2。

示例-以下是树的示例-

树

一棵树的中心和双中心

一棵树的中心是一个偏心率最小的顶点。树G中顶点X的偏心度是顶点X与树的任何其他顶点之间的最大距离。最大偏心距是树的直径。如果一棵树只有一个中心,则称为“中心树”;如果一棵树只有一个以上的中心,则称为“双中心树”。每棵树都可以是中心树或中心树。

标记树

定义-标记树是指为其顶点分配1到n唯一编号的树。我们可以手工为n的较小值计数这些树,从而推测出一个通用公式。具有n个顶点的标记树的数量为n n-2。如果两个标记树的图是同构的,并且两个树的对应点具有相同的标记,则它们是同构的。

示例

带有两个顶点的标记树具有三个顶点的三个可能的标记树

未贴标签的树木

定义-无标签树是指其顶点未分配任何数字的树。n个顶点的标记树的数量为$\ frac {(2n)!} {(n + 1)!n!} $(n加泰罗尼亚语数字)

示例

无标签的树带有三个顶点的未标记树具有四个顶点的两个可能的未标记树

根树

根树G是具有特殊节点的连接的无环图,该特殊节点称为树的根,每个边直接或间接地起源于该根。有序的有根树是每个内部顶点的子级都有序的有根树。如果根树的每个内部顶点都具有不超过m个子节点,则称为m元树。如果根树的每个内部顶点都恰好有m个子树,则称其为完整的m元树。如果m = 2,则将根树称为二叉树。

根树

二进制搜索树

二进制搜索树是满足以下属性的二进制树-

  • 顶点V的左子树中的X,值(X)≤值(V)

  • 顶点V的右子树中的Y,值(Y)≥值(V)

因此,内部节点V的左子树的所有顶点的值均小于或等于V,内部节点V的右子树的所有顶点的值均大于或等于V.从根节点到最深节点的链接数是二进制搜索树的高度。

示例

二进制搜索树

在BST中搜索密钥的算法

BST_Search(x, k)
if ( x = NIL or k = Value[x] )
   return x;
if ( k < Value[x])
   return BST_Search (left[x], k);
else
   return BST_Search (right[x], k)

二叉搜索树的复杂度


平均情况最坏的情况下
Space Complexity上)O(n)
搜索复杂度O(log n)O(n)
插入复杂度O(log n)O(n)
删除复杂度O(log n)上)