目录1.下列哪些二叉树是 AVL 树?2.a.对于n12345的情况画出所有包含n个节点并满足AVL树平衡要求的二叉树。b.画出一棵高度为4的可以称为AVL树的二叉树它必须具有最少的节点数。3.对于左单转和右左双转分别画出表示它们一般形式的图。4.对于下面的每个列表从一棵空树开始通过连续插入它们的元素来构造一棵AVL 树。a. 123456b. 654321c. 3651245.a.对于一棵包含实数的AVL 树设计一个算法来计算它的值域(也就是说最大数和最小数的差)请确定该算法的最差效率。b.判断正误 AVL树中最小的键和最大的键总是位于最后一层或者倒数第二层。6.写一个程序为n个不同整数构成的一个给定列表构造一棵 AVL 树。7.a.为列表COMPUTING 构造一棵2-3树(根据这些字母的字母顺序从一棵空树开始把它们连续插入)。b.假设查找每个键(也就是字母)的概率都是相同的求出在这棵树中进行成功查找时的最大键值比较次数和平均键值比较次数。8.假设T₈和T₂₃分别是一棵经典的二叉查找树和一棵2-3树它们都是按照相同次序插入相同的键的列表所构造成的。请判断下列命题是否成立如果查找相同的键T₂₃的键值比较次数总是小于或等于T₈的键值比较次数。9.为包含实数的2-3树设计一个算法来计算它的值域(也就是说最大数和最小数的差)并确定该算法的最差效率。10.写一个程序为包含n个整数的列表构造一棵2-3树。1.下列哪些二叉树是 AVL 树?ac是AVL树2.a.对于n12345的情况画出所有包含n个节点并满足AVL树平衡要求的二叉树。构造如下b.画出一棵高度为4的可以称为AVL树的二叉树它必须具有最少的节点数。以左子树为高度增加点每加一个节点就对树做补充最终得出要求的树3.对于左单转和右左双转分别画出表示它们一般形式的图。单左旋右左旋先对w为根节点的子树做右旋然后对v为根节点的树做左旋4.对于下面的每个列表从一棵空树开始通过连续插入它们的元素来构造一棵AVL 树。a. 123456构造过程如下b. 654321c. 3651245.a.对于一棵包含实数的AVL 树设计一个算法来计算它的值域(也就是说最大数和最小数的差)请确定该算法的最差效率。找最小值从根节点一直往左走走到最左叶子节点就是最小值。找最大值从根节点一直往右走走到最右叶子节点就是最大值。计算值域最大值 - 最小值。算法 GET_RANGE(root): // 找最小值 min_node root while min_node.left ≠ null do min_node min_node.left // 找最大值 max_node root while max_node.right ≠ null do max_node max_node.right return max_node.key - min_node.keyAVL 树高度h Θ(log n)总效率Θ(log n)b.判断正误 AVL树中最小的键和最大的键总是位于最后一层或者倒数第二层。并非正确AVL 树是平衡二叉搜索树最小值在最左节点最大值在最右节点。它们可以出现在任意层不一定在最后两层只要满足平衡即可。举反例一个高度为 4 的 AVL 树最左节点可能在第 2层根本不是最后两层。6.写一个程序为n个不同整数构成的一个给定列表构造一棵 AVL 树。#include stdio.h #include stdlib.h // AVL 树节点结构 typedef struct Node { int key; struct Node *left; struct Node *right; int height; // 节点高度 } Node; // 获取节点高度 int height(Node *node) { if (node NULL) return 0; return node-height; } // 求最大值 int max(int a, int b) { return (a b) ? a : b; } // 创建新节点 Node* createNode(int key) { Node* node (Node*)malloc(sizeof(Node)); node-key key; node-left NULL; node-right NULL; node-height 1; // 新节点初始高度为1 return node; } // 右旋操作 Node* rightRotate(Node* y) { Node* x y-left; Node* T2 x-right; x-right y; y-left T2; y-height max(height(y-left), height(y-right)) 1; x-height max(height(x-left), height(x-right)) 1; return x; } // 左旋操作 Node* leftRotate(Node* x) { Node* y x-right; Node* T2 y-left; y-left x; x-right T2; x-height max(height(x-left), height(x-right)) 1; y-height max(height(y-left), height(y-right)) 1; return y; } // 获取节点平衡因子 int getBalance(Node* node) { if (node NULL) return 0; return height(node-left) - height(node-right); } // 插入节点并保持AVL平衡 Node* insert(Node* node, int key) { // 1. 标准BST插入 if (node NULL) return createNode(key); if (key node-key) node-left insert(node-left, key); else if (key node-key) node-right insert(node-right, key); else // 不允许重复键 return node; // 2. 更新高度 node-height 1 max(height(node-left), height(node-right)); // 3. 计算平衡因子 int balance getBalance(node); // 4种不平衡情况 // 左左 if (balance 1 key node-left-key) return rightRotate(node); // 右右 if (balance -1 key node-right-key) return leftRotate(node); // 左右 if (balance 1 key node-left-key) { node-left leftRotate(node-left); return rightRotate(node); } // 右左 if (balance -1 key node-right-key) { node-right rightRotate(node-right); return leftRotate(node); } return node; } // 中序遍历输出有序序列 void inOrder(Node* root) { if (root ! NULL) { inOrder(root-left); printf(%d , root-key); inOrder(root-right); } } int main() { Node* root NULL; int n, i, num; printf(请输入整数个数 n); scanf(%d, n); printf(请输入 %d 个不同整数\n, n); for (i 0; i n; i) { scanf(%d, num); root insert(root, num); } printf(\nAVL 树中序遍历有序\n); inOrder(root); return 0; }7.a.为列表COMPUTING 构造一棵2-3树(根据这些字母的字母顺序从一棵空树开始把它们连续插入)。2-3 树规则每个节点可以存1 个或 2 个关键字插入时如果节点变成3 个关键字就分裂中间元素上升左右分成两个子节点始终保持所有叶子在同一层插入过程如下插入 C →[C]插入 O →[C, O]插入 M → 节点满分裂根[M]左[C]右[O]插入 P → 放入右节点 →[O, P]插入 U → 右节点满分裂根[M, P]左[C]中[O]右[U]插入 T → 放入右节点 →[T, U]插入 I → 放入左节点 →[C, I]插入 N → 放入中节点 →[N, O]插入 G → 左节点[C, I]满分裂根上升[G, M, P]→ 根满再次分裂最终根[M]左[G]子C, I右[P]子N,O; T,U[ M ] / \ [G] [P] / \ / \ [C] [I] [N,O] [T,U]b.假设查找每个键(也就是字母)的概率都是相同的求出在这棵树中进行成功查找时的最大键值比较次数和平均键值比较次数。p1/9,第一层查找一次第二层查找两次第三层找三次第三层的大于一个元素的节点是需要顺序查找的因此总查找次数是14128251 次M2 次G, P3 次C, I, N, T4次OU平均 25 / 98.假设T₈和T₂₃分别是一棵经典的二叉查找树和一棵2-3树它们都是按照相同次序插入相同的键的列表所构造成的。请判断下列命题是否成立如果查找相同的键T₂₃的键值比较次数总是小于或等于T₈的键值比较次数。命题错误。因为 2-3 树的一个节点可能包含 2 个键查找其中第二个键时需要 2 次比较而二叉查找树每个节点只有 1 个键只需 1 次比较。因此存在 T23​ 比较次数更多的情况。举个最简单的例子查找节点[N, O]中的O2-3 树比较 1 次不是→ 再比较 1 次是总共 2 次二叉查找树O 是单独节点总共 1 次9.为包含实数的2-3树设计一个算法来计算它的值域(也就是说最大数和最小数的差)并确定该算法的最差效率。找最小值从根节点出发一直访问最左子节点直到到达叶子节点。该叶子节点的第一个键就是最小值。找最大值从根节点出发一直访问最右子节点直到到达叶子节点。该叶子节点的最后一个键就是最大值。计算值域用最大值减去最小值得到结果。算法 GET_RANGE(root) // 找最小值 current root while current 不是叶子节点 do current current 的最左子节点 min current 第一个键 // 找最大值 current root while current 不是叶子节点 do current current 的最右子节点 max current 最后一个键 return max - min最差效率是Θ(log n)10.写一个程序为包含n个整数的列表构造一棵2-3树。#include stdio.h #include stdlib.h // 2-3树节点类型 typedef enum { NODE2, NODE3 } NodeType; // 2-3树节点结构 typedef struct Node23 { NodeType type; // 关键字node2存1个node3存2个 int key1, key2; // 子节点node2有2个node3有3个 struct Node23 *left, *mid, *right; } Node23; // 创建 2-节点 (1个键 2个子节点) Node23* createNode2(int key, Node23 *left, Node23 *right) { Node23 *node (Node23*)malloc(sizeof(Node23)); node-type NODE2; node-key1 key; node-left left; node-right right; node-mid NULL; return node; } // 创建 3-节点 (2个键 3个子节点) Node23* createNode3(int key1, int key2, Node23 *left, Node23 *mid, Node23 *right) { Node23 *node (Node23*)malloc(sizeof(Node23)); node-type NODE3; node-key1 key1; node-key2 key2; node-left left; node-mid mid; node-right right; return node; } // 辅助结构体用于分裂返回信息 typedef struct { int upKey; // 上升到父节点的键 Node23 *newNode; // 分裂出的新节点 } SplitInfo; // 递归插入函数 SplitInfo insertRec(Node23 *root, int key); // 对外插入接口 Node23* insert(Node23 *root, int key) { SplitInfo info insertRec(root, key); // 根节点分裂生成新根 if (info.newNode ! NULL) { return createNode2(info.upKey, root, info.newNode); } return root; } // 核心递归插入 分裂 SplitInfo insertRec(Node23 *root, int key) { SplitInfo nullInfo {0, NULL}; // 空树 if (root NULL) { SplitInfo info; info.upKey key; info.newNode NULL; return info; } // 叶子节点 if (root-left NULL) { if (root-type NODE2) { // 2-节点叶子 → 变成3-节点 int k1 root-key1; if (key k1) root createNode3(key, k1, NULL, NULL, NULL); else root createNode3(k1, key, NULL, NULL, NULL); return nullInfo; } else { // 3-节点叶子 → 分裂 int a root-key1, b root-key2; int m; Node23 *n1, *n2; if (key a) { m a; n1 createNode2(key, NULL, NULL); n2 createNode2(b, NULL, NULL); } else if (key b) { m key; n1 createNode2(a, NULL, NULL); n2 createNode2(b, NULL, NULL); } else { m b; n1 createNode2(a, NULL, NULL); n2 createNode2(key, NULL, NULL); } SplitInfo info; info.upKey m; info.newNode n2; return info; } } // 非叶子节点向下递归 SplitInfo ret; if (root-type NODE2) { int k root-key1; if (key k) ret insertRec(root-left, key); else ret insertRec(root-right, key); } else { int k1 root-key1, k2 root-key2; if (key k1) ret insertRec(root-left, key); else if (key k2) ret insertRec(root-mid, key); else ret insertRec(root-right, key); } // 子节点没有分裂 if (ret.newNode NULL) return nullInfo; // 子节点分裂向上合并 if (root-type NODE2) { int k root-key1; Node23 *l root-left, *r root-right; if (key k) { root createNode3(ret.upKey, k, ret.newNode, l, r); } else { root createNode3(k, ret.upKey, l, r, ret.newNode); } return nullInfo; } else { // 当前是3-节点插入后分裂 int a root-key1, b root-key2; Node23 *l root-left, *m root-mid, *r root-right; int midKey; Node23 *n1, *n2; if (key a) { midKey a; n1 createNode2(ret.upKey, ret.newNode, l); n2 createNode2(b, m, r); } else if (key b) { midKey ret.upKey; n1 createNode2(a, l, ret.newNode); n2 createNode2(b, m, r); } else { midKey b; n1 createNode2(a, l, m); n2 createNode2(ret.upKey, m, ret.newNode); } SplitInfo info; info.upKey midKey; info.newNode n2; return info; } } // 中序遍历输出有序序列 void inOrder(Node23 *root) { if (root NULL) return; if (root-type NODE2) { inOrder(root-left); printf(%d , root-key1); inOrder(root-right); } else { inOrder(root-left); printf(%d , root-key1); inOrder(root-mid); printf(%d , root-key2); inOrder(root-right); } } int main() { Node23 *root NULL; int n, i, num; printf(请输入整数个数 n: ); scanf(%d, n); printf(请输入 %d 个整数:\n, n); for (i 0; i n; i) { scanf(%d, num); root insert(root, num); } printf(\n2-3树 中序遍历有序:\n); inOrder(root); return 0; }