[자료구조] 11강 - BST, Splay, AVL, BB

✅ 1. 이진 탐색 트리

(1) 이진 탐색 트리(BST) - 개념

• 특정 데이터의 효과적인 검색을 위해 제한점을 가지는 이진 트리이다.
• 특정 데이터의 검색과 노드의 삽입, 삭제 처리에 효과적인 이진 트리이다.
• BST: 트리를 구성할 때, 데이터의 탐색을 고려하여 구성(설계)하므로 탐색에 최적화된 이진 트리이다.
• 키: 탐색, 삽입, 삭제 연산에서 비교의 대상이 되는 값이다.
• ( 즉, 이진 트리 노드의 데이터를 대표하는 값, 혹은 노드를 특정할 수 있는 값 ex.주민등록번호 등 )

(2) 이진 탐색 트리(BST) - 제한점 또는 특징

• 모든 노드의 왼쪽 서브 트리에는 해당 노드보다 작은 값 오른쪽 서브 트리에는 큰 값이 들어가는 제한점을 가짐.

(3) 이진 탐색 트리(BST) - 중위순회

• 이진 탐색 트리에서 중위 순회를 하면 정렬된 순서의 데이터를 얻을 수 있어서 효율적임.
• 쉽게말해, 이진 탐색 트리의 왼쪽 서브트리 = 작은 값, 오른쪽 서브트리 = 큰 값의 경우 중위순회를 돌리면 왼쪽 서브 트리를 먼저 수행한 뒤 루트를 수행하고 오른쪽 서브 트리를 수행하게 되는데, 이것이 결국 작은값 -> 중간값 -> 큰 값 순으로 정렬이 된 상태로 출력이 되기 때문이다.

(4) 이진 탐색 트리(BST) - 순회 연산

[ BST - 노드 정의 ]

• 위의 key 값은 unique한 데이터가 들어가며, 데이터 필드는 데이터를 넣는 필드임.

[ BST - 중위 순회 연산 ]

• (1) root 부터 left 가 null 일 때 까지 left 의 잎 노드로 내려감.
• (2) left 의 잎 노드가 null 인 경우 재귀로 돌아와 printf() 를 통해 "1" 이 수행 됨.
• (3) 이후, right 노드로 내려갔는데, null 인 경우 이전 재귀인 "2" 로 돌아가는 구조이다.
• (4) 이러한 과정이 반복되면 1 -> 2 -> 3 -> 5 -> 4 -> 6 -> 7 -> 8 -> 9 의 수행 순서가 될 것임.

(5) 이진 탐색 트리(BST) - 탐색 연산 ( 특정 값 찾기 )

• (1) searchBST(): 형식 매개변수로 root , key (내가 찾고자 하는 키) 를 같이 넘김.
• (2) if(root == NULL): root 가 만약 null 인 경우에는 아무 값도 존재하지 않으므로, 예외처리
• (3) if(key == root -> key): root(현재위치) 와 key 같이 동일한 경우 내가 찾고자 하는 값이므로 바로 리턴을 해주면 됨.
• (4) else if(key < root -> key): 찾고자 하는 값이 아닐 경우, key 값과 root(현재 위치) 값과 비교를 하고 만약 내가 찾고자 하는 값이 더 작다면, searchBST() 함수를 재귀 호출 후 매개변수로 left 노드 포인터와 key 값을 같이넘김.
• (5) else if(key > root -> key): 만약 찾고자 하는 값이 아닐 경우, key 값과 root(현재 위치) 값과 비교 후 찾고자 하는 값이 더 크다면, 이번엔 right 포인터와 key 값을 재귀함수로 넘김.
• 핵심은 해당 과정이 반복이 되면, 큰 수 작은 수 비교를 통해 원하는 값을 찾을 때 까지 내려갈 수 있음.

(6) 이진 탐색 트리(BST) - 삽입 연산

