申論 3給定一棵二元搜尋樹（binary search tree），且該樹同時也是一棵AVL 樹。樹的節點在C 語言中宣告如下：typedef struct Node {int key;// 節點的鍵值，所有節點的鍵值皆互不相同int size;// 以該節點為根的子樹節點總數(包含自己)struct Node *left;// 指向左子節點struct Node *right;// 指向右子節點} Node;並定義以下函式：int size (Node *node)：若傳入的node 為NULL，則回傳0；否則回傳node -> size。int count_less_equal (Node *node, int val)：回傳以node 為根的子樹中，所有鍵值小於等於val 的節點總數。Node* select (Node *node, int r)：回傳以node 為根的子樹中，第r 小的節點指標，r 從1 開始算。Node* greater_k_smallest (Node *root, int val, int k)：找出以root 為根的整棵樹中，所有鍵值大於val 的節點裡，第k 小的節點，k 從1 開始算。若第k 小的節點不存在，則回傳NULL。㈠完成下列程式碼的空格。（20 分）int count_less_equal(Node *node, int val) {if (node == NULL) return 0;if (node->key > val)return count_less_equal(node->left, val);else return size(node->left)+(1);}Node* select(Node *node, int r) {int left_size = size(node->left);if (r ==(2)) return node;else if (r <= left_size)return select(node->left, r);else return(3);}Node* greater_k_smallest(Node *root, int val, int k){int x = count_less_equal(root, val);int y =(4);if (y > size(root)) return NULL;return select(root, y);}㈡下圖為一棵包含5 個節點且滿足AVL 平衡特性的二元搜尋樹，圖中顯示每個節點的鍵值。若將鍵值為70 的新節點插入此樹，為保持AVL樹的平衡，會觸發旋轉。請畫出旋轉後的樹狀結構圖。除新插入的節點70 外，若原有節點的size 欄位值在旋轉後發生改變，請在旋轉後的圖中，於該節點旁標示其新的size 欄位值。（5 分）