어느덧 벌서 5장, 총 8장까지인데 어느덧 중반을 향하고 있다.
탐색트리는 앞서 했던 트리의 자료구조의 일종이다.
트리 + 이진 탐색을 접목 시킨 구조라 볼 수 있다.
1. 이진탐색(binary Search)
탐색을 하는 방법이다.
기존의 선형구조의 경우 원하는 원소를 찾기 위해선 순차로 검색해야했고
이럴 경우 O(n)의 시간이 소요,
그렇기에 이걸 반씩 나눠 찾자 라는 개념.
즉 1-10까지 있을때 10을 찾기 위해선 10번 해야할껄
5 - 7 - 9 - 10 이런식으로 단축해서 찾을 수 있다.
2. 이진탐색트리
이진탐색의 방법을 트리로 적용 시켜서 만든것.
단순 연결리스트의 중간의 레퍼런스 연결을 바꾸고,
이걸 반복하고.. 말로는 설명하기어렵다.
이진탐색트리의 경우
노드 기준 왼쪽노드 들은 해당 노드보다 작아야 하고 오른쪽은 커야한다.
50
80
10 90
위 트리는 10 때문에 안된다. 50보다는 커야하기 때문.
3. 코드
3.1 탐색연산
기본 컨셉은 찾는값(k)과 루트 비교 -> k가 루트보다 크면 오른쪽으로
k가 루트보다 작으면 왼쪽으로,
이 방법을 재귀로 계속...
# self는 클래스 안에 만든 함수라 들어가있다.
def get(self, k):
return self.get_item(self.root, k)
def get_item(self, n, k):
if n == None: # 루트에 아무것도 없다면 -> 찾는게 없다
return None
if n.key > k : # 찾는값이 작으니 왼쪽으로
return self.get_item(n.left, k)
elif n.key < k: # 찾는값이 크니 오른쪽으로
return self.get_item(n.right, k)
else:
return n.value
어려운 코드는 아니다.
3.2 삽입연산
탐색연산과 유사하지만 return이 다르다.
여기서 상당히 해맸는데, 재귀함수를 사용하는 이유와 결과를 잘 이해해야 한다.
재귀함수는 결국 큰 것을 작은 부분으로 나누어 이해하기 위함이라는 사실을 인지하고 들어가자
def put(self, key, value):
self.root = self.put_item(self.root, key, value)
# 위에 코드와 비교하면 얘는 return을 안하고 self.root, 즉 루트값을 받게끔 되어있다.
def put_item(self,n, key, value):
if n == None:
return Node(key, value) # 결국 아무것도 없는 곳 까지 갔을때 node를 삽입한다. 근데 여기서 끝이 아니다. 이 return 값이 위로 쭉쭉 올라가야한다
if n.key > key:
n.left = self.put_item(n.left, key, value)
elif n.key < key:
n.right = self.put_item(n.right, key, value)
else:
n.value = value
return n
30
20 40
10 25
여기서 5를 넣는다고 하면 얘는 10의 왼쪽으로 가야한다.
재귀적으로 볼때 새로운 값, 10이 하나의 서브트리로 완성 되야하고 이 서브트리를 왼쪽 노드, 25, 20 을 원소로 하는 서브트리가 또 완성되어야 한다.
그리고 이 서브트리는 결국 30, 40으로 이루어진 트리가 되어야한다.
그렇기때문에 값을 넣고(return Node) 한 후에 계속 해서 올라가서 결국은 return n을 해줘야한다...
이거는 직접 코드를 손으로 써본다음에 선 그으면서 봐야한다..
3.3 삭제연산
제일 생각할 것도 많고, 코드도 길고.. 그렇다 암튼.
3가지의 경우의 수가 있다.
우선 삭제할 노드를 n 이라 칭하겠다.
첫번째 : n이 자식이 없을 경우
=> n의 부모노드의 자식을 None으로 만든다
두번째 : n의 자식이 하나만 있을경우
=> n의 부모노드와 n의 자식을 직접 연결한다
세번재 : n의 자식이 많을 경우..
=> n의 자시에서 중위순회하면서 n을 방문한 직후 방문하는 노드를 n의 자리로 옮긴다
=> 이진탐색에서 n 기준 왼쪽자식은 n보다 작고 오른쪽 자식은 n보다 크다.
그렇기에 n이 삭제되면 그 다음으로 큰 n의 오른쪽 자식이 와야한다.(n보다 큰 다음 노드가 와야 한다는 뜻)
코드는 다음과 같다.
def delete(self, k):
self.root = self.del_node(self.root, k)
def del_noe(self, n, k):
if n == None:
return None
if n.key > k:
n.left = self.del_node(n.left, k)
elif n.key < k:
n.right = self.del_node(n.right, k)
# 여기까지의 코드는 k를 찾으러 가기 위한 과정이다.
else:
if n.right == None:
return n.left;
if n.left == None:
return n.right;
# 위의 코드는 첫번째 경우, 자식이 없을때
target = n #1번
n = self.minimum(target.right) #2번
n.right = self.del_min(target.right) #3번
n.left = target.left #4번
return n
target부분부터 설명을 하자면.
우리는 자식이 많은 노드를 삭제하는 경우를 생각해야한다.
여기서도 이진 탐색트리의 특성을 꼭 기억해야하는데
왼쪽 자식은 작고 오른쪽 자식은 크다는 것이다.
즉 내가 삭제 되더라도 나를 대체할 애를 뎃구와야하고
뎃구 오는 애는 오른쪽 아이들, 그리고 그 아이들에서도 제일 작은 애를 부모로 해야 정렬이 알아서 된다. 그리고 작은 자식을 뎃구 왔으면 당연히 그 친구를 삭제해주고..
그렇기에 #2번을 보면 지우려는 노드의 오른쪽 자식들 중 가장 작은 애를 고른다.
(minumum이란 함수가 있다.. 위에서 작성 안함...ㅠ)
그리고 그 고른 애들 지워준다(#3번), 이때!! 이러한 결과는 노드의 오른쪽에서 이뤄지므로 n.right로 받아준다!!(#3번)
그리고 왼쪽애들을 그대로 붙여준다(#4번)
다시 정리하자면
1. 삭제 전 오른쪽 자식들 중에서 제일 작은 값 선정
2. 제일 작은 값 삭제
3. 오른쪽, 왼쪽 연결
이렇게 된다..