在一个空的二叉排序树中依次插入关键字序列为12,7,17,11,16,2,13,9,21,4，请画出所得到的二叉排序树。

依次插入关键字序列12,7,17,11,16,2,13,9,21,4，得到的二叉排序树如下图所示：

            12
           /  \
          7    17
         / \   / \
        2  11 13  21
          /     \
         9      16
        /
       4

解释：首先将12作为根节点插入，然后7比12小，所以插入7的左子树中，17比12大，所以插入17的右子树中，11比7大但比12小，所以插入11的左子树中，16比12大但比17小，所以插入16的右子树中，2比7小，所以插入2的左子树中，13比12大但比17小，所以插入13的右子树中，9比7大但比11小，所以插入9的左子树中，21比17大，所以插入21的右子树中，4比2大，所以插入4的右子树中。最终得到的二叉排序树满足左子树中的所有关键字均小于根节点，右子树中的所有关键字均大于根节点。

相关问题

在一棵空的二叉排序树中依次插入关键字序列为49,38,65,97,76,13,27,44,82,35,50,请画出所得到的二叉排序树。求在等概率的情况下进行二叉排序树查找成功的平均查找长度

二叉排序树如下图所示：

       49
     /    \
   38      65
  /   \      \
13    44      97
     /  \     /
    27  35  76
            \
            82
             \
             50

在等概率的情况下进行二叉排序树查找成功的平均查找长度为：

平均查找长度 = (1/n) * (1 + 2 + ... + n)
其中，n为二叉排序树中的节点数

此处n=12，代入公式得：

平均查找长度 = (1/12) * (1 + 2 + ... + 12) = 2.92

因此，在等概率的情况下进行二叉排序树查找成功的平均查找长度为2.92。

在一棵空的二叉排序树中插入关键字序列为12，7，17，11，16，2，13，9，21，4请画出所得到的avl树

### 回答1：
很抱歉，由于我是一个纯文本AI，无法提供图片或图形的绘制。但是我可以简单地描述一下这棵AVL树的构建过程。

首先，我们按照给出的关键字序列依次插入二叉排序树中。插入顺序为12，7，17，11，16，2，13，9，21，4。

插入12后，这棵树只有一个根节点12。

接着插入7，树变成了：

    12
   /
  7

再插入17，树变成了：

    12
   /  \
  7    17

继续插入11，树发生不平衡，需要旋转调整：

    12
   /  \
  11   17
 /    /
7    13

继续插入16，树变成了：

    12
   /  \
  11   17
 /    /  \
7    13  16

接着插入2，树又发生不平衡，需要双旋转调整：

    12
   /  \
  11   17
 /    /  \
2    13  16
 \
  7

继续插入13，树变成了：

    12
   /  \
  11   17
 /    /  \
2    13  16
     /
    7

接着插入9，树又发生不平衡，需要旋转调整：

    12
   /  \
  11   17
 /    /  \
2    13  16
     / \
    7   9

最后插入21和4，树变成了：

      12
     /  \
    11   17
   /    /  \
  2    13  21
   \      /
    7    16
     \
      9

这就是按照给出的关键字序列所得到的AVL树。

### 回答2：
首先，根据插入的关键字序列{12, 7, 17, 11, 16, 2, 13, 9, 21, 4} ，我们可以按照二叉排序树的插入规则，逐个将关键字插入到空的二叉树中。

第一步，插入关键字12，作为根结点，得到如下树：
12

第二步，插入关键字7，小于根结点12，插入到根结点的左子树上，得到如下树：
12
/
7

第三步，插入关键字17，大于根结点12，插入到根结点的右子树上，得到如下树：
12
/ \
7 17

第四步，插入关键字11，小于根结点12，大于结点7，插入到结点7的右子树上，得到如下树：
12
/ \
7 17
\
11

第五步，插入关键字16, 大于根结点12，小于结点17，插入到结点17的左子树上，得到如下树：
12
/ \
7 17
\ /
11 16

第六步，插入关键字2，小于根结点12，小于结点7，插入到结点7的左子树上，得到如下树：
12
/ \
7 17
/ /
2 16
\
11

第七步，插入关键字13, 大于根结点12，大于结点7，小于结点17，插入到结点17的左子树上，得到如下树：
12
/ \
7 17
/ / \
2 16 21
\
11
\
13

第八步，插入关键字9，小于根结点12，大于结点7，小于结点2，插入到结点2的右子树上，得到如下树：
12
/ \
7 17
/ / \
2 16 21
\ /
11 13
/
9

第九步，插入关键字21, 大于根结点12，大于结点17，插入到结点17的右子树上，得到如下树：
12
/ \
7 17
/ / \
2 16 21
\ /
11 13
/
9

第十步，插入关键字4，小于根结点12，小于结点7，小于结点2，插入到结点2的左子树上，得到如下树：
12
/ \
7 17
/ / \
2 16 21
/ \ /
1 4 13
/
9

所得到的AVL树如上所示。

### 回答3：
AVL树是一种自平衡的二叉搜索树，它的特点是每个节点的左子树和右子树的高度差最多为1。下面是根据关键字序列12，7，17，11，16，2，13，9，21，4构建的AVL树：

首先，我们将12插入空的二叉排序树中，得到如下树结构：
12

然后，将7插入到12的左子树中，得到如下树结构：
12
/
7

接着，将17插入到12的右子树中，得到如下树结构：
12
/ \
7 17

继续，将11插入到7的右子树中，得到如下树结构：
12
/ \
7 17
/
11

然后，将16插入到17的左子树中，得到如下树结构：
12
/ \
7 17
/ \
11 16

接下来，将2插入到7的左子树中，得到如下树结构：
12
/ \
7 17
/ \
2 11
\
16

继续，将13插入到17的右子树中，得到如下树结构：
12
/ \
7 17
/ \ \
2 11 13
\
16

然后，将9插入到7的右子树中，得到如下树结构：
12
/ \
7 17
/ \ \
2 11 13
\ \
9 16

最后，将21插入到17的右子树中，得到如下树结构：
12
/ \
7 17
/ \ \
2 11 13
\ \ \
9 16 21

得到的这棵树就是根据关键字序列构建的AVL树。在这棵树中，每个节点的左右子树高度差都为1，满足AVL树的平衡性质。