Trees + AVL

Question 1

A tree designed for locating specific keys (values)

Answer 1

Search Trees

Question 2

Operations of Search Trees

Answer 2

SEARCH
MINIMUM
MAXIMUM
SUCCESSOR
PREDECESSOR
INSERT
DELETE

Question 3

Is a binary tree that satisfies the following properties:

For any node x:

• the keys in the left subtree of x are <= x.key
• the keys in the right subtree of x are >= x.key

Answer 3

Binary Search Tree (BST)

Question 4

Search begins at the _________ and traces a __________ path in the tree using BST Property

Answer 4

root, downward

Question 5

Search Pseudocode: TreeSearch(x,k)
Recursive Approach

Answer 5

TreeSearch(x,k){
if x == NULL or k == x.key
return x

   if k < x.key
         return TreeSearch(x.left, k)
   else
         return TreeSearch(x.right, k) }

Question 6

Search Pseudocode: TreeSearch(x,k)
Iterative Approach

Answer 6

TreeSearch(x,k){
while x != NULL and k != x.key
if k < x.key
x = x.left
else
x = x.right
return x
}

Question 7

To get the minimum, just follow the ________________ pointers from the root

Answer 7

left-child

Question 8

Tree-Minimum Pseudocode

Answer 8

TreeMinimum(x){
while x.left != NULL
x = x.left

return x }

Question 9

To get the maximum, just follow the ________________ pointers from the root

Answer 9

right-child

Question 10

Tree-Maximum Pseudocode

Answer 10

Tree-Maximum(x){
while x.right != NULL
x = x.right

return x
}

Question 11

The ______________ of a node is the next node visited in an inorder traversal

Answer 11

Successor

Question 12

TRUE or FALSE

If all keys are distinct, the successor of a node x is the node with the smallest key greater than x.key

Answer 12

TRUE

Question 13

If the right subtree of node x is non-empty, then the successor of x is the ___________________________.

Answer 13

leftmost node in x’s right subtree (minimum of right-subtree)

Question 14

If the right subtree of node x is empty, then the successor of x is the ______________ of x whose ______________ is also an ancestor of x.

Answer 14

lowest ancestor, left-child

Question 15

Tree-Successor Pseudocode

Answer 15

Tree-Succcessor(x){
if x.right != NULL
return Tree-Minimum(x.right)

 else
     y = x.parent
     while y != NULL and x == y.right
         x = y
         y = y.parent
      
     return y }

Question 16

The ______________ of a node is the previous visited node in an inorder traversal

Answer 16

Predecessor

Question 17

If the left subtree of node x is non-empty, then the predecessor of x is the ___________________________.

Answer 17

rightmost node in x’s left subtree (maximum of left subtree)

Question 18

If the left subtree of node x is empty, then the predecessor of x is the ______________ of x whose ______________ is also an ancestor of x.

Answer 18

lowest ancestor, right-child

Question 19

Tree-Predecessor Pseudocode

Answer 19

Tree-Predecessor(x){
if x.left != NULL
return Tree-Maximum(x.left)

 else
     y = x.parent
     while y != NULL and x == y.left
         x = y
         y = y.parent
      
     return y }

Question 20

___________ and ___________ operations change BST in a way that the BST property is preserved

Answer 20

Insertion, Deletion

Question 21

_________ searches for a NULL to replace with the new node Z

Answer 21

Insertion

Question 22

Tree-Insert Pseudocode

Answer 22

Tree-Insert(T,x){
x = T.root
y = NULL

while x != NULL
      y = x
      if z.key <= x.key
         x = x.left
     else
         x = x.right

 z.p = y
 if y == NULL
     T.root = z
 else if z.key <= y.key
       y.left = z
 else
      y.right = z }

Question 23

3 Cases for Node Deletion in BST

Answer 23

Case 1: No Children
Case 2: Has 1 Child
Case 3: Has 2 Children

Question 24

Case 1 (No Children) deletion fix-up

Answer 24

Remove it by replacing its parent’s child pointer to NULL

Question 25

Case 2 (1 Child) deletion fix-up

Answer 25

Elevate the child to take z's position in the tree. Modify z's parent to replace z with z's child (z here is the node to be deleted)

Question 26

