1) AVL rotation: Given a below BST subtree, we can use double rotation to reduce the height by 1. Double rotation can be performed with 2 times of single rotation. Please draw the subtree after the first single rotation and second single rotation, such that it performs a double rotation to becomes a subtree with h = h-1. a = z c = y b = x To Subtree after first single rotation: Subtree after second single rotation:

1) AVL rotation: Given a below BST subtree, we can use double rotation to reduce the height by 1. Double rotation can be performed with 2 times of single rotation. Please draw the subtree after the first single rotation and second single rotation, such that it performs a double rotation to becomes a subtree with h = h-1. a = z c = y b = x To Subtree after first single rotation: Subtree after second single rotation:

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

In the Branch and Bound approach we normally avoid evaluating subtrees that do not contain the solution, we are looking for. Select one: True False θ(n) is the formal way to express both the lower bound and the upper bound of an algorithm's running time Select one: True False
TREE-DELETE(root, x): should not happen! # x.key not in S # nothing to remove if root is NIL: pass else if x.key root.item.key: root.right <- TREE-DELETE (root.right, x) # x.key if root.left is NIL: root <- root.right else if root.right is NIL: else: root.item.key so Remove root.item. == # NIL if both children missing root <- root.left else: # Root has two children: remove element with smallest key in right subtree and # move it to root. Assumption: DELETE-MIN returns two values: element removed # from right subtree and root of resulting subtree (in case root.right changes). root.item, root.right <- DELETE-MIN(root.right) return root DELETE-MIN (root): # Remove element with smallest key in root's subtree; # return element removed and root of resulting subtree. if root.left is NIL: # Root stores item with smallest key; replace with right child. return root.item, root.right else: # Left subtree not empty: root not the smallest. item, root.left <- DELETE-MIN(root.left) return item, root
a) A list of student's names is maintained in an AVL tree T. Design an algorithm for performing the operation findAll to return all the names in the AVL tree that match the searched name. Note that there is a possibility that same names exist in the tree. In the case that the same name exists, the name is added to the left subtree. b) Delete element 60 in the following Binary Search Tree (BST). Provide a brief description/explanation how the delete operation is performed. Your explanation can be in point form. Show the final Binary Search Tree (after the deletion of element 60). 10 20 ส 25 32 30 40 49 45 50 180 55 51 60 230 70 74 80 75 76
The definition for binary search tree should be the one used in class Class definition: A BST is a binary tree that (if not empty) also follows two storage rules regarding its nodes’ items: ♯ For any node n of the tree, every item in n’s left subtree (LST), if not empty, is less than the item in n ♯ ♯ For any node n of the tree, every item in n’s right subtree (RST), if not empty, is greater than the item in n ● bst_insert must be iterative (NOT recursive). ● bst_remove and bst_remove_max must use the algorithm described by the suggested book authors In btNode.h: provide prototypes for bst_insert, bst_remove and bst_remove_max. ● In btNode.cpp: provide definition (implementation) for bst_insert, bst_remove and bst_remove_ma #ifndef BT_NODE_H#define BT_NODE_H struct btNode{ int data; btNode* left; btNode* right;};// pre: bst_root is root pointer of a…
Given the array below representing disjoint sets, draw the associated trees 3 4 7 -1 -1 -1 3
Exercise 3: Multi-way Trees A way to reduce the height of tree and ensure balance is to allow multiple children of nodes. In your class you learned 2-3 trees which allows up to 2 keys in a node, and the number of children is equal to the number of keys + 1. B-trees extend this concept to any arbitrary number of keys (usually number of keys is even and number of children (equal to number of keys+1) is odd). Assume we want to design a 5-way B-Tree. This will mean that there can be maximum 4 keys in a node, and if the number of keys becomes 5, we can split it into two (the same way we split 2-3 tree when number of keys becomes 3). Design a 5-way B-tree. Starting with an empty tree, insert the following keys in order. 2, 3, 5, 7, 10, 50, 22, 44, 45, 55, 66, 68, 70, 17, 6, 21, 67
Change the following traversal into a postorder traversal. template void preorder (BinNode* root) { if (root == NULL) return; // Empty subtree, do not visit (root); preorder (root->left ()); preorder (root->right ()); // Perform desired actio
Add to the BinarySearchTree class a member function string smallest() const that returns the smallest element of the tree. Provide a test program to test your function. #include <iostream>#include <string>using namespace std;class TreeNode{public:void insert_node(TreeNode* new_node);void print_nodes() const;bool find(string value) const;private:string data;TreeNode* left;TreeNode* right;friend class BinarySearchTree;};class BinarySearchTree{public:BinarySearchTree();void insert(string data);void erase(string data);int count(string data) const;void print() const;private:TreeNode* root;};BinarySearchTree::BinarySearchTree(){root = NULL;}void BinarySearchTree::print() const{if (root != NULL)root->print_nodes();}void BinarySearchTree::insert(string data){TreeNode* new_node = new TreeNode;new_node->data = data;new_node->left = NULL;new_node->right = NULL;if (root == NULL) root = new_node;else root->insert_node(new_node);}void TreeNode::insert_node(TreeNode*…
A) To create a binary tree T1 with node containing age of a person and check whether the tree constructed is a binary search tree or not based on age. Also display the nodes containing age of second youngest and age of second eldest person without using global variables, array and sorting. B) Include a function which checks whether a given tree, T2, is the sub-tree of T1. Return a pointer to the matching subtree TX. Pointers to the root of first tree (T1) and second tree(T2) are passed as parameters to the function (A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T. The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree.). Example Input/Output: A) Figure 1: T1 The given tree T1 is not a binary search tree Age of second youngest person is 3 Age of second eldest person is 8 В) 26 10 10 10 4 4 6. 30 30 T1 T2 T3 T2 is a subtree of T1, and T3 is not a subtree of T1. T3 is…
What is the Postorder Traversal of the following tree E H I) F, J, I, H, G, E, D II) G, H, I, J, E, D, F III) D, F, E, H, I, J, G IV) D, E, G, H, I, J, F V) G, J, I, H, E, F, D (F)
Question 15 Use the Binary Search Tree (BST) deletion algorithm to delete 0074 from the BST below. List the nodes of the resulting tree in pre-order traversal order separated by one blank character. For example, the tree below can be described in the above format as: 65 33 25 47 52 50 88 74 80 77 91 0065 0033 0088 0025 0047 0074 0091 0052 0080 0050 0077
2. This question is about binary search tree.a. Show the final result after inserting 3, 1, 4, 6, 9, 2, 8, 5, 7, 0 into an empty binary search tree.b. Show the result of deleting the root twice. If the deleted node contains 2 children, its value is replaced by the minimum value of the right subtree, and the deletion is propagated. Show the result after each deletion