• (1) insertBST(BSTnode* root, char key): root 와 내가 삽입하고자 하는 key 를 넣어주면 됨.
• (2) BSTnode* newNode = (BSTnode*)malloc(sizeof(BSTnode)): BSTnode(실제 이진 탐색 트리의 rootNode) 와 동일한 구조를 띄는 구조체를 새롭게 만들어서 newNode에 할당하는 작업임. 이렇게 하는 이유는, 동일한 구조를 가진 해당 노드에 내가 찾는 key 를 넣게 되며, 해당 newNode 는 삽입 및 비교 대상으로 실제 이진 탐색 트리와 비교 후 삽입이 될 예정임.
• (3) newNode -> key = key, newNode -> left = newNode -> right = NULL: 새로운 비교 및 삽입 노드를 만들기 위함.
• (4) if(root == NULL): 만약 root 가 NULL인 경우 root 에는 새로운 newNode 를 넣으면 끝임. ( 어차피 삽입 될 노드기 때문 )
• (5) ptr = root: BSTnode* ptr; 에 root 를 넣어서 해당 함수 내부에서는 ptr(실제 이진 탐색 트리)와 newNode가 비교가됨.
• (6) while(ptr): ptr(실제 이진 탐색 트리 위치) 이 NULL 이 아닐 때까지(즉, 유효한 노드를 가리킬 때까지) 반복문 수행
• (7) if(key == ptr -> key): 삽입할 키가 현재 노드의 키와 같으면, BST에서 중복된 키는 허용되지 않으므로 오류 메시지를 출력하고, 삽입을 취소하고 현재 루트를 반환한다.( 동일한 키값이 존재하면 삽입하는데 의미가 없으니까 중복허용을 안함. )
• (8) else if(key < ptr -> key): newNode의 key 즉, 찾고자 하는 키가 현재 노드의 키보다 작으면, BST 규칙에 따라 왼쪽 서브트리로 이동을 시킴.
• (9) if(ptr -> left == NULL): 만약 ptr 의 left 가 NULL 인 경우 해당 위치에 newNode 를 삽입하고 return 반복 종료
• (10) else { ptr = ptr -> left }: 아닐 경우 ptr 의 left 로 이동
• (11) else: 8 번의 else if 즉, newNode key 가 현재 key 보다 작지 않은 경우에는, 큰 경우니까 ptr 의 right 가 NULL 인지 확인 하고, NULL 이면 해당 right 에 newNode 를 넣어주고, NULL 이 아니면 ptr 의 right 로 이동을 시킴.

• 핵심: 결과적으로 이진 탐색 트리의 root 노드를 복사해서 새로운 노드를 만드는데, 이 노드는 삽입할 대상의 노드가 되고, 이후 반복 작업을 통해 이진 탐색 트리의 root 노드와 비교(크고 작고)하면서 자리를 찾아가는 과정임.

(7) 이진 탐색 트리(BST) - 삭제 연산

• 이진 탐색 트리 구조에서 특정 노드를 삭제하는 연산에 관한 내용임.
• (1) 삭제 될 key 를 받아서 root 부터 아래로 이진 탐색의 규칙에 맞게 탐색을 하게 됨.
• (2) 삭제 될 key 와 동일한 key 를 만나게 되면 해당 노드를 부모 노드로 부터 끊어주게 되면 삭제가 된 상태가 됨.
• (3) 이후, 삭제 된 노드의 위치가 leafNode 인 경우 더 이상의 연산은 없음.
• (4) 하지만, leftNode 가 아닌 경우에는 삭제되는 노드의 자식 노드가 존재하는 경우이며, 이때는 자식 노드가 1개인 경우와 2개인 경우가 있다. 만약 1개인 경우에는 단순히 삭제 후 삭제 된 노드의 부모와 자식을 연결하면 끝나지만, 2개인 경우는 자식 노드의 값을 기준을 정해서 해당 삭제되는 노드에 채워줘야 한다.
• (5) 해당 기준은 삭제 된 노드를 기준으로 오른쪽 서브트리, 왼쪽 서브트리 두 가지의 기준이 있음.
• 왼쪽 서브트리 기준: 삭제 된 노드 위치로 왼쪽 서브트리에서 가장 큰 값을 올리는 방법
• 오른쪽 서브트리 기준: 삭제 된 노드 위치로  오른쪽 서브트리에서 가장 작은 값을 올리는 방법
• 이러한 기준은 자료구조를 구현 할 때 정하는 부분으로 볼 수 있음.

