Data Structures and algorithms test 3

If the tree below is not a red-black tree by definition, what needs to be done to make it a red-black tree?

method 1: rotate 18 left above 16, keep 10 as root, keep rest same colors

or

method 2: we just need to recolor 16 to red 15, 18 to black and 30 stays red

If the tree below is not a red-black tree by definition, what needs to be done to make is a red-black tree?

convert 16 to a red node

Consider the following AVL tree. Give the steps to add 70 and maintain balance.

*Add 70 to the left of 80

*do a left rotation on 80 (bringing down 100).

*Now 60 is the root followed by 20 and 80. Then 80 is a parent of 70 and 100. Finally 100 is a child of 120.

*Do a right rotation on 80 making it the root.

*Now 80 is the root and is a parent of 60 and 100. 60 is a parent of 20 and 70. 100 is a parent of 120.

If the tree below is not a red-black tree by definition, what needs to be done to make is a red-black tree?

*Do a right rotation on 16 making it the root and make it black.

*Now do a left rotation on 10 making it the parent of 7 and 15 and make 7 and 15 red. 10 stays black

*to the right of the tree we have 25 red, its children 18 and 30 both black, and 40 red

If the array bubble sort is applied to a sorted array, the number of exchanges is O(__________).

1

In this sort, the smaller values float up to the top of the array (toward the first element) while the larger values sink to the bottom of the array; hence the name.

bubble

In the best case scenario for the insertion sort the maximum number of comparisons is O(___).

n

In a selection sort of n elements, there are at most __________ exchanges.

n-1

Because each AVL subtree is allowed to be out of balance by ± __________, the tree may contain some holes,

1

The total effort to reconstruct a sorted array through the merge sort is O(__________).

n log n

Which below is not true about a Red-Black tree.

all the above are false about Red-Black trees

When comparing selection sort, bubble sort, and insertion sort, we can observe that __________ sort gives the best performance for most arrays, because it takes advantage of any partial sorting that is in the array and uses less costly shifts instead of exchanges to rearrange array elements.

insertion

In the worst case scenario, the number of comparisons performed by a bubble sort is O(__________).

n^2

The error written into KW::insert function below can be corrected with the code __________.

template

void insert(RI first, RI next_pos){

while (next_pos != first && next_pos<(next_pos-1)){std::iter_swap(nex_pos, next_pos-1);\++next_pos;//

--next_post;

The remedy for a __________ (parent balance is +2, right child balance is +1) AVL tree is to rotate left around parent.

Right-Right

__________ is the process of rearranging the data in an array or container so that the data elements are in increasing (or decreasing) order using a linked list.

logical sorting

The height of an AVL tree is defined as

the number of edges on the longest path from the root to a leaf

Because each AVL subtree is allowed to be out of balance by ± _______, the tree may contain some holes.

1

A shift in an insertion sort requires the movement of only one item, whereas in a bubble sort or a selection sort an exchange involves a temporary item and requires the movement or use of __________ items

3

The rotations performed by the rebalance_left member function of the AVL_Tree class will reduce the overall height of a tree by __________.

-1

In the context of a Left-Left AVL tree, the right subtree of a node has height k and the left subtree has height k + 2. The balance of the node is __________.

-2

A(n) ______________ sort compares adjacent array elements and exchanges their values if they are out of order

bubble

The number of items that a 2-3 tree of height h can hold is between 2^h - 1 (all 2-nodes) and 3^h - 1 (all 3-nodes).

true

When we remove an item from a left AVL subtree, the balance of the local root is decreased

false

The height of an AVL tree is defined as the number of nodes in the longest path from the root to a leaf node, including the root.

false

The balance factor of an AVL tree is the difference between the height of the left subtree and that of the right subtree of that node and should be maintained at -2, 0 or +2

false

A Red-Black tree maintains a root that can be either red or black.

false

If a binary search tree were full and contained n items, the expected performance would be O(n).

false

A Red-Black tree maintains a red node always has black children.

true

The tree below is a true red-black tree.

false

A Red-Black tree maintains the number of black nodes in any path from the root to a leaf is the same.

true

If the array happens to be sorted before selection sort begins, no exchanges will be required.

true

The algorithm for insertion into a Red-Black tree follows the same recursive search process used for all binary search trees to reach the insertion point.

true

The order of a B-tree is defined as the maximum number of children for a node.

true

The easiest way to keep a tree balanced is never to let it become unbalanced. If any node becomes critical and needs rebalancing, rebalance immediately.

true

When we remove an item from a left AVL subtree, the balance of the local root is decreased.

false

When we remove an item from a left AVL subtree, the balance of the local root is decreased.

false

In a Red-Black tree, a node can have one child.

false