Java源码集合类TreeMap学习1——数据结构4平衡二叉树插入一个元素的递归算法

女爷i 2022-06-16 05:14 120阅读 0赞

**平衡二叉排序树上插入一个新的元素递归算法（参考书籍《数据结构(C语言版)》）**

平衡的二叉排序树BBST（Balanced Binary Search Tree）上插入一个新的元素ｅ的递归算法有如下几种情况。

**(1)** 若平衡的二叉排序树为空树，则插入一个新的元素e的新结点作为平衡的二叉排序树的根结点，那么树的深度就为1；

这个很好理解空树插入了一个根结点e，并且这棵树的深度为1，如下图中null表示的是一个空的结点(当只有一个结点时则为表示空树)。

![Center][]

**(2)** 如果e的关键字和平衡的二叉排序树的根结点的关键字相等，则不进行插入；

也就是说要插入的结点与根结点是相同的两个结点，那么就不需要在插入了。

**(3)** 如果e的关键字小于平衡的二叉排序树根结点的关键字，并且在平衡的二叉排序树的左子树中不存在和e有相同关键字的节点，则将e插入在平衡的二叉排序树的左子树上，且当插入之后的左子树深度增加1时，分别有如下的几种清楚处理率：

通俗的说就是新结点插入到平衡的二叉排序树的左子树，而且左子树不存在与新结点相同的结点，且还要满足左子树的深度增加1。

1) 平衡的二叉排序树的根结点的平衡因子为-1，也就是右子树的深度大于左子树的深度：则将根结点的平衡因子更改为0，平衡的二叉排序树的深度不变；

![Center 1][]

2) 平衡的二叉排序树的根结点的平衡因子为0（左、右子树的深度相等）：则将根结点的平衡因子改为1，平衡的二叉排序树的深度增加1；

其实我个人觉得这个说法“则将根结点的平衡因子改为1”不是很正确，我们不确定这个插入的新结点是放在左子树还是右子树，平衡因子为1那是放在左子树，然而为-1那是放在右子树。插入之后这棵树还是二叉平衡树。

![Center 2][]

3) 平衡的二叉排序树根结点的平衡因子为1(左子树的深度大于右子树的深度)：若平衡的二叉排序树的左子树根结点平衡因子为1，则需进行单向右旋转平衡处理，并且在右旋处理之后，将根结点和其右子树的根结点的平衡因子更改为0，树的深度不变；

这句话理解清楚作者表达的意思还是有点费劲的。个人理解应该是这样的：没有插入新元素e之前，平衡的二叉排序树根结点的平衡因子为1，在插入之后左子树的根结点平衡因子为1。我们可以简单点理解：平衡的二叉排序树刚开始只有两个结点，一个根结点和一个左孩子结点，那么新元素插入之后（当然这里是插入在左孩子结点上），之前的左孩子结点的平衡因子从之前的0更改为1了。具体的如下图。

![Center 3][]

若平衡的二叉排序树的左子树的根结点的平衡因子为-1，则需要进行先向左、后向右的双向旋转平衡处理，并且旋转处理之后树的深度保持不变。如下图。

![Center 4][]

**(4) **如果e的关键字大于平衡的二叉排序树根结点的关键字，并且在平衡的二叉排序树的右子树中不存在和e有相同关键字的节点，则将e插入在平衡的二叉排序树的右子树上，且当插入之后的右子树深度增加1时，分别有如下的几种清楚处理率：

通俗的说就是新结点插入到平衡的二叉排序树的右子树，而且右子树不存在与新结点相同的结点，且还要满足右子树的深度增加1。

1) 平衡的二叉排序树的根结点的平衡因子为1，也就是左子树的深度大于右子树的深度：则将根结点的平衡因子更改为0，平衡的二叉排序树的深度不变；

2) 平衡的二叉排序树的根结点的平衡因子为0（左、右子树的深度相等）：则将根结点的平衡因子改为-1，平衡的二叉排序树的深度增加1；

3) 平衡的二叉排序树根结点的平衡因子为-1(右子树的深度大于左子树的深度)：若平衡的二叉排序树的右子树根结点平衡因子为-1，则需进行单向左旋转平衡处理，并且在左旋处理之后，将根结点和其左子树的根结点的平衡因子更改为0，树的深度不变；若平衡的二叉排序树的右子树根结点平衡因子为1，则需进行两次单向旋转平衡处理，先单向右旋转平衡处理在单向左旋转平衡处理，并且在左旋处理之后，将根结点和其左子树的根结点的平衡因子更改为0，树的深度不变；

[Center]: /images/20220616/591946c0e88a4d1ab130e7d0d1cc0e1f.png
[Center 1]: /images/20220616/1349bd135e4347c28e5de2fe60dfa12d.png
[Center 2]: /images/20220616/d64db75b427f4648a4bab9e905ca21e0.png
[Center 3]: /images/20220616/9253516dee9348d2907995b449478f4f.png
[Center 4]: /images/20220616/ab0f697de49f46cfacb637c675bf4998.png