자료구조 - 이진탐색트리(BST) 그림으로 쉽게 이해하기

자료구조 - 이진탐색트리(BST) 그림으로 쉽게 이해하기

 

안녕하세요.

로스윗의 코딩캠프입니다.

오늘은 많은 사람들이 궁금해하시고 많이들 헷갈려하시는 내용을 바탕으로

자료구조 - 이진탐색트리(BST) 그림으로 쉽게 이해하기에 대해서 같이 알아보겠습니다.

그림으로 쉽게 이해할 수 있으니 끝까지 잘 따라와주세요 :)

바로 시작하겠습니다.

 

 

- 이진탐색트리 (Binary Search Tree) 시간복잡도

우선 트리구조는 그 자체만으로는 데이터 값에 대한 어떠한 제약도 없습니다.
그럼 이 상황에서 어떤 특정한 값을 찾기 위해서는 결국 트리의 모든 데이터를 탐색을 해야하는 상황이 발생합니다.
그러면 데이터 N개 만큼 탐색이 이루어져야 하기 때문에 시간 복잡도에 있어서 별다른 이점이 없게 됩니다.
이진탐색트리는 데이터의 특성에 제약을 줌으로써 탐색 속도를 이진탐색처럼 O(logN)으로 줄여주는 특징이 있습니다.

 

 

- 이진트리와 이진탐색트리의 같은점 다른점

이진탐색트리는 기본적으로 왼쪽 자식노드와 오른쪽 자식노드를 가질수 있다는 점에서 이진트리와 같은 구조입니다.
그러나 일반적인 이진트리와의 차이는 데이터 값에 제약이 생긴다는 것인데, 이진탐색트리에서 루트노드를 기준으로 왼쪽서브트리는 루트노드보다 작은값들로만 이루어져있고, 오른쪽 서브트리는 루트노드보다 큰 값들로만 이루어져 있어야 합니다. 이것이 이 둘의 차이입니다. 그리고 각각 왼쪽 서브트리와 오른쪽 서브트리 모두 이진 탐색트리를 구성하고 있을때 이 트리를 이진탐색트리(BST)라고 합니다.

 

 

이진탐색트리 예시

 

 

- 이진탐색트리 설명 예시

예를들면 위 그림처럼 트리의 루트에 데이터값 5가 들어 있을 때, 왼쪽 서브트리 전체에는 5보다 작은 값들만 들어있게 되고, 오른쪽 서브트리 전체에는 5보다 큰 값들만 들어있게 됩니다. 그리고 각각 왼쪽 서브트리와 오른쪽 서브트리를 봤을 때도 왼쪽 서브트리의 루트노드인 3을 기준으로 왼쪽은 자식노드를 포함해서 3보다 작은 데이터 값들만 들어있고, 오른쪽은 3보다 큰 값이 위치해 있어야 합니다.

 

오른쪽 서브트리도 서브트리의 루트노드인 7을 기준으로 왼쪽은 7보다 작은 값들이, 오른쪽은 7보다 큰 값들이 서브트리를 이루고 있어야 합니다. 이런식으로 계속해서 하위에 서브트리를 타고 들어가더라도 이진탐색트리의 특성이 유지되어야 합니다. 여기서 한 노드라도 이런 특성이 유지되지 않는다면 이진탐색트리라고 할 수 없습니다.

 

 

이진탐색트리 예시

 

- 이진탐색트리의 특징

이런 이진 탐색트리의 특징으로 봤을 때 이진탐색트리의 최소값은 트리의 레벨에 관계없이 트리의 가장 왼쪽 끝에 위치한 노드가 됩니다. 그림 상에서는 가장 왼쪽에 위치한 1이 실제로 이 BST에서 가장 작은 데이터값인 것을 볼 수 있습니다. 만약 1이 들어있는 노드에 왼쪽 자식이 있게 된다면 그 노드에 있는 값이 트리의 가장 최소값이면서 동시에 이진탐색트리에서 가장 왼쪽에 있는 값이겠죠.

 

 

