（1） 建立二叉树
①插入结点 16。 此时树空， 可直接插入， 如图 2（a） 所示：

图2 （a） 插入结点 16
②插入结点 3。 3 比 16 小， 从根结点向左走找到插入位置后插入， 没有发生不平衡现象， 如图 2（b） 所示：

图2（b） 插入结点 3
③插入结点 7。 按照二叉排序树查找方法找到插入位置后插入， 如图 7-5c 中的左图。 插入 7 后出现不平衡现象， 此时失去平衡的最小子树根结点为 16， 进行平衡调整， 将 7 作为根结点， 3 和 16 分别为其左右孩子结点，这样仍能保持根大于左小于右的特性， 这里进行的是 LR 调整。 结果如图 2（c） 中右图所示：

图2 （c） 插入结点 7 并做 LR 调整
④插入结点 11。 没有发生不平衡现象， 如图 2（d） 所示：

图2（d） 插入结点 11
⑤插入结点 9， 如图 2（e） 中左图所示。 插入 9 后出现了不平衡现象， 此时失去平衡的最小子树根结点为16。 由图中虚线框内的结点可以看出， 将 11 作为根结点， 9 和 16 分别作为其左右孩子结点同样满足根大于左小于右的特性， 这里进行的是 LL 调整。 调整结果如图 7-5e 中右图所示：

图2（e） 插入结点 9 并做 LL 调整
⑥插入结点 26， 如图 2（f） 中的左图所示。 插入 26 后出现了不平衡现象， 此时失去平衡的最小子树根结点为 7。 由图中虚线框内的结点可以看出， 将 11 作为根结点， 7 和 16 分别作为其左右孩子结点同样满足根大于左小于右的特性， 这里进行的是 RR 调整。 这样处理后结点 7 的右子树变为空， 可以将结点 9 连接在结点 7 的右子树上。 经调整结果如图 7-5f中右图所示：

图2（f） 插入结点 26 并做 RR 调整
⑦插入结点 18， 如图 2（g） 中的左图所示。 插入 18 后出现了不平衡现象， 此时失去平衡的最小子树根结点为 16。 由图中虚线框内的结点可以看出， 将 18 作为根结点， 16 和 26 分别作为其左右孩子结点同样满足根大于左小于右的特性， 这里进行的是 RL 调整。 调整结果如图 7-5g 中右图所示：

图2（g） 插入结点 18 并做 RL 调整
⑧插入结点 14， 没有发生不平衡现象， 如图 2（h） 所示：

图2（h） 插入结点 14
⑨插入结点 15， 如图 2（i） 中的左图所示。 插入 15 后出现了不平衡现象， 此时失去平衡的最小子树根结点为 16。 由图中虚线框内的结点可以看出， 将 15 作为根结点， 14 和 16 分别作为其左右孩子结点同样满足根大于左小于右的特性， 这里进行的是 LR 调整。 调整结果如图 7-5i 中右图所示， 至此， 平衡二叉树建立完成。

图2（i） 插入结点 15 并作 LR 调整
（2） 删除结点
①删除结点 16。 因结点 16 是叶子结点， 应按照删除操作的第一种情况来处理： 直接删除。 结果如图 2（j）所示：

图2（j） 删除结点 16
②删除结点 15。 结点 15 含有一棵子树， 因此应按照删除操作的第二种情况来处理： 删除 15， 并将 15 的子树根连接在 15 与其双亲结点相连的指针上。 结果如图 2（k） 所示：

图2（k） 删除结点 15
③删除结点 11。 结点 11 含有两棵子树， 因此应按照删除操作的第三种情况来处理： 沿着结点 11 的左子树根一直往右走， 最终来到结点 9， 因 9 是叶子结点， 这样就转化成了删除操作的第一种情况， 将 9 直接删除。 然后将关键字 11 用关键字 9 来代替。 结果如图 2（1） 所示：