[ 이진 탐색 트리 - 삭제 연산 ( 실제 구현 ) ]

• (1) 자식 노드가 0개인 경우: 삭제되는 노드의 자식 노드가 0개인 경우에는 잎 노드 이므로, 조건문을 보면 삭제 되는 노드의 자식 노드들이 NULL 인 경우 해당 부모 노드로 부터 연결을 끊게 됨. ( 매우 간단함 )
• (2) 자식 노드가 2개인 경우: 오른쪽 서브트리 기준으로 하면, 가장 작은 값을 삭제되는 노드로 올리면 끝나고 왼쪽 서브트리를 기준으로 하면 가장 큰 값을 삭제되는 노드로 올려주면 해결이 된다. 이후, 노드가 올라가게 되면 그 자리는 비어진 자리가 되므로 올라간 기존 노드의 부모 노드와 자식 노드간의 연결을 해주면 된다.
• (3) 자식 노드가 1개인 경우: 삭제하려는 노드를 삭제한 뒤 삭제 된 노드의 기존 자식 노드와 부모 노드간의 연결을 하면 됨.

---

✅ 2. 변형 BST - Splay, AVL, BB

• Splay, VAL, BB 트리는 이진 탐색 트리의 기본 구조를 따르지만, 성능을 위해 각자 다른 방식으로 자기 균형을 만드는 변형들이다. 즉, 이진 탐색 트리(BST) 의 탐색/삽입/삭제 등 성능을 올리기 위해 만들어진것임.
• 자세하게는, BST는 입력되는 순서에 따라 구조가 랜덤하게 만들어지고, 운 나쁘면 탐색이 오래 걸리는 구조가 된다. 이를 막기 위해 AVL, RB, Splay 같은 균형 트리들은 ‘구조가 나빠지지 않도록 강제로 조정하는 확정 트리'다.
• 즉, BST 의 균형이 잘 맞는다는건, 트리 내부의 노드들이 탐색에 유리하게 위치해 있다는 의미로 해석.

(1) Splay 트리

• 자주 탐색하는 키를 가진 노드를 루트에 위치하도록 구성한 BS 트리 ( 자주 탐색하는 키를 위로 올리는 느낌임. )
• 즉, 최근에 접근한 노드를 루트로 가져오는 자료구조이다.
• 또한, 검색, 삽입, 삭제 후 해당 노드를 루트로 Splay 연산을 수행하여 트리를 재정렬함.
• Splay 연산: 최근에 접근한 노드는 다시 사용할 가능성이 높다고 예상하여 루트로 올려주는 연산을 의미하며, 이러한 과정을 Splay 연산이라고 한다.
• Splay 트리: Splay 연산을 반복하고 적용하여 재구성되어 생성된 이진 트리를 의미한다.

(2) Splay 트리 - 연산

• Splay 트리 연산은 최근에 접근한 노드는 다시 사용할 가능성이 높다고 예상하여 루트로 올려주는 연산을 의미함.
• Splay 연산의 3가지 패턴: Zig , Zig-Zig , Zig-Zag 세 가지 패턴이 존재함.
• 이러한 연산 모두 기본으로 최근 접근한 노드를 루트까지 올리기 위해 반복적으로 회전하며 트리를 재구성하는 과정을 진행함.
• 최근에 접근한 노드 기준: 검색(찾으려는 값의 노드), 삽입(새로 넣는 노드), 삭제(삭제하려는 노드) 와 같은 작업을 수행한 노드가 바로 "최근에 접근한 노드" 가 되는 것이다.
• ***즉, 검색 / 삽입 / 삭제 이후 바로 Splay 연산 을 통해 재구성을 하는 트리라고 보면 될 듯.***
• ***결론은 검색 / 삽입 / 삭제 연산 후 Zig, Zig-Zig, Zig-Zag 연산 패턴을 골라서 활용하는 느낌으로 이해하면 될듯.***
• 회전이란? - 단순히 노드 위치를 바꾸는 작업으로, BST 성질 유지 + 루트로 올리는 목적을 가짐.

