Brainscape's Knowledge GenomeTM

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


See full index

CS YEAR ONE > DSA - Trees > Flashcards

DSA - Trees Flashcards

1
Q

What is a Tree?

A
  • Very Flexible and powerful data structure
  • Involves connect NODES like LL
  • Has a Hierarchal structure unlike linear structure of LL
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Define Root:

A

-Node that has no incoming edges (HAS NO PARENTS)
- Unique node at the base of the tree (TOP)

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

Give 4 example of Types of Trees

A
  • Unary Tree ==> (0-1 Children) ≈ LL
  • Binary Tree ==> (0-2 Children)
  • Ternary Tree ==> (0-3 Children)
  • Quad Tree ==> (0-4 Children)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Define Leaf:

A

-Node that has no outgoing edges (HAS NO CHILD NODES)

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

Define Height:

A

-Length of longest path from root to leaf
LEVEL ≡ HEIGHT
STARTS AT 0

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

Define Size:

A

No. of Nodes

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

Define Edge:

A

The Link that connects nodes

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

What is Height & Size of tree with 1 node?

A

Height = 0
Size = 1

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

What is Height & Size of tree with no node?

A

Height = -1
Size = 0

AKA EMPTY TREE

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

Name the 3 Tree Implementation Options :

A
  • BASIC
  • Sibling List
  • Array
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Explain Basic implementation?

A

A Doubly Linked List that has a field value and right and left child pointer
- Prev Pointer points to left child
- Next Pointer points to right child

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

Explain Sibling list Implementation?

A

Similar to basic in that it is a Doubly Linked List however, the Prev pointer points to left child and the Next pointer point to the sibling of the left child
(This node should be right child of the parent)

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

Explain Array Implementation?

Binary Trees

A

Binary Trees use this Array layout where index 1 is the root and the children of node at index i is 2i & (2i)+1

example:
[X|33|10|30|X|X|21|1|X|X|X|X]
33 is root
10 & 30 are 33’s Children
21 & 1 are 30’s Children

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

Define Binary Tree ADT

A

Each Parent has only 2 Child Nodes

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

What does constructor EmptyTree()?

A

Returns an empty tree

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

What does constructor MakeTree(V,L,r)?

A

Returns a new tree, where root node has value V, left subtree l & right subtree r

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

What does the accessor isEmpty(t)?

A

Returns tree if list is empty, otherwise False

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

What does root(t) do?

A

Returns the root node value of the tree

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

What does left(t) do?

A

Returns the left subtree of the tree

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

What does right(t) do?

A

Returns the right subtree of the tree

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

CODE to Create a Tree?

A

MakeTree(33,
leaf(10),
MakeTree(30,
MakeTree(21,
EmptyTree,
Leaf(25))),
Leaf(1)))

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

CODE to Reverse a Tree Order?

A

reverseTree(t) {
if( isEmpty(t)
return (t)
else
return (MakeTree(root(t)),
reverseTree(right(t))
reverseTree(left(t))
}

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

What does FLATTEN do to the Tree?

A

Turns the tree into a list (maybe Linked List)
Usually Starting with Left subtree, Root , Right subtree

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

CODE to Flatten?

A

flatten(t) {
if Tree.isEmpty(t)
return EmptyList
else
return append(flatten(left(t)),
MakeTree(root(t), flatten(right(t)))))
}

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

What Defines a Quad Tree?

A
  • Has 4 Children
  • Only Leaf Node holds values
  • Internal Nodes Have 4 Children
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is useful about Quad Tree?

A

Representing 2D data, like images (image compression)

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

What does the Constructor baseQT do?

A

Returns a single leaf node quad tree with a value

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

What does MakeQT(luqt,ruqt,llqt,rlqt) do?

A

Returns a new quad tree, built for 4 sub-quad trees

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

What does accessor isValue(qt)do?

A

returns true if qt is a value node quad Tree

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

CODE to ROTATE QT?

A

rotate(qt) {
if( isValue(qt) )
return qt
else
return makeQT( rotate(rl(qt)),
rotate(ll(qt)),
rotate(ru(qt))
rotate(lu(qt))) }

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

What does the Code to Rotate DO?

A

90 degree Rotation

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

Define Binary Search Tree:

A
  • Holds value in such a way that we can quickly search/ insert elements so that we can find them
  • VALUES in Left subtree are smaller than the root
  • VALUES in Right subtree are larger than the root
  • The subtrees are also BST
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

What happens when a BST is flattened?

A

The values are returned in ORDER

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

CODE for Insertion in BST:

A

insert(v,bst) {
if( isEmpty(bst))
return MakeTree (v, EmptyTree, EmptyTree)
else if ( v < root(bst))
return MakeTree( root(bst), insert(v,left(bst)),
right(bst))
else if (v > root(bst))
return MakeTree(root(bst), left(bst),
insert(v,right(bst)))
else error(“ERROR;_value_already_in_tree”)

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

What is the problem with the Insertion Code?

A

Method is insufficient as it requires us to make a new copy of BTS with additional values

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

What is the CODE for Searching a BST Recursively ?

A

isIn( value v, tree t) {
if( isEmpty(t) )
return false
else if (v == root)
return true
else if (v < root(t))
return isIn(v, left(t)) // searches recursively on either
else // Right/Left Node depending on if
return isIn(v, right(t)) // it is Smaller / Larger

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

What is the CODE for Searching a BST Iteratively?

A

isIn (value v , tree t) {
while (( not isEmpty(t)) and (v != root(t)) )
if (v < root(t) )
t = left(t) // updates t to point to left child
else
t = right(t) // updates t to point to right child
return ( not isEmpty(t))

38
Q

What is the Complexity of Search for this BST:
1
\
2
\
3
\
4

Also Describe it?

A

O(n)

The BST in diagram has all its items are inserted linearly with 1 as its root

39
Q

What is the Complexity of Search for this BST:
4
/ \
2 6
/ \ / \
1 3 5 7

A

O(log_2(n))

40
Q

What is Average Search case for BST?

A

O(log_2(n))

41
Q

What is Average Insertion case for BST

A

O(log_2(n))
- Depends on height of BST which is O(log_2(n))

42
Q

What is Average Height of GENERAL BST?

A

O( √n )

43
Q

What are the 2 Options to Delete BST?

A

First Option:
- Insert all items except the one you want to delete into a new
BST
- COMPLEXITY = O(log_2(n))
- Worse than deleting from an Array: O(n)

Second Option:
- Find the node containing the elements to de DELETED
- If it is a LEAF, REMOVE it
- IF only one of the node’s children is not EMPTY, replace the
node with the root of the non-empty subtree
- Otherwise,
Find the left-Most node in the right subtree replace the value
to be deleted with that of the left-most node and replace the
left-most node with its right child

44
Q

CODE to DELETE BST:

A

delete(value v, tree t){
if(isEmpty(t))
error(“ERROR:_given_items_is_not_in_given_tree”)
else
if( v < root(t))
return MakeTree( root(t), delete(v,left(t)),right(t))
else if ( v > root(t))
return MakeTree( root(t), left(t),delete(v,right(t)))
else
if (isEmpty(left(t)))
return right(t)
else if (isEmpty(right(t)))
return left(t)
else
return smallestNode(right(t), left(t),
removeSmallestNode(t))
}

45
Q

CODE for smallestNode?

A

smallestNode(tree t) {
if (isEmpty(left(t))) // if empty return root
return root(t)
else
return smallestNode(left(t)) // otherwise check left
}

46
Q

CODE for removeSmallestNode?

A

removeSmallestNode(tree t) {
if (isEmpty(left(t))) // if left subtree is empty, your on
return right(t) // the node you want to remove
// may have right child so return that
else
return MakeTree(root(t), removeSmallestNode(left(t)),
right(t))
// Makes a new tree with smallest node removed
// On left subtree everything else is unchanged
}

47
Q

CODE to check Binary Tree is a BST?

A

isbst (tree t) {
if ( isEmpty(t) )
return true
else
return (allsmaller(left(t),root(t)) and isbst(left(t) and
allbigger(right(t), root(t)) and isbst(right(t))))

48
Q

CODE for ALLSMALLER?

A

allsmaller (tree t , value v) {
if (isEmpty(t))
return true
else
return ((root(t) < v) and allsmaller(left(t),v) and
allsmaller(right(t),v))

49
Q

CODE for ALLBIGGER?

A

allbigger (tree t, value v) {
if ( isEmpty(t))
return true
else
return ((root(t) > v) and allbigger(left(t),v) and
allbigger(right(t),v))

50
Q

CODE for Sorting BST?

A

printInOrder (tree t) {
if(not isEmpty(t) ){
printInOrder(left(t))
print(root(t))
printInOrder(right(t))
}
} // CODE essentially flattens the tree

sort (array a of size n) {
t = EmptyTree
for i = 0,1,…,n-1
t = insert(a[i],t) // insert elements in treee
printInOrder(t) // prints them in order
}

51
Q

How do you change the Sorting CODE to insert it into an array?

A

-REMOVE print(root(t))
- Put List<Integer> BST = new ArrayList<>();
- BST.add(root(t))
- keep everything the same</Integer>

52
Q

Define AVL tree:

A

A BST is said to be AVL when it has a balance at every node is either 1,0 or -1

53
Q

Define Height of a Node:

A

Height of a node is the length of the longest path from that node to a leaf

54
Q

How do you Calculate balance of a Tree / At a Node?

A

Height of Left subtree - Height of Right subtree

55
Q

What does a balance of -1 mean?

A

Overweight to right/ Balanced to Right

56
Q

What does a balance of 1 mean?

A

Overweight to left/ Balanced to Left

57
Q

What does a balance of 0 mean?

A

Right & Left subtree have the same maximum length

58
Q

What is the MAX size of the tree?

A

2^(h+1) - 1

59
Q

What is the MIN size of the tree?

A

T_h= F_(h+3) -1
- where F is Fibonacci Sequence
- T_h is Fibonacci Tree
- h is height of Tree

60
Q

How do u make Fibonacci Tree T_n?

A

T_n = T_(n-1) + T_(n-2) + 1

61
Q

How do u draw Fibonacci Tree T_n?

A
  • Draw T_(n-1) & T_(n-2)
  • Then connect these with 1 external NEW node
62
Q

What is Binet’s Formula?

A

F_k = (((√5 +1)/2)^k -((√5 -2)/2)^k ) / √5 = Aprox. O(1.16^k)

Aprox. O(1.16^k) REMEMBER THIS

63
Q

What is Size of AVL tree in its Height?

A

EXOPENTIAL

64
Q

What is Height of AVL tree in its Size?

A

Logarithmic

65
Q

What is the Complexity of Insertion, Deletion & Searching of AVL tree?

A

log(n)
WORST CASE HEIGHT IS LOG IN SIZE

66
Q

Describe the Complexity of Inserting(x)?

A
  • FIND leaf to insert x ==> Takes O(log(n)) steps
  • Insert in leaf ==> O(1) steps
  • DO balancing on way up ==> O(log(n)) many times do O(1)
    steps

IN TOTAL O(log(n))
DELETE IS SIMILAR TO DO THIS

67
Q

Describe the Complexity of Searching(x)?

A

GOES through at MOST O(log(n))- many levels

IN TOTAL O(log(n))

68
Q

What is AVL tree Invariants?

A

BALANCE of EVERY NODE is 1,0,-1
When Inserting a new element into the tree we allow breaking the invariant, then amend this by re-balancing the tree.

69
Q

How does insert work in AVL trees?

A
  • Same a BST Insertion
  • Check balance
  • Fix if balance it is not 1,0,-1
70
Q

What the Four Balance cases?

A

LL,RR,LR,RL

71
Q

How does delete work in AVL trees?

A
  • Same a BST Deletion
  • Check balance
  • Fix if balance it is not 1,0,-1
72
Q

How do you fix Left-Left imbalance (LL)?

A

Right Rotation from the first node you go Left FROM

73
Q

How do you fix Right-Right imbalance (RR)?

A

Left Rotation from the first node you go Right FROM

74
Q

How do you fix Left-Right imbalance (LR)?

A

Left rotation from the node you go left into and the one you go Right from after.

  • THIS BECOMES AN LL CASE:
    Then after the rotation the new root for the subtree, perform a right rotation on it.
75
Q

How do you fix Left-Right imbalance (RL)?

A

Right rotation from the node you go right into and the one you go Left from after.

  • THIS BECOMES AN RR CASE:
    Then after the rotation the new root for the subtree, perform a Left rotation on it.
76
Q

CODE FOR RR:

A

Node leftRotate(Node x) {
Node y = x.right;
Node T2 = y.left;
y.left = x;
x.right = T2;
x.height = max(height(x.left), height(x.right)) + 1;
y.height = max(height(y.left), height(y.right)) + 1;
return y;
}

77
Q

CODE FOR LL:

A

Node rightRotate(Node y) {
Node x = y.left;
Node T2 = x.right;
x.right = y;
y.left = T2;
y.height = max(height(y.left), height(y.right)) + 1;
x.height = max(height(x.left), height(x.right)) + 1;
return x;
}

78
Q

AVL tree uses?

A

-For indexing large records in databases
-For searching in large databases

79
Q

Idea of BST Insertion?

A
  • Takes val and bst as parameters
  • Checks if bst isEmpty if so makes tree with v as root and left , right EmptyTree
  • If root is larger than val, makeTree with root, Insert method on v and left subtree, & right subtree
  • If root is smaller than val, makeTree with root, left subtree and Insert method on v & right subtree
  • else Error value already in tree
80
Q

Idea of RECURSIVELY Searching a BST?

A
  • isIn takes val & tree as parameters
  • Checks if tree is empty , if so returns false
  • Checks if root = val, if so true
  • Checks if val < root , if do a isIn with val and left subtree
    -else do a isIn with val and right subtree
81
Q

Idea of ITERATIVELY Searching a BST?

A
  • isIn takes val & tree (t) as parameters
  • While Tree is not empty and val is not root :
    • check if val < root, if so update t to point to left child
    • else update t to point to right child
  • Return not isEmpty(t), T if value is found/ F if doesn’t exists
82
Q

Idea of Deleting from BST?

A
  • Takes val & tree t as parameters
  • Checks if tree is empty , Returns Error Item is not in tree
  • Checks if val < root if so return
    makeTree(root, delete(v, left(t)),right(t)
  • else Checks if val > root if so return
    makeTree(root, left(t),delete(v, right(t))
  • Otherwise :
    - Check if Left OR Right Child are empty and return the other tree (IF LEFT WAS EMPTY RETURN RIGHT)
  • else return makeTree(smallestNode(right(t),left(t), removeSmallestNode(right(t)))
83
Q

Idea for Deleting the smallestNode?

A
  • Takes tree t as parameter
  • Checks if left child is empty, if so return root
  • else return smallestNode(left(t))
    // REPEATS TILL NO MORE LEFT SUBTREES

t is non-empty BST

84
Q

Idea for removeSmallestNode?

A
  • Takes tree t as parameter
  • Checks if left child is empty, if so return right child

-else return makeTree(smallestNode(right(t),left(t), removeSmallestNode(right(t)))

// NEW TREE WITH SMALLEST NODE REMOVED FROM LEFT SUBTREE & EVERYHTING ELSE IS UNCHANGE

t is non-empty BST

85
Q

Idea for checking if Binary Tree is BST

A
  • If tree is empty it is a valid BST
  • Otherwise BST if:
    • All vals in left branch are < pivot
      USE ALLSMALLER with left(t) & root(t)
    • All vals in right branch are > pivot
      USE ALLSMALLER with right(t) & root(t)
    • Left branch is a valid BST
      USE isBST with t
    • Right Branch is a valid BST
      USE isBST with t
86
Q

Idea for isBst?

A
  • Takes tree as parameter
  • Checks if tree is empty, if so returns true
  • Otherwise
    returns allsmaller(left(t),root(t)) & isbst(left(t)) & allbigger(right(t),root(t)) & isbst(right(t))
87
Q
A
88
Q

Idea for allBigger?

A
  • Takes Tree and val as input
  • Checks if empty, if so returns true
  • Otherwise
    return root(t) > v & allBigger(left(t),v) & allBigger(right(t),v)
89
Q

Idea to Print in Order?

A
  • Take tree as input
  • Check if it is not empty if so PrintInOrder left subtree, root and right subtree

//PRINTS RESULTS IN ORDER

90
Q

Idea of sort in BST?

A
  • Takes an array of size n
  • Make t an emptyTree
  • Iterate through the array, insert the elements in index i of array into t
  • Call PrintInOrder(t) to print values

CS YEAR ONE (15 decks)

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