“嗨，阿米戈！”
“你好，瑞希！”
“我在那边找到了我的旧笔记，给你准备了一些有趣的资料，我想你会感兴趣的。”
“让我们听听吧。你总能找到一些有趣的东西，后来证明它们非常有用。”
“好吧。今天我想给大家讲讲树，所以我将从图表开始。”
“图是由点和连接它们的线组成的系统。点称为图的顶点，线称为图的边。例如：”
“将图用作各种现实世界过程和任务的数学模型非常方便。已经为图发明了许多不同的任务和算法，因此它们被相当频繁地使用。”
“例如，假设顶点是城市，边是道路。那么搜索城市之间的最短路线就变成了：«给定一个图，找到两个顶点之间的最短路径»。 ”
“但是从 A 到 B 的路径并不总是与从 B 到 A 的路径相同。因此，有时有两条不同的线是首选。为此，线（图形的边缘）被箭头替换。在换句话说，图形可以有两个箭头：一个从 A 到 B，另一个从 B 到 A。”
“如果图形使用箭头，则称为有向图；如果它只有线，则称为无向图。”
“每个顶点都可以有自己的边数。一个顶点也可以根本没有边。相反，一个顶点可以通过边连接到每个其他顶点。如果图中的每对顶点都由一条边连接， 那么称为完全图。 ”
“如果你可以用边到达图中的每个顶点，那么它就被称为连通图。具有三个独立顶点且没有边的图仍然是图，但我们称它为断开图。”
“要从 N 个顶点形成连通图，至少需要 N-1 条边。这种图称为树。”
“此外，通常选择一个顶点作为树的根，其余的被声明为分支。没有自己分支的树分支称为叶子。例如：”
“如果树的每个元素都有两个孩子，那么它就被称为二叉树。也就是说，可以有0个或2个分支。你可以在右上角看到一棵二叉树。”
“当每个分支有 2 个孩子并且所有叶子（没有孩子的顶点）都在同一行时，树称为完全二叉树。”
“例如：”
“为什么需要这些树？”
“哦，树的用处很多，一般来说，二叉树就是排序好的结构化数据。”
“那是什么？”
“是的，很简单。我们在每个顶点中存储一定的值。并且每个元素都遵循一个规则：右孩子中存储的值必须大于顶点中存储的值，左孩子中存储的值必须小于存储在顶点中的值。 这种排序可以快速找到所需的树元素。”
“你能解释一下这是什么意思吗？”
“树元素通常是通过加法排序的。假设我们有7个元素：13、5、4、16、8、11、10”
“这是将元素添加到树中的方式。”
“如果我们要在这棵树中寻找数字 7，那么这就是搜索的方式”
“0) 从根开始。”
“1a) 7 等于 13 吗？不”
“1b) 7 是否大于 13？不，所以我们移动到左子树。”
“2a) 7 等于 5 吗？不。”
“2b) 7 是否大于 5？是的，所以我们移动到右子树。”
“3a) 7 等于 8 吗？不”
“3b) 7 是否大于 8？不，所以我们移动到左子树。”
“4a) 没有左子树，这意味着数字 7 不在树中。”
“啊，也就是说，我们只需要检查从根到想要的数字所在位置的路径上的顶点就可以了。嗯，确实很快。”
“而且，如果这棵树是平衡的，那么你只需要通过大约20个顶点就可以搜索一百万个元素。”
“我同意——那不是很多。”
“平衡树是什么意思？”
“一棵没有扭曲的树，即没有长分支的树。例如，如果我们在构建树时已经对元素进行了排序，那么我们将创建一棵由一个分支组成的非常长的树。 ”
“嗯。你说得对。那我们怎么办？”
“正如您可能已经猜到的那样，最有效的树的分支长度大致相同。然后每次比较都会丢弃剩余子树的最大部分。”
“所以，我们需要重建这棵树？”
“是的。它需要“平衡”——尽可能接近完整的二叉树。”
“为了解决这个问题，发明了自平衡树。 如果树在添加元素后变得扭曲，那么它会稍微重新排列元素以使一切正常。 这是一个平衡的例子：”
“其中一些树被称为红黑树。”
“为什么叫红黑？”
“他们的发明者用两种颜色绘制所有顶点。一种颜色是红色，另一种颜色是黑色。不同的顶点遵循不同的规则。这构成了平衡程序的整个基础。”
“例如：”
“那么这些规则是什么？”
“1) 红色顶点不能是红色顶点的子顶点。”
“2）每片叶子的黑色深度都一样（黑色深度是指从根开始的路径上黑色顶点的个数）。”
“3）树的根是黑色的。”
“我不会解释它是如何工作的——你的脑袋可能已经爆炸了。”
“是的。我的处理器冒了一点烟。”
“这是给你的链接。如果你愿意，你可以在这里阅读更多相关信息。”
“现在，去休息一下。”
GO TO FULL VERSION