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

참조 : C로 배우는 쉬운 자료구조(이지영 저)

공부날짜 : 2021.02.18

 

<Section5> 이진 탐색 트리

 

1. 이진 탐색 트리의 개념

 

 이진 트리를 탐색용 자료구조로 사용하기 위해 원소 크기에 따라 노드 위치를 정의한 것이다. 탐색을 위해서는 찾을 자료를 식별할 수 있는 유일한 값이 필요한데, 이것을 키(key)라고 한다. 

 

 1) 모든 원소는 서로 다른 유일한 키를 갖는다. 

 2) 왼쪽 서브 트리에 있는 원소들의 키는 그 루트의 키보다 작다. 

 3) 오른쪽 서브 트리에 있는 원소들의 키는 그 루트의 키보다 크다. 

 4) 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리이다. 

 

2. 이진 탐색 트리의 탐색 연산

 

 searchBST(bsT , x)

      p ← bsT; //포인터 p

      if (p = NULL) then

         return NULL;

      if (x = p.key) then 

         return p;

      if (x < p.key) then 

         return searchBST(p.left , x);

      else return searchBST(p.right , x);

 end searchBST()

 

3. 이진 탐색 트리의 삽입 연산

 

 insertBST(bsT , x)

     p ← bsT; // 삽입할 자리를 찾기 위한 포인터

     while (p != NULL) do {

          if (x = p.key) then return;

          q ← p; // 삽입할 노드의 부모 노드를 지정하기 위한 포인터

          if (x < p.key) then p ← p.left;

          else p ← p.right;

     } // 삽입할 노드 탐색

 

     new ← getNode();

     new.key ← x;

     new.left ← NULL;

     new.right ← NULL; // 삽입할 노드 생성

 

     if (bsT = NULL) then bsT ←new;

     else if (x < q.key) then q.left ← new;

     else q.right ← new;

     return; // 삽입 노드 연결

 end insertBST()

 

4. 이진 탐색 트리의 삭제 연산

 

 deleteBST(bsT , x)

     p ← 삭제할 노드;

     parent ← 삭제할 노드의 부모 노드;

 

     // 0. 삭제할 노드가 없는 경우

     if (p = NULL) then return;

 

     // 1. 삭제할 노드의 차수가 0인 경우

     if (p.left = NULL and p.right = NULL) then {

         if (parent.left = p) then parent.left ← NULL;

         else parent.right ← NULL;

     }

 

     // 2. 삭제할 노드의 차수가 1인 경우

     else if (p.left = NULL or p.right = NULL) then {

         if (p.left != NULL) then {

             if (parent.left = p) then parent.left ← p.left;

             else parent.right ← p.left;

         }

         else {

             if (parent.left = p) then parent.left ← p.right;

             else parent.right ← p.right;

         } 

     }

     // 3. 삭제할 노드의 차수가 2인 경우

     else if (p.left != NULL and p.right != NULL) then {

         q ← maxNode(p.left); // 왼쪽 서브트리에서 후계자 노드를 포인터 q로 지정

         p.key ← q.key;

         deleteBST(p.left , p.key); //후계자 노드 자리에 대한 2차 재구성

     }

 end deleteBST()