为什么二元树很重要？

Question

为什么我们要专门研究二叉树？正如在一般的m-way搜索树中,不像DataStructure教科书中的二叉树那样重要.

使用二叉树是否超过m-way树？

Answer 1

二叉树是多路树的最简单形式,因此在这个意义上它们更容易学习.

多路树具有由N键和N+1指针组成的节点,沿着以下行:

               |
   +-----+-----+-----+-----+
   | k00 | k01 | k02 | k03 |
   +-----+-----+-----+-----+
  /      |     |     |      \
p00     p01   p02   p03     p04

要找出要在搜索中跟随的指针,请将要查找的键与节点中的键进行比较.上面的例子是order-2多路树(我将命令定义n为具有2n键和2n+1指针).

当你"退化"这个结构以使最小的节点成为可能时,你最终得到一个键和两个指针,你的经典二叉树:

      |
   +-----+
   | k00 |
   +-----+
  /       \
p00       p01

当我上大学时(我会很快承认它是不久前),我们首先研究二叉树,因为算法很优雅.搜索是一个简单的比较节点,并选择两个子树之一.插入和删除也相对容易.

然后我们继续进行平衡二叉树,其中搜索完全相同,但插入和删除稍微复杂一些,涉及通过子树根"旋转"子树,必要时保持平衡.

接下来是非平衡多路树,一旦找到正确的节点,就可以获得在节点内搜索的概念,最后,平衡的多路树基本上与二叉树相同但具有相同的多路树.增加了顺序搜索的复杂性,以及节点内的插入或删除以及节点本身的组合和吐出.

在每个步骤中,您只需为算法添加一点复杂性.我不记得有太多人遇到这种进展的麻烦,所以你提到的所有教科书都只是处于初级水平.

我从来没有真正发现多路树比二叉树更有用,除非在一个非常特殊的情况下.那是当你从像磁盘这样的慢速介质中读取树的节点时,你已经针对扇区/簇/块大小进行了优化.

我们通过确保节点的大小与底层磁盘块相同,在OS/2下显示了一个多路树实现(显示我的年龄).即使这可能会导致一些浪费的空间,速度的提升也是值得的.

对于内存中的东西,二叉树具有多路的所有优点,没有任何额外的复杂性(必须将节点的顺序搜索与子树选择相结合).

二进制树归结为"我们应该向左还是向右移动？",多方式是"这个节点中的关键在哪里,以便我们可以选择子树？".

Answer 2

二叉树是一个简单的概念,它们易于理解,易于实现,并且工作良好且快速 - 我认为这足以用于教学和/或使用它们.