倾斜的树

展开树是一种自平衡或自调整的二叉搜索树。换句话说，我们可以说，叉形树是二叉搜索树的变体。我们应该知道二叉搜索树的先决条件。

我们已经知道，在每种情况下二叉搜索树的时间复杂度。一般情况下，二叉搜索树的时间复杂度为O (logn)最坏情况下的时间复杂度为O(n)。在二叉搜索树中，左子树的值小于根节点，右子树的值大于根节点;在这种情况下，时间复杂度为O (logn)．如果二叉树是左偏或右偏，则时间复杂度为O(n)。为了限制偏度AVL和红黑树进入画面，有O (logn在所有情况下所有操作的时间复杂度。我们还可以通过更实际的实现来改进这种时间复杂度，所以新的树数据结构被设计成一棵被称为“张开树”的树。

什么是展树?

张开树是一棵自平衡树，但是AVL和红黑树也是自平衡树。是什么让这两棵树与众不同呢?它还有一个独特的属性，那就是显示。

展开树包含与展开树相同的操作二叉搜索树，即插入、删除和搜索，但它还包含一个操作，即显示。所以。在展开树中的所有操作之后都要进行展开。

张开的树不是严格的平衡树，但它们是大致平衡的树。让我们来理解一下在散列树中的搜索操作。

假设我们要在树中搜索7个元素，如下所示:

要在展开树中搜索任何元素，首先，我们将执行标准的二叉搜索树操作。因为7比10小所以我们要到根结点的左边。在执行搜索操作之后，我们需要执行显示操作。这里的显示意味着我们在任何元素上执行的操作在执行一些重排之后应该成为根节点。树的重新排列将通过旋转来完成。

注意:伸展树可以定义为自调整的树，其中对元素执行的任何操作都会重新排列树，使已执行操作的元素成为树的根节点。

旋转

有六种类型的旋转用于显示:

1. z形旋转(右旋转)
2. z形旋转(向左旋转)
3. 之字形(一个字形接着一个字形)
4. 弯弯曲曲(弯弯曲曲接弯弯曲曲)
5. Zig Zig(向右旋转两次)
6. Zag Zag(左转两次)

选择旋转类型所需的因素

以下是选择旋转类型的因素:

• 我们要旋转的节点有祖父节点吗?
• 节点是父节点的左子节点还是右子节点?
• 该节点是祖父节点的左子节点还是右子节点?

旋转的情况

案例1:如果节点没有祖父级父节点，并且它是父节点的右子节点，那么我们执行左旋转;否则，执行右旋转。

案例2:如果节点有祖父节点，则基于以下场景;旋转将执行:

场景1:如果节点位于父节点的右侧，并且父节点也位于其父节点的右侧，则右转右转执行。

场景2:如果节点在父节点的左侧，但父节点在其父节点的右侧，则左右之字形旋转执行。

场景3:如果节点在父节点的右边，并且父节点在其父节点的右边，则左转左转执行。

场景4:如果节点在父节点的右边，但父节点在其父节点的左边，则左右之字形旋转执行。

现在，让我们用例子来理解上面的旋转。

为了重新排列树，我们需要执行一些旋转。下面是展开树中的旋转类型:

• 急转旋转

当要搜索的项是根节点或根节点的子节点(即左子节点或右子节点)时，使用zig旋转。

在搜索时，在展开树中可能存在以下情况:

案例1:如果搜索项是树的根节点。

案例2:如果搜索项是根节点的子节点，则会出现两种情况:

1. 如果子节点是左子节点，则执行右旋转，称为右旋转之字形。
2. 如果子节点是右子节点，则执行左旋转，称为左之字形旋转。

让我们通过一个示例来查看上述两个场景。

考虑下面的例子:

在上面的例子中，我们必须在树中搜索7个元素。我们将采取以下步骤:

步骤1:首先，我们将7与根节点进行比较。因为7小于10，所以它是根节点的左子节点。

步骤2:一旦找到元素，我们将执行显示。向右旋转，使7成为树的根节点，如下所示:

让我们考虑另一个例子。

在上面的例子中，我们必须在树中搜索20个元素。我们将采取以下步骤:

步骤1:首先，我们将20与根节点进行比较。因为20大于根节点，所以它是根节点的右子节点。

步骤2:一旦找到元素，我们将执行显示。执行左旋转，使20元素成为树的根节点。

• 之字形旋转

有时，当要搜索的项既具有父项又具有祖父项时，就会出现这种情况。在这种情况下，我们必须执行四次旋转来显示。

让我们通过一个例子来理解这种情况。

假设我们必须在树中搜索1个元素，如下所示:

步骤1:首先，我们必须执行一个标准的BST搜索操作来搜索1元素。因为1小于10和7，所以它在节点7的左边。因此，元素1有一个父元素，即7，也有一个祖父元素，即10。

步骤2:在这一步中，我们必须执行显示。我们需要在旋转的帮助下将节点1作为根节点。在这种情况下，我们不能简单地执行一个之字形或之字形旋转;我们必须实现之字形旋转。

为了使节点1成为根节点，我们需要执行两次被称为zig旋转的右旋转。当我们执行右旋转时，10将向下移动，节点7将向上移动，如下图所示:

同样，我们将执行右旋转，节点7将向下移动，节点1将向上移动，如下所示:

如上图所示，节点1已成为树的根节点;因此，搜索完成。

假设我们想在下面的树中搜索20。

为了搜索20，我们需要进行两次向左旋转。搜索20个节点的步骤如下:

步骤1:首先，执行标准的BST搜索操作。因为20大于10和15，所以它在节点15的右边。

步骤2:第二步是表演展翅。在这种情况下，将执行两次左旋转。第一次旋转时，节点10向下移动，节点15向上移动，如下图所示:

第二次左旋转时，节点15向下移动，节点20成为树的根节点，如下图所示:

正如我们所观察到的，进行了两次左旋转;所以它被称为左旋之字形。

• 之字形旋转

到目前为止，我们读到父母和祖父母都是RR或LL关系。现在，我们将看到父节点和祖父节点之间的RL或LR关系。

让我们通过一个例子来理解这种情况。

假设我们要在树中搜索13个元素，如下所示:

步骤1:首先，执行标准的BST搜索操作。因为13大于10但小于15，所以节点13将是节点15的左子节点。

步骤2:由于节点13在节点15的左边，节点15在节点10的右边，所以存在RL关系。首先，我们对节点15进行右旋转，15向下移动，节点13向上移动，如下图所示:

但是，节点13不是根节点，并且13位于根节点的右侧，因此我们将执行向左旋转，即锯齿旋转。节点10向下移动，节点13成为根节点，如下图所示:

我们可以在上面的树中观察到节点13已经成为根节点;因此，搜索完成。在本例中，我们先执行了之字形旋转，然后是之字形旋转;所以，它被称为之字形旋转。

• 之字形旋转

让我们通过一个例子来理解这种情况。

假设我们要在树中搜索9个元素，如下所示:

步骤1:首先，执行标准的BST搜索操作。因为9小于10但大于7，所以它将是节点7的右子节点。

步骤2:因为节点9在节点7的右边，节点7在节点10的左边，所以存在LR关系。首先，我们在节点7上执行左旋转。节点7向下移动，节点9向上移动，如下图所示:

节点9仍然不是根节点，并且9位于根节点的左侧，因此我们将执行称为zig旋转的右旋转。向右旋转后，节点9成为根节点，如下图所示:

从上面的树中可以看出，节点13是根节点;因此，搜索完成。在本例中，我们先执行了之字形旋转(向左旋转)，然后再执行之字形旋转(向右旋转)，因此称为之字形旋转。

张开树的优点

• 在展开树中，我们不需要存储额外的信息。相比之下，在AVL树中，我们需要存储每个节点的平衡因子，这需要额外的空间，红黑树还需要存储一个额外的比特信息，表示节点的颜色，红色或黑色。
• 在各种实际应用中，它是最快的二叉搜索树。它用于Windows NT和GCC编译器．
• 它提供了更好的性能，因为频繁访问的节点将移动到更靠近根节点的地方，因此可以快速访问扩展树中的元素。它在缓存实现中使用，因为最近访问的数据存储在缓存中，因此我们不需要访问内存来访问数据，并且花费的时间更少。

张开树的缺点

张开树的主要缺点是树不是严格平衡的，即它们是大致平衡的。有时候，斜叉树是线性的，所以它需要O(n)的时间复杂度。

在展开树中插入操作

在插入操作时，首先将元素插入到树中，然后对插入的元素执行展开操作。

15 10 17 7

步骤1:首先，我们在树中插入节点15。插入之后，我们需要执行显示。因为15是根节点，所以我们不需要执行显示。

步骤2:下一个元素是10。因为10小于15，所以节点10将是节点15的左子节点，如下所示:

现在，我们来执行向外伸展的．为了使10成为根节点，我们将执行右旋转，如下所示:

步骤3:下一个元素是17。因为17大于10和15所以它将成为节点15的右子结点。

现在，我们将表演展示。因为17有父结点也有祖父结点所以我们将执行之字形旋转。

在上图中，我们可以看到17成为了树的根节点;因此，插入完成。

步骤4:下一个元素是7。因为7小于17 15和10，所以节点7将是10的左子节点。

现在，我们要展开树。因为7有父节点和祖父节点，所以我们将执行两个右旋转，如下所示:

节点7仍然不是根节点，它是根节点的左子节点，即17。因此，我们需要再执行一次右旋转，使节点7成为根节点，如下所示:

插入操作算法

在上面的算法中，T是树，n是我们要插入的节点。我们已经创建了一个包含根节点地址的临时变量。我们将运行while循环，直到temp的值变为NULL。

一旦插入完成，将执行展开

显示操作算法

在上面的实现中，x是执行旋转的节点，而y是节点x的左子节点。

执行左。旋转(T, x)

在上面的实现中，x是执行旋转的节点，y是节点x的右子节点。

在展开树中删除

正如我们所知，叉形树是二叉搜索树的变体，所以在叉形树中的删除操作将类似于BST，但唯一的区别是，在叉形树中删除操作之后是展开操作。

删除类型:

在展开树中有两种类型的删除:

1. 自底向上倾斜
2. 自顶向下倾斜

自底向上倾斜

在自下而上展开中，首先从树中删除元素，然后在删除的节点上执行展开。

让我们来理解一下在Splay树中的删除。

假设我们想从下面的树中删除12,14:

• 首先，我们简单地执行标准的BST删除操作来删除12个元素。因为12是一个叶节点，所以我们简单地从树中删除这个节点。

删除仍未完成。我们需要显示被删除节点的父节点，即10。我们必须表演斜面(10)在树上。正如我们在上面的树中看到的，10在节点7的右边，节点7在节点13的左边。因此，首先对节点7进行左旋转，然后对节点13进行右旋转，如下图所示:

不过，节点10不是根节点;节点10是根节点的左子节点。因此，我们需要对根节点14进行右旋转，使节点10成为根节点，如下所示:

• 现在，我们必须从树中删除第14个元素，如下所示:

我们知道，我们不能简单地删除内部节点。将节点的值替换为为了前任手册或有条不紊地进行后续．假设我们使用顺序后继，其中我们将值替换为右子树中存在的最小值。节点14右子树的最小值为15，因此我们将值14替换为15。由于节点14成为叶节点，所以我们可以简单地删除它，如下所示:

但是，删除还没有完成。我们还需要执行一个操作，即显示，其中我们需要将删除节点的父节点作为根节点。在删除之前，节点14的父节点是根节点，即10，因此在本例中我们不需要执行任何显示。

自顶向下倾斜

在自顶向下展开中，我们首先执行要执行删除的展开，然后从树中删除节点。一旦元素被删除，我们将执行连接操作。

让我们通过一个例子来理解自上而下的展开。

假设我们想从树中删除16，如下所示:

步骤1:在自顶向下展开中，我们首先在节点16上执行展开。节点16既有父节点，也有祖父节点。节点16在它的父节点的右边，父节点也在它的父节点的右边，所以这是一个曲折的情况。在本例中，首先，我们将在节点13上执行左旋转，然后在节点14上执行左旋转，如下所示:

节点16仍然不是根节点，它是根节点的右子节点，因此我们需要对节点12执行左旋转以使节点16成为根节点。

一旦节点16成为根节点，我们将删除节点16，我们将得到两棵不同的树，即左子树和右子树，如下图所示:

我们知道左子树的值总是小于右子树的值。左子树的根是12右子树的根是17。第一步是找到左子树的最大元素。在左子树中，最大的元素是15，然后我们需要对15进行展开操作。

正如我们在上面的树中看到的那样，元素15既有父元素，也有祖父元素。一个节点在它的父节点的右边，父节点也在它的父节点的右边，所以我们需要执行两次左旋转来使节点15成为根节点，如下所示:

在树上执行两次旋转后，节点15成为根节点。如我们所见，15的右子节点为NULL，因此我们将节点17附加到15的右部分，如下所示，此操作称为a加入操作。

注意:如果要删除的元素不在展开树中，则执行展开。在到达NULL之前，将对最后访问的元素执行显示。

删除操作算法

在上述算法中，我们首先检查根是否为Null;如果根为NULL，则表示树为空。如果树不是空的，我们将对要删除的元素执行显示操作。一旦展开操作完成，我们将根数据与要删除的元素进行比较;如果两者不相等，则表示该元素不存在于树中。如果它们相等，则可能发生以下情况:

案例1:根的左侧为NULL，根的右侧为根节点。

案例2:如果左子树和右子树都存在，则显示左子树中的最大元素。当展开完成后，最大元素成为左子树的根。右子树将成为左子树根的右子树。