Flashcards in Pert4 Deck (16):
Tree yang storing NULL pointer yaitu?
Threaded binary tree
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).
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”).
what is binary tree?
sebuah rooted tree data structure dimana setiap node memiliki paling banyak 2 children
Perbedaan array dan linked list
- Linear collection of data elements
- Store value in consecutive memory locations
- Can be random in accessing of data
- Linear collection of nodes
- Doesn’t store its nodes in consecutive memory locations
- Can be accessed only in a sequential manner
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
DFS pake data struktur apa?
BFS pake data struktur apa?
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
• Priority Queues
• Breadth First Search
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).
Deque dikenal juga?
head-tail linked list
an abstract data type in which the each element is assigned a priority.
dalam priority queue, lower priority number berarti?
higher priority. sort ascending
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.