Binary Search Tree and algorithms: Can someone explain the concept of these? use

Question

Binary Search Tree and algorithms: Can someone explain the concept of these? use different values, I'm looking for understanding.

We have numbers between 1 and 1000 that we want to search. We introduce them in a binary search tree. To test this tree, we choose to look for 501. Given this sequence: 724. 120. 210. 521. 309. 488. 513. 489.498. 501 Can this be the possible patch of the tree to find the searched number? Why? For this given Binary Search Tree T. Complete the following Successor(T, c) = Successor(T. h) = Animate the tree with the following numbers: 11.12.13.14.15.16.17.18.19.20 while keeping T a BST. What is the result of 5 successive DELETE (MINIMUM (7)) operations on the tree? Show all steps. For any given binary search tree, come up with an algorithm that can return true if the tree is balanced, and false otherwise. What is its complexity? Design an algorithm that uses a stack to reverse a queue. What is its complexity? Design an algorithm that takes as input two doubly linked lists and tests if one is the reverse of the other (if the values in List of size 3 are 1. 2. 3 and the values of List 2 of size 3 are 3. 2. 1 then the algorithm must return true). What is its complexity? Design an algorithm that takes as input two unordered linked lists and returns an ordered linked list containing all elements from the input Lists (if the values in List1 are 1.3 and the values of List2 are 3.2.5 then the algorithm must return a List3 with values 1. 2. 3, 3. 5). What is its complexity? Same as 6.1.. with input being two ordered linked lists.

Explanation / Answer

int jsw_insert(struct jsw_tree *tree, int data) { if (tree->root == NULL) { tree->root = make_node(data); } else { struct jsw_node *it = tree->root; int dir; for (;;) { dir = it->data data == data) { return 0; } else if (it->link[dir] == NULL) { break; } it = it->link[dir]; } it->link[dir] = make_node(data); } return 1; } int jsw_remove(struct jsw_tree *tree, int data) { if (tree->root != NULL) { struct jsw_node *p = NULL, *succ; struct jsw_node *it = tree->root; int dir; for (;;) { if (it == NULL) { return 0; } else if (it->data == data) { break; } dir = it->data link[dir]; } if (it->link[0] != NULL && it->link[1] != NULL) { p = it; succ = it->link[1]; while (succ->link[0] != NULL) { p = succ; succ = succ->link[0]; } it->data = succ->data; p->link[p->link[1] == succ] = succ->link[1]; free(succ); } else { dir = it->link[0] == NULL; if (p == NULL) { tree->root = it->link[dir]; } else { p->link[p->link[1] == it] = it->link[dir]; } free(it); } } return 1; }

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.