[자료구조] 이원탐색트리(이진탐색트리)

이원탐색트리(이진탐색트리 : Binary Search Tree : BST)

  : 이진 트리로서 공백이 아니면,

다음 성질을 만족한다.

 

 

 

 

 

 

 

이진 탐색 트리의 정의

(1) 모든 원소는 상이한 키를 갖는다.  (2) 왼쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 작다.  (3) 오른쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 크다.  (4) 왼쪽 서브트리와 오른쪽 서브트리도 모두 이원 탐색 트리이다.

 

 

알고리즘. 이진 탐색 트리에서의 순환 탐색

searchBST(B, x)          // B는 이진 탐색 트리          // x는 탐색할 키 값      p <- B;      if ( p = null ) then return null; // 공백 이진 트리로 탐색 실패      if ( p.key = x ) then return p; // 탐색 성공      if ( p.key < x ) then return searchBST(p.right, x); // 오른쪽 서브트리 탐색      else return searchBST(p.left, x);                        // 왼쪽 서브트리 탐색  end searchBST()

 

 

 

 

 

 

 

이진 탐색 트리의 삽입

키 값이 x인 원소를 삽입하기 위해선 트리에 x를 키값으로 하는 원소가 있는지를 확인한다.

이를 위해서 탐색 키 값을 x로 하여 탐색을 수행하고, x를 가진 원소가 있어야 될곳에 없다면

(없어서 탐색이 안된다면) x를 키 값으로 가진 원소가 없는 것이므로 "탐색이 종료된 지점"에

원소를 삽입하면 된다.

 

알고리즘. 이진 탐색 트리에서의 원소 삽입

insertBST(B, x)        // B는 이진 탐색 트리, x는 삽입할 원소의 키 값      p <- B;      while ( p ≠ null ) do { // 삽입하려는 키 값을 가진 노드가 이미 있는지 검사             if ( x = p.key ) then return;             q <- p; // q는 p의 부모 노드를 지시             if ( x < p.key ) then p <- q.left;             else p <- p.right;      }      newNode <- getNode(); // 삽입할 노드를 만듦      newNode.key <- x;      newNode.right <- null;      newNode.left <- null;      if ( B = null ) then B <- newNode; // 공백이원트리인 경우 root가 newNode가 됨      else if ( x < q.key ) then q.left <- newNode; // q는 탐색이 실패로 종료하게 된 원소      else q.right <- newNode;      return;  end insertBST()

 

 

 

 

 

 

 

이진 탐색 트리의 삭제

(1) 자식이 없는 리프(단말) 노드의 삭제

  삭제해야 될 노드가 자식이 없는 단말 노드의 경우에는 부모 노드의 해당 링크 필드를 널(null)로

  만들고 삭제한 노드를 반환하면 된다.

(2) 자식이 하나인 노드의 삭제

  삭제할 노드가 하나의 자식만을 가진 노드인 경우에는 삭제되는 노드의 자리에 하나뿐인 그 자식

  노드를 위치시키면 된다.

(3) 자식이 둘인 노드의 삭제

  삭제할 노드가 두 자식을 가진 경우에는 먼저 삭제되는 그 노드의 자리에

  그의 왼쪽 서브트리에서 제일 큰 원소로 대체할 것인지 또는

  그의 오른쪽 서브트리에서 제일 작은 원소로 대체할 것인지 선택한다.

  그 다음 해당 서브트리에서 이 대체 원소를 삭제하면 된다.

 

알고리즘. 이진 탐색 트리에서의 원소 삭제

deleteBST(B, x)      p <- node to be deleted;    // 주어진 키 값 x를 가진 노드      parent <- parent node of p // 삭제할 노드의 부모 노드      if ( p = null ) then return ;      case {            p.left = null and p.right = null : // 삭제할 노드가 단말(리프) 노드인 경우                  if ( parent.left = p ) then parent.left <- null;                  else parent.right <- null;            p.left = null or p.right = null; :   // 삭제할 노드의 차수가 1인 경우                  if ( p.left ≠ null ) then {                         if ( parent.left = p ) then parentl.left <- p.left;                         else parent.right <- p.left;                  }                  else {                          if ( parent.left = p ) then parent.left <- p.right;                          else parent.right <- p.right;                  }            p.left ≠ null and p.right ≠ null; :   // 삭제할 노드의 차수가 2인 경우                            q <- maxNode(p.left);            // 왼쪽 서브트리에서 최대 키 값을 탐색                  p.key <- q.key;                  deleteBST(p.left, p.key);      }  end deleteBST()