C++(数据结构与算法):69---平衡搜索树之分裂树/伸展树

一、分裂树简介

• 当使用AVL树或红黑树来实现字典时，最坏情况下，每一个字典操作的时间复杂性是字典大小的对数。在已知的数据结构中，没有一个会提供更好的性能。然而，在字典的很多实际应用中，令我们更感兴趣的不是一个操作而是一个操作序列所需要的时间。例如，在前面搜索树的应用文章中，每一个应用的时间复杂性都取决于一个字典操作序列，而不是任意一个操作

分裂树概述

• 分裂树是二叉搜索树，而且是一个单独的字典操作，其时间复杂性是O(n)
• 而对f个查找、i个插入、d个删除所组成的操作序列，其时间复杂性是O((f+i+d))。与使用AVL树或红黑树的渐近时间复杂性相同
• 研究表明，对任意的字典操作序列，分裂树比AVL树或红黑树的实际运行速度要快
• 不仅如此，分裂树的编码还更容易实现

二、分裂节点

• 分裂树的操作与二叉搜索树的完全相同。但是，分裂树的操作（get、put、remove等）都是从分裂节点开始的
• 在分裂操作的最后，分裂节点是二叉搜索树的根（重点，见下面的分裂步骤）
• 分裂节点是在操作中所检查的最深层的节点（即终止比较关键字的节点、生成的节点、删除的节点、或者是该节点的左孩子或右孩子）

查找时的分裂节点

• 如果查找80：检查最深的节点是80这个节点，所以80节点就是本次查找的分裂节点
• 如果查找31：检查最深的节点是31这个节点，所以31节点就是本次查找的分裂节点
• 如果查找55：搜索路径是从30到60，检查最深的节点是60这个节点，所以60节点就是本次查找的分裂节点

插入时的分裂节点

• 插入时可能会生成一个新的节点或者覆盖一个已经存在的节点
  • 生成新的节点时：新节点就是本次的分裂节点
  • 覆盖一个已存在的节点时：覆盖的节点就是本次的分裂节点

• 当插入5时：5已存在，因此插入操作会覆盖这个节点，因此5就是本次插入操作的分裂节点
• 当插入65时：65在树中不存在，插入之后，65会成为60的右孩子，因此65就是本次的分裂节点

删除时的分裂节点

• 当二叉搜索树中存在要删除的关键字k时，最深检查的节点是要删除的节点，但是这个节点不会成为分裂节点，因为删除之后就不存在了。因此删除之后有这样几种情况：
  • ①如果删除节点由=有父节点：删除节点的父节点为本次的分裂节点（因为除去删除节点，其父节点就是本次删除中搜索最深的节点）
  • ②如果删除节点没有父节点，但是有左孩子或左右孩子：删除节点的左孩子为本次的分裂节点
  • ②如果删除节点没有父节点，但是无左孩子有右孩子：删除节点的右孩子为本次的分裂节点

• 当删除33时：33存在，因此此次的分裂节点就是其父节点32
• 当删除35时：35存在，因此此次的分裂节点就是其父节点40
• 当删除30时：30存在，因此此次的分裂节点就是其左孩子5

三、分裂步骤

• 概念：当对分裂树进行查找、删除、添加之后，我们就需要根据分裂节点进行分裂操作，通过分裂操作最终让分裂节点称为新根节点。（如何选取分裂节点已经在上面介绍了）
• 分裂过程：
  • ①当分裂节点上面只有一个父节点时，分裂的时候将分裂节点上移1层（此时变为新根节点）
  • ②当分裂节点还有父节点以及祖父节点时，每次分裂的时候要将分裂节点上移2层
  • ③当还有父节点/祖父节点时，分裂节点参照步骤①或步骤②不断的向上移动，直到成为新根节点
• 备注：分裂树的分裂操作与AVL树的单/双旋转十分的类似，甚至是相同的

上移1层的操作

• 如果分裂节点还有父节点时，但是无祖父节点，就需要向上移动1层
• 在移动1层的分裂步骤中，有两种类型：
  • 一种是L型（表示分裂节点q是其父节点的左孩子）
  • 一种是R型（表示分裂节点q是其父节点的右孩子）
• 下面显示了L型分裂的步骤，分裂之后分裂节点称为根节点（R型的步骤类似）

上移2层的操作

• 当分裂节点还有父节点以及祖父节点时，就需要向上移动2层。此时我们假设分裂节点为q，父节点为p，祖父节点为gp
• 上移2层分为四种类型：
  • LL：分裂节点为祖父节点的左孩子的左孩子
  • LR：分裂节点为祖父节点的左孩子的右孩子
  • RR：分裂节点为祖父节点的右孩子的左孩子
  • RL：分裂节点为祖父节点的右孩子的右孩子
• 下面以LL型分裂步骤为例，分裂节点要向上移动2层

• 下面以LR型分裂步骤为例，分裂节点要向上移动2层

• RR和RL的步骤与上面类似

• 为什么不每次一层一层的移动呢？上面我们介绍了在不同的情形下，每次分裂可能会移动2层或1层（根据分裂节点所处的层数来判断），但是分裂步骤也可以一层一层的移动（即L型和R型），但是为什么不这样呢？因为这样做了之后不能保证任一个由f个查找、i个插入、d个删除所组成的操作序列可以用O((f+i+d))时间来完成

四、一个分裂的演示案例

• 例如下图a是一棵初始搜索树，现在我们搜索节点2，那么节点2将为分裂节点，并且查找之后分裂节点要成为新根节点
• 下图a-d为此次搜索操作的整体过程，共经历了：LL分裂-->LR分裂-->L分裂

五、折算复杂性

• 一个操作的实际时间复杂性和最坏情况的时间复杂性与操作的步骤的执行步数密切相关
• 但是一个操作的折算复杂性常常与实际复杂性没有直接关系，它是一种计算技法。它唯一的要求是，对一个操作序列，所有操作的折算复杂性之和大于或等于实际复杂性之和。即：
  • amortized(i)金额actual(i)分别表示在含有n个操作的序列中，第i个操作的折算和实际复杂性

• 因此我们可以把折算复杂性当做任意操作序列的时间复杂型的上限
• 你可以把一个操作的折算复杂性看作是你要求的运行时间，而不是实际的运行时间。只要这个运行时间至少等于操作序列实际运行时间

分裂树的折算复杂性定理

• 在一棵具有n个元素的分裂树中，查找、插入或删除操作的折算复杂性是O()

• 有定理和上面的公式可知，由f个查找、i个插入、d个删除所组成的操作序列可以用O((f+i+d))时间来完成