依次输入表(30,15,28,20,24,10,68,35,50)中的元素,生成一棵平衡的二叉排序树。请画出构造过程,并在其中注明每一次平衡化的类型(LL型、RR型、LR型、RL型)
时间: 2023-08-21 07:05:43 浏览: 80
好的,我来回答你的问题,并画出构造过程:
首先,将表中的第一个元素 30 作为二叉排序树的根节点。
```
30
```
接下来,依次将其他元素插入二叉排序树中。
```
30
/ \
15 28
/ / \
10 20 24
/ \
35 68
/
50
```
可以看到,插入元素时出现了不平衡的情况,需要进行平衡操作。
插入 15 后,30 的左子树比右子树高 2,属于 LL 型不平衡,需要进行右旋平衡操作。
```
28
/ \
15 30
/ / \
10 20 24
/ \
35 68
/
50
```
插入 10 后,15 的左子树比右子树高 2,属于 LL 型不平衡,需要进行右旋平衡操作。
```
28
/ \
15 30
/ \
10 20
\
24
```
插入 68 后,30 的右子树比左子树高 2,属于 RR 型不平衡,需要进行左旋平衡操作。
```
28
/ \
15 35
/ \ \
10 20 30
/ \
24 68
/
50
```
插入 50 后,68 的左子树比右子树高 2,属于 LL 型不平衡,需要进行右旋平衡操作。
```
28
/ \
15 35
/ \ \
10 20 50
/ \
30 68
/ \
24 32
```
最终得到的平衡二叉排序树如上图所示。