이진탐색트리의 최소값은 트리의 레벨에 관계없이 트리의 가장 왼쪽 끝에 위치한 노드

 

반대로 최대값도 트리의 레벨에 관계없이 트리의 가장 오른쪽 끝에있는 노드가 가장 큰 값을 가지고 있게 됩니다. 이 그림에서는 가장 오른쪽에 위치한 9가 실제로 이 BST에서 가장 큰 값인 것을 볼 수 있습니다.

 

 

최대값도 트리의 레벨에 관계없이 트리의 가장 오른쪽 끝에있는 노드이다

 

그래서 이진탐색트리는 루트 데이터의 값이 항상 왼쪽 데이터 보다는 크고 오른쪽 데이터 보다는 작기 때문에, 왼쪽 - 루트 - 오른쪽 순서로 방문하는 중위탐색 즉, inorder 탐색으로 하게 될 경우 모든 데이터값을 정렬된 순서로 가져 올 수 있다는 특징이 있습니다.

 

 

이진탐색트리를 중위탐색할 경우 데이터 값이 정렬된 순서로 방문하게 된다

 

반응형

 

- 이진탐색트리의 데이터 삽입

이진탐색트리의 데이터 삽입 과정은 어떻게 이루어질까요?
기본적으로 이진탐색트리는 중복된 데이터는 삽입하지 않고 데이터의 삽입이나 삭제가 이뤄져도 그 특성이 유지되어야 합니다. 그래서 데이터가 삽입 될 때는 자신이 들어가야 할 위치부터 찾아야 하는데, 이진탐색트리에서 중복 데이터는 없기 때문에 위치를 찾는 과정에서 자신과 동일한 값의 데이터가 있다면 데이터를 삽입하지 않고 그대로 종료를 하게 됩니다. 그리고 최종적으로 추가된 노드는 트리의 leaf노드에 위치해야 하고 루트부터 값 비교를 하면서 트리를 타고 들어가야 합니다.

 

 

이진탐색트리 예시

예를들어 위 그림과 같은 트리에서 1이라는 데이터를 삽입한다고 가정해봅시다. 처음 만나는 루트값인 8과 비교연산을 하게 되고 8보다 값이 작기 때문에 왼쪽 서브트리로 이동하게 됩니다. 여기서 8의 왼쪽 자식노드인 5를 만나 다시 비교 연산을 하게 되고 역시 5보다 작기 때문에 다시 왼쪽 서브트리로 이동하게 됩니다. 여기서 5의 왼쪽 자식노드인 2를 만나 다시 비교 연산을 하게 되고 역시 2보다 작기 때문에 역시 왼쪽 서브트리로 이동하게 됩니다. 그런데 여기서 더이상 타고 들어 갈 왼쪽 자식 노드가 없기 때문에 비교 연산을 하지 못하고 2의 왼쪽 자식노드로 추가가 되면서 삽입연산이 종료가 됩니다. 최종적으로 이런 모양이 나오겠죠.

 

 

이진탐색트리에 1의 데이터를추가한 모습

 

 

- 이진탐색트리의 데이터 삭제

삽입은 이렇게 위치만 잘 찾아서 leaf노드에 추가 해주면 되는데 삭제는 조금 더 복잡합니다. 삭제를 할때는 트리의 leaf노드만 삭제 되는게 아니라 중간에 위치한 노드가 삭제 될 수도 있기 때문이죠. 그래서 삭제 연산을 할 때는 먼저 삭제할 데이터가 있는 노드의 위치를 찾은 다음에 1)삭제 할 데이터가 leaf노드에 있는 경우, 2)한 개의 자식 노드를 가진 경우, 3)두개의 자식 노드를 가진 경우에 대해서 모두 생각해 봐야합니다.

 

 

이진탐색트리 예시

 

 

