trees

Question 1

A tree with 𝑁 nodes always has ___ edges

Answer 1

A tree with n nodes has n -1 edges

Question 2

searching in binary search tree pseudocode

Answer 2

if the tree is empty
return NULL
else if the item in the node equals the target
return the node value
else if the item in the node is greater than the target
return the result of searching the left subtree
else if the item in the node is smaller than the target
return the result of searching the right subtree

Question 3

removal in binary search tree pseudocode

Answer 3

if the tree is empty return false

Attempt to locate the node containing the target using the binary search
if the target is not found return false
else the target is found, so remove its node:

Case 1: if the node has 2 empty subtrees
- replace the link in the parent with null

Case 2: if the node has a left and a right subtree
- replace the node’s value with the max value in the
left subtree
- delete the max node in the left subtree

Case 3: if the node has no left child
- link the parent of the node to the right (non-empty) subtree

Case 4: if the node has no right child
- link the parent of the target to the left (non-empty) subtree

Question 4

time complexity of BST operations

Answer 4

The complexity of operations search, insert and remove in BST is 𝑂(ℎ) , where ℎ is the height.

𝑂(log⁡𝑛) when the tree is balanced, i.e., ℎ=𝑂(log⁡𝑛). The updating operations may cause the tree to become unbalanced.

The tree can degenerate to a linear shape and the operations will become 𝑂(𝑛)

Question 5

what is the AVL property

Answer 5

An AVL tree is a binary search tree such that (AVL property):
The height of the left and right sub-trees of the root differ by at most 1
The left and right sub-trees are AVL trees
treat nil tree as height -1

Question 6

AVL insertion

Answer 6

1. insert as in simple BST
2. work your way up tree from the node inserted, restoring AVL property (and updating heights as you go).

Question 7

AVL tree max number of rotations that may need to be done after inserting node

Answer 7

In general, process may need several rotations before done with an Insert. 𝑂(log⁡𝑛) rotations may be required

Question 8

AVL delete

Answer 8

1. Perform standard BST delete
2. Work your way up tree from the node deleted, restoring AVL property (and updating heights as you go).

Question 9

AVL tree advantages and disadvantages

Answer 9

Advantages
𝑂(log⁡𝑛) worst-case searches, insertions and deletions

Disadvantages
Complicated Implementation
Must keep balancing info in each node
To find node to balance, must go back up in the tree: easy if pointer to parent, otherwise difficult
Deletion complicated by numerous potential rotations