Pert4 Flashcards Preview

Data Structures > Pert4 > Flashcards

Flashcards in Pert4 Deck (16):
1

Tree yang storing NULL pointer yaitu?

Threaded binary tree

2

Syarat Binary Search Tree?

– Every node has a key and no two nodes have the
same key (keys are unique).
– Left sub tree’s keys are smaller than root’s key.
– Right sub tree’s keys are larger than root’s key.
– The left and right sub trees are also binary search tree (recursively).

3

4 jenis binary tree?

• PERFECT binary tree is a binary tree in which every level are at the same depth.

• COMPLETE binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. A perfect binary tree is a complete binary tree.

• SKEWED binary tree is a binary tree in which each node has at most one child.

• BALANCED binary tree is a binary tree in which no leaf is much
farther away from the root than any other leaf (different balancing scheme allows different definitions of “much farther”).

4

what is binary tree?

sebuah rooted tree data structure dimana setiap node memiliki paling banyak 2 children

5

Perbedaan array dan linked list

Array:
- Linear collection of data elements
- Store value in consecutive memory locations
- Can be random in accessing of data

Linked List:
- Linear collection of nodes
- Doesn’t store its nodes in consecutive memory locations
- Can be accessed only in a sequential manner

6

Depth First Search (DFS)

algorithm for traversing or searching in a tree or graph. We start at the root of the tree (or some arbitrary node in graph) and explore as far as possible along each branch before backtracking.
DFS has many applications, such as:
• Finding articulation point and bridge in a graph
• Finding connected component
• Topological sorting

7

DFS pake data struktur apa?

Stack

8

BFS pake data struktur apa?

Queue

9

Stack are widely used to?

• Reverse the order of data
• Convert infix expression into postfix
• Convert postfix expression into infix
• Backtracking problem
• System stack is used in every recursive function
• Converting a decimal number into its binary equivalent

10

Queue Applications?

• Deques
• Priority Queues
• Breadth First Search

11

Deque?

is a list in which elements can be inserted or deleted at either end. It is also known as a head-tail linked list, because elements can be added to or removed from the front (head) or back (tail).

12

Deque dikenal juga?

head-tail linked list

13

Priority Queue?

an abstract data type in which the each element is assigned a priority.

14

dalam priority queue, lower priority number berarti?

higher priority. sort ascending

15

Breadth first search (BFS)?

an algorithm for traversing or searching in a tree or graph.
We start at the root of the tree (or some arbitrary node in graph) and explore all neighboring nodes level per level until we find the goal.

16

BFS has many applications, such as:

BFS has many applications, such as:
• Finding connected component in a graph.
• Finding shortest path in an unweighted graph.
• Ford-Fulkerson method for computing maximum flow.