이진 검색 트리

이진 트리란?

트리 자료구조에서 최상위 노드인 root노드부터 다른 노드들 까지 모두 각각이 최대 두개의 자식 노드를 가지는 것이다. 이름이 붙여진것은 나무를 반대로 돌린것과 생긴것이 비슷하다고 하여 붙여졌다.

이진 검색 트리

이진 검색 트리에는 특징이 있다.

• 1.각 노드는 킷값을 하나씩 갖는다. 각 노드의 킷값은 모두 다르다.
• 2.최상위 레벨에 루트 노드가 있고 각 노드는 최대 2개의 자식노드를 갖는다.
• 3.임의 노드의 킷값은 자신의 왼쪽아래에 있는 모든 노드의 킷값보다 크고, 오른쪽 아래에 있는 모든 노드의 킷값보다 작다.

이진 검색 트리의 노드 객체 구조

이진 검색 트리 노드의 필드로는 item, left, right 가 있다.

• item = 노드의 키 값
• right = 노드의 오른쪽 자식노드
• left = 노드의 왼쪽 자식노드
• pageNumberOfRecord = 레코드의 위치에 관한 정보

이진 검색 트리의 알고리즘

• 검색

이진 트리에서 key값이 x 인 노드를 검색하려고 한다.

Copycopy code to clipboard
search(t,x):
  ①if(t = null || t.item - x)
    return t
  ②else if(x < t.item)
    return search(t.left,x)
  ③else:
    return search(t.right,x)

루트 노드인 t와 찾는 값인 x 가 주어진다. 루트노드 t의 key값과 x 를 비교하여 x 가 더 작으면 트리노드의 왼쪽으로 가서 검색을 하고(②), x 가 더 크다면 오른쪽으로 가서 검색을 한다(③). 만일 노드의 key 값이 x 와 같다면 그 값을 return 해준다(①).

위와 같은 검색 알고리즘은 재귀적인 구조를 갖고있다.

• 삽입

원소 x 를 이진 검색 트리에 삽입하려면 우선 이진 검색트리에 x 를 킷값으로 가진 노드가 없어야 한다.

Copycopy code to clipboard
insert(x):
  root <- insertItem(root,x)

insertItem(t,x):
  if(t == null)
    r.item <- x; r.left <- null; r.right <- null
    return r
  else if(x < t.item)
    t.left <- insertItem(t.left,x)
  else
    t.right <- insertItem(t.right,x)

if(t == null) 은 트리에서 x 를 키값으로 가진 노드가 없을때를 말하는 것이다. 만약 노드가 없다면 그 노드를 붙여주면된다.

만약에 현재 노드의 키 값인 보다 삽입할 키값 x 가 크다면 그 노드의 오른쪽으로 보내고 만약 작다면 현재 노드의 왼쪽으로 보낸다.