Case 3 (2 children) deletion fix-up

Answer 26

Find z's successor y (in z's right subtree) and replace z's key with y's. Perform delete operation on y (case 1 or 2)

Question 27

A BST that is height balanced

Answer 27

Adelson-Velsky and Landis (AVL) Tree

Question 28

AVL Meaning

Answer 28

Adelson-Velsky and Landis Tree

Question 29

In AVL, for each node, the heights of its left and right subtrees differ by __________.

Answer 29

at most 1

Question 30

In AVL, whenever the height differs by more than 1, _________ is done

Answer 30

rebalancing

Question 31

The height of an empty tree (or subtree) is ___.

Answer 31

-1

Question 32

Insertion could disrupt the AVL height balance property. We fix this via ___________

Answer 32

rotation

Question 33

AVL Insertion Steps

Answer 33

1. Do BST Insert 2. from the node inserted up to the root, we update the balance and do fix up when necessary

Question 34

4 Types of Rotations

Answer 34

Single Rotation (Left and Right) Double Rotation (Left-Right and Right-Left)

Question 35

Node where height imbalance occured

Answer 35

Critical node (C)

Question 36

Child of critical node that is an ancestor of the inserted node

Answer 36

Pivot node (P)

Question 37

Child of pivot node that is an ancestor of the inserted node

Answer 37

Q node (Indi ko alam tawag T.T)

Question 38

4 Fix Up cases

Answer 38

Left-Left Leaning Right-Right Leaning Left-Right Leaning Right-Left Leaning

Question 39

Left-Left Leaning Fix Up

Answer 39

Right Rotate at Critical node

Question 40

Right-Right Leaning Fix Up

Answer 40

Left Rotate at Critical Node

Question 41

Left-Right Leaning Fix Up

Answer 41

Left Rotate at Pivot Right Rotate at Critical node

Question 42

Right-Left Leaning Fix Up

Answer 42

Right rotate at Pivot Left Rotate at Critical node

Question 43

is a connected, acyclic, undirected graph.

Answer 43

Free Tree

Question 44

is a free tree in which one of the vertices is distinguished from the others (root).

Answer 44

Rooted Tree

Question 45

The _______________ is the number of edges on the path.

Answer 45

path length

Question 46

The _________ of a node is the length of the longest downward path from that node to a leaf.

Answer 46

height

Question 47

The _________ of a node is the length of the path from the root to that node.

Answer 47

depth

Question 48

Any node y on the path from root to a node x is an ___________ of x.

Answer 48

ancestor

Question 49

If y is an ancestor of x, then x is a _____________ of y.

Answer 49

descendant

Question 50

TRUE or FALSE: Every node is both an ancestor and a descendant of itself.

Answer 50

TRUE

Question 51

If y is an ancestor of x and x ≠ y, then y is a ________________ of x and x is a __________________ of y.

Answer 51

proper ancestor, proper descendant

Question 52

The _________________ is the tree induced by descendants of x, rooted at x.

Answer 52

subtree rooted at x

Question 53

TRUE or FALSE A tree consists of the root (r) and one or more subtrees T1, T2, ... , Tk each of whose roots are children of r.

Answer 53

FALSE, a root can have no subtree but still be a tree

Question 54

The number of edges in a tree is equal to the ________________ .

Answer 54

number of nodes – 1.

Question 55

Tree Applications

Answer 55

file systems parsing / parse trees decision trees databases

Question 56

A binary tree T is a structure defined on a finite set of nodes that either - contains no nodes, or - is composed of a root node, a binary tree called its left subtree, and a binary tree called its right subtree

Answer 56

IDK T.T

Question 57

A binary tree is a rooted tree in which every node has ___________ children.

Answer 57

at most two

Question 58

Level i is full if there are exactly _________ at that level.

Answer 58

2^i nodes

Question 59

TRUE or FALSE: A binary tree of height k is full if level k is full.

Answer 59

TRUE

Question 60

A tree traversal refers to the process of __________________.

Answer 60

visiting each node

Question 61

aka tree search or walking the tree

Answer 61

Tree Traversal

Question 62

A binary tree used to represent expressions.

Answer 62

Binary Expression Trees

Question 63

leaves –> ________________ internal nodes –> _______________

Answer 63

operands operators