Free Lines Arrow
본문 바로가기
728x90

Algorithm/알고리즘 기본27

[Algorithm] Graph Graph 그래프의 개념을 알아 보고 구현을 해본다. Graph 의 구조 Graph 는 Vertex(Node) 와 Edge 를 가지는 자료 구조이다. Vertex: 정점 Edge: 간선 G(V,E) : 그래프는 정점과 간선으로 이루어져 있다. Adjacent Vertex: 인접정점 으로 하나의 정점과 연결되어 있는 정점을 말한다. 정점 v1 과 V2 가 Edge 로 연결 되어 있다고 하면 다음과 같다. Graph 의 종류 무방향 그래프 방향 그래프 가중치 그래프 무방향 그래프 무방향은 말 그대로 방향이 없는 그래프이다. 위 그래프를 정점과 노드로 표현 하면 다음과 같다. V = {V1, V2, V3, V4, V5} E = {(V1, V2), (V1,V3), (V2,V4), (V2,V5), (V3,V4),.. 2021. 7. 21.
[Algorithm] Binary Search Tree - Tree traversal Binary Search Tree 의 Tree traversal구현 마지막으로 순회를 알아보자 순회의 종류 Preorder(전위 순회) : Root -> Left -> Right 순으로 방문한다. Inorder(중위 순회) : Left -> Root -> Right 순으로 방문한다. Postorder(후위 순회) : Left -> Right-> Root 순으로 방문한다. 그림으로 보는게 빠를것 같다. 순회 예시 코드 public void preOrder(Node node) { if (node == null) { return; } System.out.println(node.getData()); preOrder(node.left); preOrder(node.right); } public void inOrde.. 2021. 6. 10.
[Algorithm] Binary Search Tree - Delete Binary Search Tree 의 Delete구현 지금 까지 Binary Search Tree의 정의, Insert, Search, Successor, Predecessor 에 대해서 알아봤다. 아래에 링크가 있으니 처음부터 보면 도움이 될것이라 생각합니다. Delete 구현 delet를 구현할때 다음과 같은 사항을 고려해야한다. 삭제할 노드의 자식이 아예 없을때 삭제할 노드의 자식이 하나만 있을때 삭제할 노도의 자식이 둘다 있을때 왜 고려해야 될까? 우리는 Insert 할때 규칙을 만들어서 Binary Search Tree를 구현하였다. 그렇기 때문에 규칙을 유지해 가면서 Tree를 삭제해야 된다. 삭제 노드의 자식이 아예 없을때 제일 간단하다 그냥 삭제노드와 삭제노드의 부모와 연결을 끊어준다. !.. 2021. 6. 9.
[Algorithm] Binary Search Tree - Successor, Predecessor Successor, Predecessor 지금 까지 Binary Search Tree의 정의, Insert, Search에 대해서 알아봤다. 그럼 왜? Delete를 먼저 구현하지 않고 Successor, Predecessor 를 먼저 구현해보는것일까? 그것은 Delete를 할때 여러가지 조건이 있고 Delete를 안정적으로하기 위해서 필요하기 때문이다. Successor 란? 선택한 노드의 오른쪽 서브트리중 가장 작은값을 가지는 노드를 의미한다. 50 을 선택하면 일단 50 노드의 오른쪽 서브트리를 찾는다 그중 가장 최소값 즉 왼쪽으로 계속 이동하면서 작은 값을 찾는다. 그말인 즉슨 선택한 노드보다 크면서 제일 작은값이다. Successor 의 코드구현 public Node getSuccessor(No.. 2021. 6. 8.
728x90
반응형

티스토리툴바