재민

이진 탐색 트리는 탐색을 효율적으로 하기 위한 자료구조로서, 이진트리이자 모든 원소는 서로 다른 key를 가지는 특성을 가지고 있다. 이진탐색에서의 탐색은 searchBST() 연산을 이용하여 진행된다. 우선 루트에서 시작하여, 탐색할 key값 x를 루트 노드의 key값과 비교한다. key값보다 루트 노드의 key값이 클 경우 왼쪽 서브트리에서, key값이 루트노드의 key값보다 클 경우 오른쪽 서브트리에서 탐색을 진행한다는 기본 메커니즘을 기반으로 탐색을 진행한다. 이진탐색에서 탐색의 구현은 반복/재귀가 있다. 반복적 방법은 while p != NULL을 이용하여 p값을 찾을 때까지 삽입 연산을 계속 수행하는 방법이고, 재귀적 방법은 찾고자하는 key값이 해당 key값보다 클 경우 범위를 제한하여 다시..

이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 가리키는 포인터를 가지고 있어서, 양방향으로 탐색이 가능하며, 삭제 시 양쪽의 연결을 수정해야 한다. Doublely Linked List에서 노드의 삭제는 다음과 같은 순서로 이루어진다. 1) 삭제할 노드의 오른쪽 노드와 왼쪽 노드를 탐색한다. 2) 삭제할 노드의 오른쪽 주소를 삭제할 노드의 왼쪽 노드의 rlink에 저장한다. 3) 삭제할 노드의 왼쪽 노드 주소를 삭제할 노드의 오른쪽 노드의 llink에 저장한다. 4) 삭제할 노드를 삭제한다. [코드로 구현하기] #include #include // 이중 연결 리스트의 노드 구조체 정의 struct Node { int data; struct Node* llink; // 왼쪽 노드를 가리키는 포인터..

Linked List에서 삭제는 다음과 같은 순서로 이루어진다. 1) 삭제할 노드의 앞 노드를 찾는다. 앞 노드를 찾는 이유는 크게 두가지인데, 연결관계를 해제하기 위해서이자 노드를 효율적으로 찾아 해제시키는 방법이기 때문이다. 2) 앞 노드의 링크필드에 삭제할 노드의 링크 필드값을 저장한다. 3) 삭제할 노드를 삭제하고, 메모리를 해제한다. 삭제 연산을 c로 구현하면 다음과 같다. #include #include // 단일 연결 리스트의 노드 정의 struct Node { int data; struct Node* next; }; // 연결 리스트의 헤드를 전역 변수로 선언 struct Node* head = NULL; // 연결 리스트에 노드 추가 void insertNode(int val) { str..