이진탐색트리

이진탐색트리(Binary Search Tree)

• 모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들만 가진다.
• BST 의 최소값은 트리의 가장 왼쪽에 존재 3/ 최대값은 가장 오른쪽에 존재 50

BST를 순회하는 방법

• 출발은 항상 루트노드를 기준으로 시작20

* 순회 : TST의 모든것들을 한번씩 방문하는것을 말한다.

preorder traversal(전위 순회)

현재 노드 방문 (값 출력)
재귀적으로 왼쪽 서브 트리 순회
재귀적으로 오른쪽 서브 트리 순회

- BST 에 대한 순회가 끝! 20, 5, 3, 15, 10, 17, 50, 30, 40

코드로 표현

preorder(tree) {
 방문(tree.root);
 preorder(tree.left);
 preorder(tree.right);
}

inorder traversal(중위 순회)

• 바이너리 서치 트리에 대한 값들을 순서대로 방문하는 특징이 있다.

재귀적으로 왼쪽 서브 트리 순회
현재 노드 방문(값 출력)
재귀적으로 오른쪽 서브 트리 순회

- 5지나 3 3 값 출력 현재 노드 방문 5 5값 출력 > 15 지나 10 10 값 출력 > 현재 노드 방문 15 15값 출력 > 17 17값 출력 > 현재 노드 방문 20 20값 출력 > 50지나 30 30값 출력 > 4040값 출력 > 현재노드 방문 50 50값 출력
BST 에 대한 순회가 끝! 3, 5, 10, 15, 17, 20, 30, 40, 50

코드로 표현

inorder(tree) { 
 inorder(tree.left);
 방문(tree.root);
 inorder(tree.right);
}

postorder traversal(후위 순회)

재귀적으로 왼쪽 서브 트리 순회
재귀적으로 오른쪽 서브 트리 순회
현재 노드 방문 (값 출력)

- BST 에 대한 순회가 끝! 3, 10, 17, 15, 5, 40, 30, 50, 20

코드로 표현

postorder(tree) { 
 postorder(tree.left);
 postorder(tree.right);
 방문(tree.root);
}

노드의 successor(후임자)

• 해당 노드보다 값이 큰 노드들 중에서 가장 값이 작은 노드

  에
  20의 successor : 30
  17의 successor : 20
  10의 successor : 15

노드의 predecessor(선임자)

• 해당 노드보다 값이 작은 노드들 중에서 가장 값이 큰 노드

  예
  20의 predecessor : 17
  10의 predecessor : 5
  40의 predecessor : 30