728x90 Algorithm77 [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. [Algorithm] Binary Search Tree - Search Binary Search Tree 의 Search 구현 앞에서 Binary Search Tree의 정의와 insert를 구현을 해봤다. 이번에는 Search를 알아보고 구현해보자. Search 구현 search 구현은 참 간단하다 그래도 설명을 하면 더 쉽게 이해 되니 그림으로 먼저 알아보자. 일단 글로 설명하자면 root 부터 비교를 한다 root 값보다 작으면 왼쪽으로 이동 root 값보다 크면 오른쪽으로 이동 이동하면서 탐색을 반복한다. Search 코드 구현 // rootNode 는 멤버면수이다. public Node searchNode(int data) { // rootNode 가 null 이면 리턴 if (rootNode == null) { System.out.println("Can not f.. 2021. 6. 8. [Algorithm] Binary Search Tree - Insert Binary Search Tree 컴공때 배웠던걸 복습할겸 다시 공부할겸 정리할겸 겸사겸사 특징 자식을 최대 2개만 가질수 있는 트리이다. root 의 왼쪽값은 root 의 값보다 작다. root 의 오른쪽 값은 root의 값보다 크다. Insert, Search, Delete, Successor, Predecessor 을 구현한다. Binary Search Tree 의 구조 다음은 Binary search tree 의 구조이다 100 이 처음에 들어와 루트가 되었고 50 을 넣을때 100 과 비교한다. 부모보다 작기 때문에 왼쪽에 추가해준다. 200 이 들어왔을때 부모의 값보다 크기 때문에 오른쪽 에 추가해준다. 이걸 반복하면 다음과 같은 그림이 된다. Insert 구현 위의 예시대로 구현 하면된다. .. 2021. 6. 8. 이전 1 ··· 13 14 15 16 17 18 19 20 다음 728x90 반응형