1) 삭제 할 데이터가 leaf(리프)노드에 있는 경우

우선 첫번째로 삭제할 노드라 leaf노드인 경우를 보겠습니다. 위 그림 상에서는 2나 8이 될 수 있겠죠. 이때는 null을 부모노드에게 리턴시켜서 자신에게 가리키던 자식포인트를 null로 가리키게 해줍니다. 그래서 2를 지우게 되면 부모노드였던 1은 오른쪽 자식노드로 null값을 가지게 되고, 8을 지우면 부모노드였던 9는 왼쪽 자식노드로 null값을 가지게 되면서 데이터를 삭제 할 수 있습니다.

 

 

null을 부모노드에게 리턴시켜서 자신에게 가리키던 자식포인트를 null로 가리키게 해준다

 

 

2) 삭제할 데이터가 한 개의 자식 노드를 가진 경우

다음으로 한 개의 자식노드를 갖는 데이터를 삭제할 경우입니다. 이때는 하나있는 자식노드를 부모노드로 보내주면 됩니다.
여기서 1이 들어있는 노드를 기준으로 1의 자식노드인 2를 1의 부모노드 였던 3의 자식으로 연결시켜주면 됩니다. 그럼 이진탐색트리의 속성이 유지되면서 데이터를 삭제할 수 있습니다. 자식노드가 왼쪽에 있던 오른쪽에 있던 상관없이 동일하게 적용됩니다. 데이터 9기 들어있는 노드를 삭제할 때는 데이터의 왼쪽 자식을 자신의 부모였던 노드7의 자식으로 만들어주면 됩니다. 그럼 데이터를 삭제해도 이진탐색트리의 속성은 계속 유지됩니다.

 

 

1의 자식노드였던 2를 1의 부모노드 였던 3의 자식으로 연결시켜준 모습

 

 

3) 삭제하 데이터가 두개의 자식 노드를 가진 경우

마지막으로 두개 자식노드를 가지고 있는 데이터를 삭제 할 경우입니다. 이때는 두가지 방법이 있습니다. 첫번째는 노드의 왼쪽 서브트리의 최대값이 삭제할 노드의 위치에 오게 하는 것이고, 두번째는 노드의 오른쪽 서브트리의 최소값을 삭제할 노드의 위치에 오게 하는 것입니다. 데이터가 삭제될 노드의 위치에는 왼쪽 서브트리의 노드보다는 큰 값이 있어야 되고 오른쪽 서브트리의 값보다는 작은 값이 루트에 위치해 있어야 하기 때문에 두 방법 중 하나를 선택하게 됩니다. 둘 중 어느 방법이든 상관없지만 오른쪽 서브트리의 최소값을 가져오는 경우로 보도록 하겠습니다.

 

 

2개의 자식을 가지고 있는 7노드를 삭제해보자

 

삭제할 노드가 7일 때 노드 7의 오른쪽 서브트리에서 최소값은 8이기 때문에 8을 데이터가 삭제될 노드의 위치로 가져옵니다. 그럼 노드7 대신에 8이 들어오면서 그림과 같은 트리의 모양이 그려집니다.

 

 

노드7 대신에 8이 들어온 모습

여기서 멈추면 데이터 값 8이 두번 중복되기 때문에 삭제할 데이터가 있던 노드의 위치를 기준으로 오른쪽 서브트리의 방금 가져온 데이터 8이 위치한 노드를 삭제해줘야 합니다. 그러면 최종적으로 데이터 중복을 피하면서 이진탐색트리를 유지할 수 있게 됩니다. 

 

 

중복된 8의 값을 삭제시킨 모습

 

오늘은 이렇게 자료구조 - 이진탐색트리(BST) 그림으로 쉽게 이해하기에 대해서 알아보았습니다.

다음 포스팅도 더 쉽고 재밌는 포스팅으로 다시 돌아오겠습니다.

감사합니다.