[ Zig 패턴(연산) ]

• Splay Tree 에서 최근 접근한 노드의 부모가 루트일 때 수행되는 단일 회전을 하는 연산을 의미한다.
• 쉽게말해, 최근 접근한 노드를 x라고 하면, x 노드를 루트 노드로 바로 올려버리는 연산이다.
• 이후, 나머지 노드들 또한, 재구성이 될 수 있음.
• 또한, Zig 패턴은 Splay 연산의 가장 간단한 경우라고 보면 된다.
• 최종적으로 최근 접근한 노드 x가 루트가 되도록 하는 회전 단계 중 하나로 볼 수 있다.

[ Zig-Zig 패턴(연산) ]

• 최근 접근한 노드의 부모 노드를 먼저 루트로 올리고 자기가 루트로 올라가는 연산이다. ( 두개의 단일 회전 )
• 위의 이미지에서 (1), (2), (3), (4) 삼각형은 서브트리들을 의미한다. 즉, 많은 트리가 존재한다고 해도 위와같이 적은 노드만 옮겨서 구조를 재구성 할 수 있기 때문에 오버헤드가 크지 않다는 장점이 있음.

[ Zig-Zag 패턴(연산) ]

• 최근 접근한 노드를 x로 볼 때 x 노드를 하나씩 루트노드로 올리는 과정으로 볼 수 있음.

(3) Splay 트리 - 연산 예제

• 왼쪽 트리에 대해 7이 루트가 되도록 Splay 연산을 적용한 예제임.

(4) Splay 트리 - 정리

• 최근 사용 데이터를 루트로 올리는 재구성을 통해 최근 사용 데이터 최적화를 진행함.
• 즉, Splay 트리의 핵심은 재구성을 통한 정렬로 볼 수 있음.

(5) AVL 트리

• 일반적으로 BST는 단순히 이진 트리의 규칙과 왼쪽 < 현재 < 오른쪽 규칙만 따르고 있기 때문에, 데이터 삽입 순서에 따라 트리가 한쪽으로 치우칠 수 있음. 즉, 편향 트리가 될 가능성이 있다는 의미임.
• 즉, 이러한 편향 트리 구조가 만들어지는 것을 방지하기 위해 나온것이 AVL 트리이다.
• BST 를 유지하면서 균형을 맞추려면 오버헤드가 너무 커질 수 있기 때문에 높이 균형 트리를 만들자는 개념으로 AVL 트리가 등장 한 것으로도 봄. ( 높이차이는 1차이 정도로 봄 )

(6) AVL 트리 - 특징

• AVL 트리의 특징: 트리의 모든 노드들은 BF(x) = { -1, 0, 1 } 와 같은 특징을 가짐.
• BF(balance factor): 임의의 노드 x의 왼쪽과 오른쪽 서브트리의 높이 차이를 해당 노드 x의 balance factor 라함.
• BF(x) = { -1, 0, 1 }: 모든 노드가 -1 , 0 , 1 밸런스 팩터를 가지는 이진 탐색 트리(BST) 를 의미함.
• 즉, 모든 노드가 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이 를 진행 했을 때 결과값으로 -1, 0, 1 을 얻어야 밸런스(균형)이 맞다고 판단을 하고, 만약 해당 수에 포함이 되지 않을 경우에는 위치 조정이 필요한 상황으로 판단해 위치를 조정하게 됨.
• 트리의 높이: 루트 노드로 부터 잎 노드까지의 차수를 높이로 볼 수 있음. 즉, 노드가 3개 있다면 그건 높이가 2임.
• 결과적으로 이러한 balance factor 를 통해 균형을 유지함.

