이진 검색 트리 (Binary Search Tree)

📚 정의

이진 탐색 트리는 이진 트리이지만, 좀 더 세부적인 정의를 갖는다.

• 모든 노드는 서로 다른 값을 같는다.
• 루트 노드의 왼쪽 서브 트리에 포함된 모든 값들은 루트 값보다 항상 작다.
• 루트 노드의 오른쪽 서브 트리에 포함된 모든 값들은 루트 값보다 항상 크다.
• 왼쪽, 오른쪽 서브 트리는 각각 루트 노드를 갖는 또 다른 이진 탐색 트리 구조여야 한다.
  
  
  

📚 연산

노드 클래스

static class Node {
	int value;
	Node left, right;
		
	public Node(int value) {
		this.value = value;
		this.left = null;
		this.right = null;
	}
}

삽입

private static void insertNode(int element) {
   if(root == null) { // 트리가 없다면 루트 노드로 설정한다.
      root = new Node(element);
   } else {
      Node head = root;
      Node cur;
		
      while(true) {
         cur = head;
				
         if(head.value > element) { // 넣으려는 값이 현재 노드 값보다 작으면 왼쪽으로 탐색한다.
            head = head.left;
              
            if(head == null) { // 왼쪽 자식 노드가 비어있으면 해당 위치에 값을 삽입한다.
               cur.left = new Node(element);
               break;
            }
         } else { // 넣으려는 값이 현재 노드 값보다 크면 오른쪽으로 탐색한다.
            head = head.right;
              
            if(head == null) { // 오른쪽 자식 노드가 비어있으면 해당 위치에 값을 삽입한다.
               cur.right = new Node(element);
               break;
            }
         }
      }
   }
}

[참고]

• 오늘도 MadPlay! - 이진 탐색 트리: 자바 언어로 구현하기