利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树，基于该二叉排序树查找元素 30 要进行多少次元素间 的比较

建立的二叉排序树如下所示：

根据二叉排序树的查找规则，对于每一个节点，如果要查找的元素小于当前节点的值，则向左子树查找，否则向右子树查找。因此，在查找元素 30 时，需要比较的元素如下所示：

50 -> 35 -> 30

因此，需要进行 3 次元素间的比较。

相关问题

利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树，请画图对应的二叉树

以下是对应的二叉排序树的图示：

50
/ \
43 72
/ \ \
20 45 85
\
65
\
75

注：这是一个二叉排序树，根节点的值为50，左边子节点的值比根节点小，右边子节点的值比根节点大。每个节点的左边子节点和右边子节点的值也同样要满足这个条件。

利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树， 在构造该二叉排序树的过程中首次出现不平衡时，最小不平衡子树的根是 72 ，需要 进行（ ）次旋转进行调整，

首先，使用逐点插入法建立序列对应的二叉排序树，过程如下：

1. 50插入，成为根节点
2. 72插入，成为根节点的右孩子
3. 43插入，成为50的左孩子
4. 85插入，成为72的右孩子
5. 75插入，成为85的左孩子
6. 20插入，成为43的左孩子
7. 35插入，成为20的右孩子
8. 45插入，成为43的右孩子
9. 65插入，成为75的右孩子
10. 30插入，成为35的左孩子

在构造该二叉排序树的过程中，第一次出现不平衡的情况是，插入30之后，35的左子树高度为2而右子树高度为0，不满足平衡二叉树的要求。

最小不平衡子树的根是72，需要进行2次旋转进行调整，一次右旋和一次左旋。具体操作如下：

1. 对72的右子树85进行右旋，得到：

     50
    /  \
   43  85
  /    / \
20    75 72
      /   /\
     65  45 30

2. 对72进行左旋，得到：

     50
    /  \
   43  75
  /   /  \
20  65   72
      /   / \
    45   85 30

经过调整后，得到一棵平衡二叉树。