Description

Problem 1 (10.1-2)
Basic Idea: We can make it similar to the heap and stack in the computer. That is, starting at the edge and forwarding to the middle.

Problem 2 (10.1-6)

Time Complexity Analysis
push() : O(1), as the push() of stack is O(1) 1 and we call it once.
the while loop ( pop() after push() elements).
empty() & size() : O(1), as the empty() and size() of stack is O(1) and we call it twice.
Problem 3 (10.2-5)

Time Complexity Analysis
insert() : takes O(1), we just need to construct a new Node , no matter with
the number of elements.
to find the target.
Problem 4 (12.2-7)
TREE-MINIMUM() always goes to the left child until it is null . It depends on the height of the tree. As the height of BST must be (proof is similar with Problem 7), it is .
TREE-SUCCESSOR() involves two cases:
1. It has right child. We take this right child as a tree root to find TREEMINIMUM() .
2. It has no right child but parent. Check whether this node is the left child. If yes, its parent is the successor. If no, take the parent as the one to check the parent. That is, check parent recursively until we find the node is the left child or the tree root. If the latter case happened, the original node must be the last element.
Then, according to the previous rules, we can point out that we must traverse each edge of the tree twice. As one edge means one move of the pointer (go up or down), the number of edges makes the conclusive result of time complexity. The edges of BST with vertices is . Therefore, the time complexity should be
.
Problem 5 (12.3-4)
No.

Problem 6 (12.3-5)
Use AVL Tree as the BST.

}
long long getHeight(Node* n) { if (n == nullptr) { return 0;
} return n->height;
}

Node* search_helper(T t, Node* root) { if (root == nullptr) { return nullptr; // means not exist
} else if (t == root->val) { return root;
} else if (t < root->val) {
return search_helper(t, root->left);
} else {
return search_helper(t, root->right);
}
}

// lastRight means the one need to change its succ
// lastLeft means the succ of the new Node
Node* insert_helper(T t, Node* root, Node* lastRight, Node* lastLeft) {
if (root == nullptr) {
Node* res = new Node(t, lastLeft); // Node(T val, Node* succ) if (lastRight != nullptr) { lastRight->succ = res;
} return res;
} auto res = root; if (t < res->val){
res->left = insert_helper(t, res->left, lastRight, res);
} else {
res->right = insert_helper(t, res->right, res, lastLeft); }

auto balance = getHeight(res->left) – getHeight(res-
>right);
if (balance > 1) { if (t < res->left->val) { res = rightRotate(res);
} else { res->left = leftRotate(res->left); res = rightRotate(res)
}
} else if (balance < -1) { if (t > res->right->val) { res = leftRotate(res);
} else {
res->right = rightRotate(res->right); res = leftRotate(res);
} }
res->height = max(getHeight(res->left), getHeight(res-
>right)) + 1; return res;
}

// lastRight means the one need to change its succ
// lastLeft means the the replacement of the deleted Node in succ of lastRight
Node* insert_helper(T t, Node* root, Node* lastRight, Node* lastLeft) {
if (root == nullptr) { throw /* some error */
} if (root->val == t) { delete root;
if (lastRight != nullptr) { lastRight->succ = lastLeft;
}
return nullptr;
} auto res = root; if (t < res->val){
res->left = insert_helper(t, res->left, lastRight, res);

} else {
res->right = insert_helper(t, res->right, res, lastLeft); }
auto balance = getHeight(res->left) – getHeight(res-
>right);
if (balance > 1) { if (t < res->left->val) { res = rightRotate(res);
} else {
res->left = leftRotate(res->left); res = rightRotate(res)
}
} else if (balance < -1) { if (t > res->right->val) { res = leftRotate(res);
} else { res->right = rightRotate(res->right); res = leftRotate(res);
} }
res->height = max(getHeight(res->left), getHeight(res-
>right)) + 1; return res;
} public:
/* constructor and destructor */

Node* search(T t) {
return search_helper(t, this.root);
}
void insert(T t) {
this.root = insert_helper(T t, this.root, nullptr, nullptr); }
void remove(T t) {
this.root = remove_helper(T t, this.root, nullptr, nullptr);

Problem 7 (6.1-2)
As it is stored as complete binary tree, we can point the relation of height and the

As is an positive integer, we have:

As must be an non-negative integer.

Problem 8 (6.1-6)
23
/
17 14
/ /
6 13 10 1
/ /
5 7 12
Obviously, it is not, as 7 > 6.