Binary Search Tree에 대하여

Sorting 알고리즘항목과 마찬가지로 자료구조도 게시물을 올려보겠습니다.

오늘 소개할 자료구조는 Binary Search Tree입니다.

대부분 컴퓨터공학을 전공하신 분이라면 자료구조라는 과목을 통해서 다양한 자료구조를 접해보셨을 겁니다.

저도 공부했었던 부분이지만 요즘 다시 보고있습니다.

그러면서 왜 BST는 등장하게 됐을까요? 왜 사용할까요? 뭐가 좋아서?

구글검색을 통해서 여기저기 정보를 모아보니

먼저 Binary Tree를 도입하게 된 계기부터 알게됐습니다.

2진 트리의 구조는 계층적인 데이터를 표현하기에 적합하여 선형구조를 대신해 채택되었고 이 트리구조에서 탐색을 용이하게 하기 위해 2진 트리의 구조를 변형한 것이 Binary Search Tree입니다.

어떤 값이 트리에 추가될 때 먼저 루트 노드를 기준으로 왼쪽은 작은 값 오른쪽은 큰값으로 구성되고 그 자식노드로 내려가서도 동일한 기준으로 검사하여 추가합니다.

이 그림과 같이 40을 기준으로 왼쪽은 작은 값 오른쪽은 큰 값이 들어옵니다.

여기에서 만약 25가 들어온다면 40보단 작으므로 왼쪽 20보다 크므로 오른쪽 30보단 작으므로 왼쪽에 새로운 노드가 생길 것입니다.

삭제는 몇가지 경우에 따라 생각해봐야 하는데요.

1. 단말(leaf) 노드인가

2. 자식노드가 1개인가

3. 자식노드가 2개인가

1번의 경우는 매우 단순합니다. 해당 값이 있는 노드를 찾아가서 삭제하고 부모 노드가 가지고 있는 포인터 변수를 NULL로 초기화 하면 됩니다.

2번의 경우는 자식 노드가 왼쪽이나 오른쪽에만 치중 되었을 경우 루트노트의 단 하나뿐인 자식노드가 부모노드와 값이나 노드 위치를 바꾸면 됩니다.

3번의 경우는 왼쪽 서브트리의 가장 큰 값을 삭제하려는 노드에 옮겨오거나, 오른쪽 서브트리의 가장 작은 값을 가져옵니다. 그리고 가져온 노드는 삭제하면 완성입니다.

코드는 제 나름대로 Binary Search Tree를 구현했습니다.

ubuntu 15.04에서 C로 구현하였습니다.

2015.11.06. 17:45 추가

코드를 파일로 올렸었는데 git을 시작하면서 git에 올린 내용으로 대체하겠습니다.

git 사용이 아직 헷갈리네요 파일이 필요하신분은 댓글이나 방명록으로 연락주시면 드리겠습니다.