数据结构之平衡二叉树的平衡调整

• 算法结构

目录

1：LL型调整

2：RR型调整

3：LR型调整

4：RL型调整

5：总结

作者约定：将导致不平衡的结点称作被破坏者，破坏了结点的平衡的结点成为破坏者，经过调整可以让该树平衡的结点称为调整结点。

1，LL型调整

LL型不平衡调整方法：以调整结点为中心，进行右旋操作，就可以使树平衡。

情况1：

在这里插入图片描述

在这里插入图片描述

情况2：

在这里插入图片描述

在这里插入图片描述

情况3：

在这里插入图片描述

在这里插入图片描述

2，RR型调整

RR型不平衡调整方法：以调整结点为中心，进行左旋操作，就可以使树平衡。

情况1：

在这里插入图片描述

在这里插入图片描述

情况2：

在这里插入图片描述

在这里插入图片描述

情况3：

在这里插入图片描述

在这里插入图片描述

3，LR型调整

LR型不平衡调整方法：以调整结点为中心，进行左旋操作，在进行右旋操作，就可以使树平衡

情况1：

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

情况2：

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

情况3：

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

4，RL型调整

RL型不平衡调整方法：以调整结点为中心，进行右旋操作，在进行左旋操作，就可以使树平衡

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

情况2：

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

情况3：

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

5，总结

LL型：

以被破坏者的左孩子结点作为调整结点，对其进行右旋。如果调整结点有右子树，将其右子树作为被破坏者的左子树。

LR型：

以被破坏者的左孩子的右孩子结点为调整结点。

如果破坏者为调整结点的左孩子，以调整结点进行左旋，将破坏者作为调整结点的父节点的右子树，后进行右旋，破坏者位置保持不变。

如果破坏者为调整结点的右孩子，以调整结点进行左旋，破坏者位置保持不变。后进行右旋，将破坏者作为被破坏者的左子树。

RR型：

以被破坏者的右孩子结点为调整结点，对其进行左旋。如果调整结点有左子树，将其右子树作为被破坏者的右子树。

RL型：

以被破坏者的右孩子的左孩子结点为调整结点。

如果破坏者为调整结点的左孩子，以调整结点进行右旋，破坏者位置保持不变，后进行左旋，将破坏者作为被破坏者的右子树。

如果破坏者为调整结点的右孩子，以调整结点进行右旋，将破坏者作为调整结点的父节点的左子树。后进行左旋，破坏者位置保持不变。

如何在程序中判断是LL型，RR型，LR型还是RL型

可以根据树的高度差来判断。如果被破坏者左子树高度 – 被破坏者右子树高度 > 1，说明是LL型或LR型，否则就是RR型或RL型。

如果被破坏者的左孩子的左子树高度 – 被破坏者的左孩子的右子树高度 = 1，则为LL型，否则为LR型。

如果被破坏者的右孩子的左子树高度 – 被破坏者的右孩子的右子树高度 = -1，则为RR型，否则为RL型。

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://www.net2asp.com/4d8450c6d0.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