Addition. 2-3 Trees

이미지는 전부 직접 제작한 것입니다. 퍼가실 때에는 반드시 출처를 명시해주세요.

Add1. 2-3 Trees
- 차수가 2 또는 3인 노드를 가지는 트리 (자식이 2 or 3)
  > AVL은 균형 트리를 지향

  > 2-3 트리는 완전 균형 트리를 지향
  > AVL 트리에 비해 상대적으로 단순한 논리

- 2-노드

  > 자식 노드가 2개이고 키가 1개인 노드

  > 이진 탐색트리처럼 하나의 데이터 k1와 두 개의 자식노드를 가짐

  

- 3-노드

         

  > 자식노드가 3개이고 키가 2개인 노드

  > 2개의 데이터 k1, k2와 3개의 자식 노드를 가짐

  > 왼쪽 자식(Left Child), 중간 자식(Middle Child), 오른쪽 자식(Right Child)
  > 키 크기는 12 < 50 < 65 < 90 < 100

   * 왼쪽 서브 트리에 있는 데이터들은 모두 k1보다 작은 값

   * 중간 서브 트리에 있는 값들은 모두 k1보다 크고 k2보다 작음

   * 오른쪽에 있는 데이터는 모두 k2보다 큼

- 2-3 트리 insertion 예

  > 이진 탐색트리와 마찬가지로 리프노드에 삽입

  > 키 39의 삽입

     * 이진 탐색트리라면 40보다 작으므로 40의 L Child 노드를 만들어 삽입

     * 2-3 트리에서 리프는 3-노드일 수 있으므로, 키 39인 레코드와 키 40인 레코드가 합쳐져서 하나의 노드

  > 키 38의 삽입

     * 하나의 노드에 세 개의 키가 들어감. 3- 노드의 키는 두 개까지만 허용.

     * 중간 키 39를 지닌 레코드가 부모 노드로 올라감

     * 작은 키 38과 큰 키 40이 좌우로 분리(Split)            

  > 키 37의 삽입

   > 키 36의 삽입

     * 리프노드에 키 36, 37, 38이 존재. 중간 키 37이 부모노드로 올라가고 나머지는 분리

     * 부모 노드의 키가 30, 37, 39 로 바뀜

     * 중간 키인 37을 그 위 부모노드로 올리고 자신은 키 30인 노드와 39인 노드로 분리
     * 키 39인 노드는 키 37, 50인 부모노드의 중간 자식으로
     * 키 36은 키 30의 오른쪽 자식으로, 키 38은 키 39의 왼쪽 자식으로 들어감

  > 키 35, 34, 33 까지 삽입 후 키 32의 삽입

 

     * 중간 키 33이 부모노드로

     * 부모노드의 중간 키 33이 그 위로

     * 루트 노드의 키가 3개

     * 새로운 루트를 만들어 자신의 중간 키 37을 올림

     * 나머지 키를 분리하여 키 33과 키 50인 노드로 split

- 2-3 트리 deletion 예

  > 왼쪽 또는 오른쪽 자매노드를 살핌

  > 하나라도 3-노드가 있으면 빌려오되, 반드시 부모노드를 거쳐서 빌려옴

  > 키 1, 4로 구성된 왼쪽 자매노드의 키 4인 레코드가 부모 노드로 올라가는 대신 부모노드의
     키 5인 레코드가 삭제된 키 10의 자리로 들어감

  > 키 5의 삭제

    * 왼쪽, 오른쪽 3-노드가 없어 노드 자체가 삭제됨

    * 따라서 자식 노드가 두 개로 줄어들어 부모 노드도 2-노드로 바뀌어야 함

    * 부모 노드의 키 중 하나가 삭제된 노드의 자매 노드로 이동

    * 여기서는 부모 노드의 왼쪽 키가 삭제된 노드의 왼쪽 자매 노드로 이동

    * 물론, 부모노드의 오른쪽 키가 오른쪽 자매로 이동할 수 있음

    * 키 20인 노드를 삭제한 최종 결과

  > 키 40의 삭제

    * 키 80 노드로부터 빌릴 키가 없으므로 키 40인 노드는 삭제
    * 부모 노드인 키 45 노드는 더이상  2-노드 상태를 유지할 수 없어 삭제된 노드의 자매노드인

      키 80 노드로 합쳐짐

  > 키 45의 삭제

    * 키 35인 루트 노드가 2-노드 상태를 유지할 수 없어 왼쪽 자매 노드와 합쳐짐

    * 루트 노드 자체가 삭제되고 트리 높이가 감소 -> 그러나 균형 상태 유지

이미지는 전부 직접 제작한 것입니다. 퍼가실 때에는 반드시 출처를 명시해주세요.