在一棵空的二叉排序树中插入关键字序列为12,7,17,11,16,2,13,9,21,4请画出所得到的avl树
时间: 2023-06-17 09:03:21 浏览: 96
首先,插入关键字序列到空的二叉排序树中,得到如下图所示的二叉排序树:
```
12
/ \
7 17
/ \
2 21
\
4
\
9
\
11
\
13
\
16
```
然后,我们需要对这棵二叉排序树进行平衡调整,以得到 AVL 树。具体过程如下:
1. 从最后一个被插入的节点开始,依次向上回溯,检查每个祖先节点是否失衡。如果一个节点失衡,则需要进行旋转操作。
2. 对于失衡的节点,分为四种情况:
- LL型:左子树的左子树上插入节点导致失衡,需要进行右旋操作。
- RR型:右子树的右子树上插入节点导致失衡,需要进行左旋操作。
- LR型:左子树的右子树上插入节点导致失衡,需要进行左右旋操作。
- RL型:右子树的左子树上插入节点导致失衡,需要进行右左旋操作。
经过平衡调整后,得到如下图所示的 AVL 树:
```
11
/ \
7 16
/ \ \
2 9 17
\ \ \
4 12 21
\ /
13 19
```
其中,节点的平衡因子为 -1、0、1。