(7) AVL 트리 - balance factor 예시

• 만약 50을 기준으로 한다면, 50의 왼쪽 서브트리는 높이가 1이 될 것이고, 오른쪽 서브트리의 높이는 2가 될 것이다. 그리고 왼쪽 서브트리 높이(1) - 오른쪽 서브트리 높이(2) 를 하게 되면, -1 높이차를 얻을 수 있게 된다.
• 그 결과 -1, 0, 1 에 포함이 되기 때문에 균형이 맞다고 판단해 해당 50 노드는 조정이 필요없다 판단을 하게 된다.
• ***즉, AVL 트리는 모든 노드의 밸런스 팩터를 구해가지고 범위를 벗어난다면 트리의 구조가 비효율적이라고 판단해 균형을 맞추는 작업인 위치 조정을 하는 그러한 자료구조로 볼 수 있다.***
• ***이러한 과정은 조회를 제외한 매번 삽입과 삭제 과정에서 밸런스 팩터를 확인하는 작업을 진행함.***

(8) AVL 트리 - 동작 예시

• 위와 같이 90을 삽입 한 뒤 삽입 연산이 이뤄졌으므로, BF(balance factor) 검사를 하게 되는데 이때 50을 보면 1, 0, -1 범위를 벗어나기 때문에 균형이 맞지 않다고 판단을 하게 됨.
• 또한, 해당 구조는 50을 기준으로 오른쪽 오른쪽으로 균형이 깨진 상태로 오른쪽 편향 트리로 볼 수 있음.
• 이제 균형을 잡아줘야하는데, 이진 탐색 트리 구조의 규칙을 따라야하며, 위의 오른쪽 이미지와 같은 모습으로 바뀌게 됨.
• 즉, 결과적으로 AVL 트리의 특징(높이차 1, 0 ,-1) 을 만족하는 구조로 바뀌게 된다.

(9) BB 트리

[ BB 트리 ( Bounded-Balanced Tree ]

• BB 트리의 "Bounded-Balanced Tree" 의 뜻은 "경계가 설정된 균형 트리" 또는 " 균형이 일정 범위(한계) 안에서 유지되는 트리" 를 의미한다.
• 쉽게말해, AVL 트리 처럼 완벽한 균형을 잡는 것이 아닌, 허용된 범위 안에서 균형을 유지하는 트리로 볼 수 있다.
• 즉, 허용 오차 내에서 균형을 유지해주며, 균형 조건이 심하지 않지만, 너무 흐트러지지 않게 제한된 균형 트리임.
• ***그리고 핵심은 해당 BB 트리가 의미하는 균형은 무게 기반 균형을 의미한다.***
• 결론은 해당 트리는 높이가 아닌 **서브트리의 노드 개수(크기/무게)**를 기준으로 균형을 잡는다.

[ 균형 조건: β (베타) ]

• BB 트리가 균형을 유지하는 정도는 **균형 인수 β(베타)** 라는 값으로 제어가 된다.

[ β 값에 따른 군형 정도 ]

• 📌 참고: β가 1/2에 가까울수록 균형은 엄격해지지만, 삽입/삭제 시 균형을 맞추기 위한 재조정 (Rebalancing) 작업이 더 자주 발생한다.

[ 결론 ]

• 결론적으로, BB 트리는 β 값을 설정하여 서브트리 간의 노드 개수 비율을 제한함으로써 "너무 기울어지지 않도록" 규현을 유지하는 효율적인 자료 구조로 볼 수 있음.
• AVL 트리는 높이를 기반으로 하고, BB 트리는 무게(노드의 갯수)를 기반으로 균형을 잡는 트리 자료구조임.