Transcript Advanced Data Structures

4. Advanced Data Structures
 Priority Queue
 An abstract data type to efficiently support finding the item with the
highest priority across a series of operations.
4. Advanced Data Structures
1
Methods (PriorityQueue.java)
메서드
기능
public boolean offer(E o)
지정된 요소를 우선순위 큐에 삽입합니다.
public E peek()
큐의 선두를 취득합니다만, 삭제하지 않습니다.
public boolean add(E o)
지정된 요소를 이 큐에 추가합니다.
public boolean remove(Object o)
지정된 요소의 단일의 인스턴스가 있는 경우는 큐로부터 삭
제합니다.
public Iterator <E> iterator()
이 큐 내의 요소의 반복자를 돌려줍니다.
public int size()
이 컬렉션중의 요소의 수를 돌려줍니다.
public void clear()
우선순위 큐로부터 모든 요소를 삭제합니다.
public E poll()
큐의 선두를 취득 및 삭제합니다.
public Comparator <? super E >
comparator()
컬렉션의 순서부에 사용하는 콤퍼레이터를 돌려줍니
다.
E: 요소들의 그룹(컬렉션)을 나타내는 인터페이스
제너릭 타입(Generic Types)은 주로 자바 컬렉션에서 많이 사용되고 있다. 컬렉션은 자
료구조이다. 컬렉션에는 어떤 자료를 담을지 알 수 없으므로 최상위 객체인 Object 형태
로 저장되고 관리되도록 설계되어 있다. 제너릭 타입을 사용하면 프로그래머가 원하는
객체의 타입을 명시해서 의도하지 않은 객체는 저장될 수 없도록 컴파일시에 오류를 확
인할 수있게 된다.
4. Advanced Data Structures
2
 Heap
 An essentially complete binary tree is a binary tree that satisfies the
following conditions:
 It is a complete binary tree down to a depth of d-1.
 The nodes with depth d are as far to the left as possible
 A heap is an essentially complete binary tree such that
 The values stored at the nodes come from an ordered set.
 The value stored at each node is greater than or equal to the values stored at
its children. This is called the heap property.
30
25
20
18
16
12
14
4. Advanced Data Structures
19
17
11
3
 Tree
 A tree is an acyclic, connected, undirected graph.
 A tree may be defined as an undirected graph in which there exists
exactly one path between any given pair of nodes.
 Simple properties
 A tree with n nodes has exactly n-1 edges.
 If a single edge is added a tree, then the resulting graph contains exactly
one cycle.
 If a single edge is removed from a tree, then the resulting graph is no
longer connected.
 Tree traversal
 To traverse a non-empty binary tree in preorder (depth-first traversal),
perform the following operations recursively at each node, starting with the
root node:
1.Visit the root.
2.Traverse the left subtree.
3.Traverse the right subtree.
4. Advanced Data Structures
4
 To traverse a non-empty binary tree in inorder (Symmetric traversal) perform
the following operations recursively at each node:
1.Traverse the left subtree.
2.Visit the root.
3.Traverse the right subtree.
 To traverse a non-empty binary tree in postorder (breadth-first traversal),
perform the following operations recursively at each node:
1.Traverse the left subtree.
2.Traverse the right subtree.
3.Visit the root.
4. Advanced Data Structures
5
 A binary tree representing an arithmetic expression
-
+
/

3
+
3
1
2
-
9
6

+
-
3
5
4. Advanced Data Structures
7
4
6
 Tree Traversal
 Preorder
-/+313+-952+3-746
 Inorder
3+13/9-5+2-37-4+6
 Postorder
31+395-2+/374-6+-
 Priority Queue
 Heap(1)
 Heap(2)
 Tree
4. Advanced Data Structures
7