JavaScript로 이진탐색트리 구현하기
이진탐색트리(Binary Tree)
기본개념
개념은 정말 단순하다. 트리는 부모-자식 관의 관계 에 의해서 정의된다고 했다. 이진탐색트리를 살펴보기 전에 먼저 이진트리 부터 이야기 하자면, 일반 트리는 다자녀가 가능한 대신에 이진트리는 자녀를 두명밖에 못 갖는다. 마치 중국에서 불어나는 인구에 대비해서 한 가구당 1자녀를 갖도록 했듯이, 이진트리도 자녀를 두개밖에 못 갖도록 제한을 받게 된 것이다. 이진트리의 부모 노드가 가질 수 있는 자식 노드는 2개이고, 관리의 용이함을 위해서 왼쪽, 오른쪽 자식으로 나눈다.
위의 이진트리에서 아래 두가지 제한사항이 추가된 것이 이진탐색트리다.
- 왼쪽 자식 노드는 항상 부모노드보다 값이 작아야한다.
- 오른쪽 자식 노드는 항상 부모노드보다 값이 커야한다.
다른말로 하면, 트리를 탐색 할 때, 왼쪽은 내려갈수록 작아지고, 오른쪽은 내려갈수록 커진다는 이야기다.
구현
일반 트리를 구현 할 때에는 자식이 얼마나 될지 모르니 자식노드를 담을 배열을 선언해서 주소를 저장했지만, 이진트리는 왼쪽, 오른쪽 두개의 주소를 가리키는 포인터 변수만 있으면 된다.
이진탐색트리의 조건을 만족하기 위해서는 insert 메소드의 구현이 가장 중요하다. 이 때 재귀파티가 열린다. 그나마 재귀 호출이 글 처럼 와닿게 하기 위해서 아래 코드처럼 왼쪽, 오른쪽 기능을 모듈화 해 보았다.
insert(data)메소드가 호출되면, 일단 인자로 받은 data 값이 현재 부모 노드의 값보다 작은지 큰지를 검사한다.- 작다고 가정하고 글을 이어나가면, 값이 작으니까 우리는 넘겨받은 data 를 부모 노드의 왼쪽에다 넣고 싶다. ->
this._toLeft(data)호출, 이 때 넘겨받은 data를 인자로 다시 넘겨주는 것이 중요하다. _toLeft(data)메소드가 하는일은 왼쪽에 이미 자식이 있는지 없는지를 확인해서 넘겨받은 data 들어갈 곳을 찾는 역할을 한다. 즉, 이미 왼쪽에 자식이 들어서 있으면, 자식한테 위임한다. 야! 너가 알아서 이 데이터 처리해줘 :this.left.insert(data), 왼쪽에 자식이 없을 때에는this.left = new Node(data)로 자기 자식으로 품으면 된다.
위의 세번째 과정에서 다시 나의 왼쪽 자식에게 데이터를 넘겨주면서 위임하는 것이 곧 재귀호출이다. 빈 공간을 찾을때까지 insert를 재귀 호출 하는 것이 포인트다.
contains 메소드는 값을 인자로 받아서, 해당하는 트리의 부분 전체를 리턴하는 메소드다. 함수 로직은 위의 insert 를 재귀로 구현한 과정과 똑같고, 다만 값이 같을 때, this 를 리턴하는 것이 포인트다. 주의 할 점은 재귀함수 안에서 return 값이 있는 경우에는 함수를 다시 호출 할 때, 그 앞에 return 을 붙여주어서, 끝나는 조건을 만났을 때, 콜스택을 타고 올라올 수 있도록 연결을 해 주어야 한다.
validate 함수 구현
인자로 node 를 받아서, 넘겨받은 트리가 이진탐색트리가 맞는지 아닌지를 검사 해주는 함수이다.
이 함수가 기능을 제대로 하기 위해서는 다시 한 번 이진탐색트리의 성립조건을 살펴봐야한다.
- 왼쪽 자식 노드는 항상 부모노드보다 값이 작아야한다.
- 오른쪽 자식 노드는 항상 부모노드보다 값이 커야한다.
우리는 위에서 insert 와 contains 메소드를 구현할 때, 재귀로 함수를 호출하면서 밑의 자식에게 일을 위임하는 것을 살펴봤다. 이번에도 같은 재귀의 개념을 사용해보자.
이 때, min: 상한선, max: 하한선 개념을 사용해서 위의 두가지 조건을 항상 만족하는지를 살펴보는 것이 이 함수 구현의 핵심이다.
