平衡二叉树ll型调整

平衡二叉树是一种高效的数据结构，它的修改和查询操作都能保持在log(n)时间下完成。而其中的平衡调整操作是保持平衡二叉树性质的关键所在。其中一个常见的调整操作是LL型调整，即左左旋转。本文将从多个角度分析平衡二叉树LL型调整。

一、LL型调整介绍

当插入一个节点后，如果发现平衡因子的绝对值超过了1，那么就需要进行平衡调整操作来重新构建平衡二叉树。而LL型调整就是其中一种操作，它是指针对某个节点的左子树不平衡，而且该左子树的左子树比右子树高的情况。具体操作可以分为以下三步：

1. 将不平衡节点的左孩子作为新的根节点；

2. 把新根节点的右孩子变成原根节点的左孩子；

3. 把原根节点变成新根节点的右孩子。

这样就实现了左左旋转，也就是LL型调整。如下图所示。


二、LL型调整原理

为了更好地理解LL型调整的原理，我们需要首先了解平衡二叉树的定义和性质。平衡二叉树是一棵空树或者具有以下性质的二叉树：

1. 左子树和右子树的高度差不超过1；

2. 左子树和右子树本身也是一棵平衡二叉树。

而平衡二叉树的性质决定了它的查找效率为log(n)，但是在插入或删除某个节点后，可能会导致平衡二叉树失去平衡，因此需要进行平衡调整。

当一个节点的左子树高度比右子树高度多2时，就需要进行LL型调整。因为此时左子树中的最高节点必须成为根节点，并且该最高节点的右子树成为原根节点的左子树，并且原根节点成为新根节点的右子树。这样就能保证平衡二叉树的性质。如下图所示。


三、LL型调整的代码实现

以下是LL型调整的代码实现：

```

struct TreeNode {

int val;

int height;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), height(1), left(NULL), right(NULL) {}

};

TreeNode* leftRotate(TreeNode* root) {

TreeNode* newRoot = root->left;

root->left = newRoot->right;

newRoot->right = root;

root->height = max(getHeight(root->left), getHeight(root->right)) + 1;

newRoot->height = max(getHeight(newRoot->left), getHeight(newRoot->right)) + 1;

return newRoot;

}

```

其中节点结构体包含了节点值、节点高度、左孩子和右孩子指针。leftRotate函数就是LL型调整的代码实现，它接受一个不平衡的节点指针作为参数，然后返回一个新的根节点指针。具体实现即按照LL型调整的三个步骤进行操作。同时，更新节点的高度信息可以保证平衡二叉树的性质。

四、LL型调整性能分析

LL型调整是一种比较简单的平衡调整操作，因此其时间复杂度为O(1)。即LL型调整的性能表现是非常优秀的。另外，由于平衡二叉树中节点的平衡状态可以很快地感知并进行调整，因此它的增删改查操作的时间复杂度都是O(log(n))，且稳定性也非常好。