Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CMSC 123 > Trees + AVL > Flashcards

Trees + AVL Flashcards

1
Q

A tree designed for locating specific keys (values)

A

Search Trees

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Operations of Search Trees

A

SEARCH
MINIMUM
MAXIMUM
SUCCESSOR
PREDECESSOR
INSERT
DELETE

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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
A

Binary Search Tree (BST)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

root, downward

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Search Pseudocode: TreeSearch(x,k)
Recursive Approach

A

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) }
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Search Pseudocode: TreeSearch(x,k)
Iterative Approach

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

left-child

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Tree-Minimum Pseudocode

A

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

return x }
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

right-child

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Tree-Maximum Pseudocode

A

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

return x
}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

Successor

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

TRUE

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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.

A

lowest ancestor, left-child

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Tree-Successor Pseudocode

A

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 }
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

A

Predecessor

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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.

A

lowest ancestor, right-child

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Tree-Predecessor Pseudocode

A

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 }
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

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

A

Insertion, Deletion

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

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

A

Insertion

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Tree-Insert Pseudocode

A

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 }
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

3 Cases for Node Deletion in BST

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Case 1 (No Children) deletion fix-up

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Case 2 (1 Child) deletion fix-up

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Case 3 (2 children) deletion fix-up

A

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)

27
Q

A BST that is height balanced

A

Adelson-Velsky and Landis (AVL) Tree

28
Q

AVL Meaning

A

Adelson-Velsky and Landis Tree

29
Q

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

A

at most 1

30
Q

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

A

rebalancing

31
Q

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

A

-1

32
Q

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

A

rotation

33
Q

AVL Insertion Steps

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

4 Types of Rotations

A

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

35
Q

Node where height imbalance occured

A

Critical node (C)

36
Q

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

A

Pivot node (P)

37
Q

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

A

Q node (Indi ko alam tawag T.T)

38
Q

4 Fix Up cases

A

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

39
Q

Left-Left Leaning Fix Up

A

Right Rotate at Critical node

40
Q

Right-Right Leaning Fix Up

A

Left Rotate at Critical Node

41
Q

Left-Right Leaning Fix Up

A

Left Rotate at Pivot
Right Rotate at Critical node

42
Q

Right-Left Leaning Fix Up

A

Right rotate at Pivot
Left Rotate at Critical node

43
Q

is a connected, acyclic, undirected graph.

A

Free Tree

44
Q

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

A

Rooted Tree

45
Q

The _______________ is the number of edges on the path.

A

path length

46
Q

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

A

height

47
Q

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

A

depth

48
Q

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

A

ancestor

49
Q

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

A

descendant

50
Q

TRUE or FALSE:

Every node is both an ancestor and a descendant of itself.

A

TRUE

51
Q

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

A

proper ancestor, proper descendant

52
Q

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

A

subtree rooted at x

53
Q

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.

A

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

54
Q

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

A

number of nodes – 1.

55
Q

Tree Applications

A

file systems
parsing / parse trees
decision trees
databases

56
Q

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
A

IDK T.T

57
Q

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

A

at most two

58
Q

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

A

2^i nodes

59
Q

TRUE or FALSE:

A binary tree of height k is full if level k is full.

A

TRUE

60
Q

A tree traversal refers to the process of __________________.

A

visiting each node

61
Q

aka tree search or walking the tree

A

Tree Traversal

62
Q

A binary tree used to represent expressions.

A

Binary Expression Trees

63
Q

leaves –> ________________
internal nodes –> _______________

A

operands
operators

64
Q
A

CMSC 123 (4 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions