cse 3

what is m in load factor n/m?

length of array

To determine whether the tree is balanced or not

we have to measure its height

Height of a tree (or a node) is the longest path from the root (or from the node) to a

leaf node

For BST: height = max (? ) + 1

left child’s height , right child’s height

The height of a NULL node is

\-1

leaf nodes have height

0

Use ? to determine if trees are imbalanced

balance factor

balance factor formula

hleft - hright

trees of both height can differ by

1

\-ve balance factor = right-heavy tree = rotate ?

left

\+ve balance factor = ? = rotate right

left heavy tree

AVL trees have what guaranteed time for all operations

o(logn)

For N nodes =

N-1 edges (parent child relation)

all nodes are accessible through?

root

There is only one path to reach any node from?

root

Trees are a special form of

graphs

Edges can connect any vertex in any possible way

any possible way

Any vertex can be accessed through

any path

A graph is a way of representing relationships that exist between

pairs of objects

A Graph G can be represented as an ordered pair of a set V of vertices and a set E of ?

edges

Edges in graphs can be directed or

undirected

Adjacent Vertices: Two vertices, u and v, connected together via the same ?

edge

An edge is said to be ? to a vertex if the vertex is one of the edge’s endpoint

incident

A ? is a sequence of alternating vertices and edges that starts at a vertex and ends at a ? such that each edge is incident to its predecessor and ? vertex.

path, vertex, successor

Cycle is a path that starts and ends at the same

vertex and includes at least one edge

Undirected Graphs: Edges do not have a ?

direction

Undirected Graphs: Edge (u, v) will be equivalent to the edge ?

(v, u)

Directed Graphs or Digraphs: Edges have a direction pointing from

one vertex to another vertex

Mixed Graphs: Edges have a direction pointing from one vertex to another vertex and some edges are undirected

one vertex to another vertex

Directed Acyclic Graphs: Finite directed graph with no

cycles

Complete Graphs: All vertices are connected to

each other

Unweighted graphs: all edges are of equal weight of

1

Weighted graphs: have different values associated to ?

edges

What is the order that Breadth-First Search (BFS) goes by to visit nodes/vertices

starts from top of height all the way to leafs by row

What is the order that Depth-First Search (DFS) goes by to visit nodes/vertices

starts from left side all the way down to leaf then middle, then right side down to leaf

Time complexity of Breadth-First Search (BFS) ?

O(V+E)

BFS Memory complexity is not good bc it stores many references so ? is usually preferred

DFS

DFS constructs a ? for unweighted graphs (smaller number of edges)

\

Shortest path

DFS uses ?

stack LIFO

BFS uses ?

queue FIFO

Vertex is a

node

edge

lines that connect nodes

time complexity for DFS

o(v+e)

DFS is used to solve

mazes

BFS Walk through all nodes on the same ?

level

BFS is based on

queues

BFS is suitable for searching nearby

vertices

BFS has no concept of

backtracking

DFS goes as deep as possible until there is ?

no neighbor left

DFS is based on

stacks

Suitable for searching vertices farther away from

the source

DFS can recursively ?

backtrack

On what side is the predeccor?

left

on what side is the successor ?

right

if you delete a root node what will be the new root? Predecessor or Successor?

predecessor, largest item in right subtree

Pre-order traversal Visit root node first, then

left-subtree and finally right-subtree

Post-order traversal Visit left-subtree first, then

right-subtree, and finally the root node

In-order traversal Visit left-subtree first, then

root node, and finally right-subtree

what is the pre order traversal

32,10,1,19,16,23,55,79

what is the post order traversal

1,16,23,19,10,79,55,32

what is the in order traversal

1,10,16,19,23,32,55,79

stack all operation time

o(1)

queue: dequeue operation time

o(n)

linked list operation time to remove tail element

o(n)

doubly linked list time operation

o(1)

hash tables time operation to locate bucket

o(1)

hash tables time operation to locate element

o(n)

Each element in a tree has a parent element and children

zero/more

Edge: Connection between ? nodes to show a relationship between them

2

Path: A path is an ordered list of nodes that are connected by ?(from top to bottom)

edges

Height of a node x: number of edges in **longest** path from the **node** x to a ?

leaf

Depth/Level of node x: **Number** of **edges** in path from ? to **node** x

root

Degree of a **node**: The number of its ?

children

Degree of a **tree**: Total number of ? in it

nodes

In a tree, there must only be a ? path from the root node to any other node

single

Every node in the tree can have at most ? children (left child and right child)

2

balanced BST time

o(logn)

imbalanced BST time

o(n)

mapping can be defined as an association between

2 objects

mapping associated objects can be referred as

key value pairs

array of key-value pairs are sometimes referred as

associative arrays or maps

Unlike a standard array, indices for a map need not be

consecutive nor even numeric.

Unlike Python, many other programming languages ? have a built-in mapping data type like dictionary

do not

Elements are stored as ? in the list

objects

Searching a particular key requires ? time complexity

o(n)

How does the dictionary have o(1) time complexity for all operations? Python Dictionary is implemented with another?

data structure

• We can pass any “?”of key into a mechanism to convert it into indices/codes

type

The goal of a hash function, h, is to map each key, k, to an integer in the range \[?\]

\[0, N - 1\]

N in \[0, N - 1\] is the ?

capacity of a hash table

what is the value of “Tim” in the map, M, containing N=11 memory locations?

1

Ali = ? % 11

3

Sue = ? % 11

4

Mia = ? % 11

4

if N=11 memory locations what is the last value of the index

10

We can store multiple items in any

specific bucket

what is a bucket in code

M\[j\]

M is the ? of buckets

array

j is the

index generated by hash function

Time to search for the bucket is

O(1)

Time to search a key in the bucket depends on the size of the bucket. So for size m time complexity is

O(m)