×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,312,121명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형


이진 탐색 트리(Binary Search Tree)의 정의


1. 각 노드가 최대 두개의 자식을 갖는 탐색 트리이다.


2. 왼쪽 자식은 부모보다 키 값이 작고, 오른쪽 자식은 부모보다 키 값이 크다.



Key값이 8, 3, 10, 1, 6, 14, 4, 7, 13으로 구성되어있다면 위의 정의에 의해 다음과 같이 트리가 구성된다.


이때 Key라는 것은 각 개체에 대한 저장 단위를 의미한다.



이때 3의 왼쪽 서브 트리는 1 오른쪽 서브 트리는 6부터 시작되는 트리를 의미한다.






이진 탐색 트리는 하나만 존재하는 것이 아닌 여러개 존재 할 수도 있다.


예를들면 1,2,3,4로 구성되어 있는것은 1,2,3,4를 섞는 방법 4!가지 즉, 총 24가지 트리로 나타날 수 있다.





따라서 자신이 제작하는 알고리즘에 맞도록 이진 탐색 트리는 조절이 가능하다.

(예를들어 1값이 가장 자주 접근된다면, 첫번째 그림처럼 불균형 한 트리가 유리하지만, 보통 균형 잡힌 트리가 유리하다.)


이진 탐색 트리(Binary Search Tree)의 검색


재귀적인 구현으로 찾아 낼 수 있다.


1. 트리가 비어 있다면 k는 트리에 있을 수 없다.

2. 만약 루트의 값이 원하는 값 k라면, 이 값을 리턴

3. 만약 루트의 값이 k보다 크다면, 이 값은 루트의 왼쪽 서브 트리에 있어야 하며

 만약 루트의 값이 k보다 작다면 이 값은 오른쪽 서브 트리에 있어야 한다.

4. 같은 과정을 계속 반복


 이 그림을 이용해 4를 찾는다면 3->3->2의 과정을 통해 찾아 낼 수 있다.







이진 탐색 트리(Binary Search Tree)의 삭제


삭제할 노드가 무엇인가에 따라서 세 가지 경우가 존재한다.


1. 삭제할 노드가 리프일 때는

  ->그냥 지우면 된다.


2. 노드가 하나의 자식을 가진다

  ->노드를 지우고, 자식을 원래 노드의 위치로 옮긴다.


3. 노드가 두 자식을 가진다.

  -> 노드의 키 값보다 바로 앞에 있거나, 바로 뒤에 있는 노드를 찾는다.

  -> 이 그림에서 3을 삭제한다 가정하면 키 값 바로 앞 값은 1, 바로 뒤 값은 6이다.

  -> 찾은 값을 올린다. 이때 바로 앞 값을 올린다고 가정하면 3자리에 1이 들어간 후, 원래 있던 1을 삭제한다.


  -> 만약 처음 사진에서 바로 뒤 값을 돌린다고 가정하면 3자리에 6이 들어가고 원래 있던 6을 삭제하게되면 4와 7이 남게 된다.

   이때 4와 7은 다시 이진 탐색 트리의 조건에 맞게 설정해 주면 된다. 

   즉, 4는 6의 왼쪽으로 가고 1은 4의 왼쪽 자식으로 가게되고, 7은 6의 오른쪽 자식으로 남게 될 것이다.

반응형