아래와 같은 이진 탐색 트리가 있습니다.
이때 150이라는 데이터를 넣으려고 합니다.
그럼 일단 루트 노드부터 비교를 하겠죠?
150은 100보다 크니까 오른쪽으로 갑니다.
그곳에는 300이 있네요. 150은 300보다 작으므로
왼쪽에 자식 노드로 배치될 겁니다.
보면 처음 루트 노드를 비교할 때부터 자리를 잡을 때까지
노드를 비교한 후, 한 쪽을 선택하기 때문에
나머지 절반을 배제하고 있습니다.
이진 탐색 트리는 데이터를 탐색할 때뿐만 아니라,
데이터를 입력하는 과정도 O( log N )이네요.
반면에 vector와 list는 비교할 것 없이
바로 데이터를 입력하죠. 빅오 표기법으로 나타내면
O ( 1 )입니다. 대신 탐색할 때는 O( N )이죠.
이진 탐색 트리는 입력과 탐색 모두
O ( logN )으로 표현할 수 있습니다.
즉 입력은 다른 자료 구조에 비해 느리지만
탐색은 더 빠르다는 것입니다.
이진 탐색 트리의 데이터를 순서대로 접근하려면
중위 순회(inorder) 방식으로 순회해야 합니다.
중위 순회는 아래 그림을 통해 알 수 있듯이
부모 노드의 자식 노드 중 왼쪽을 먼저 순회하고
이후 부모 노드를 순회, 마지막으로 오른쪽 자식 노드를
순회하는 방식입니다.
아래 그림을 보시면
중위 순회 진행 시 루트 노드로 갑니다.
100은 부모 노드이죠?
그래서 왼쪽 자식 노드로 갑니다.
근데 50이 들어 있는 노드도 부모 노드입니다.
그래서 왼쪽 자식 노드로 갑니다.
25는 자식 노드가 맞네요.
25라는 값을 얻습니다.
( 현재 탐색한 데이터 : 25 )
이후 부모 노드의 값을 얻습니다.
( 현재 탐색한 데이터 : 25 - 50 )
다음 마지막 순서인
오른쪽 자신 노드의 값을 얻습니다.
( 현재 탐색한 데이터 : 25 - 50 - 75 )
루트 노드 입장에서 왼쪽 자식 노드들의
값을 얻었으니 이제 부모 노드인 자신의 값을
얻습니다.
( 현재 탐색한 데이터 : 25 - 50 - 75 - 100 )
그리고 마지막 순서인 오른쪽 자식 노드의
값을 얻으려고 했는데 오른쪽 자식 노드도
자식 노드를 갖고 있어 부모 노드네요.
그래서 넘기고 왼쪽 자식 노드의 값을 얻습니다.
( 현재 탐색한 데이터 : 25 - 50 - 75 - 100 - 150 )
이후 부모 노드의 값을 얻습니다.
( 현재 탐색한 데이터 : 25 - 50 - 75 - 100 - 150 - 300 )
마지막으로 오른쪽 자식 노드의 값을 얻습니다.
( 현재 탐색한 데이터 : 25 - 50 - 75 - 100 - 150 - 300 - 500 )
중위 순회 방식으로 이진 탐색 트리의 데이터를
정렬된 순서대로 탐색할 수 있네요.
이진 탐색 트리를 구성할 때
작은 데이터는 왼쪽에 큰 데이터는 오른쪽에 입력하고
중위 순회 방식으로 순회하였더니
정렬된 순서대로 데이터를 얻을 수 있죠.
이러한 이유로 이진 탐색 트리에서 중위 순회는
상당히 중요하다고 볼 수 있습니다.
나중에 이진 탐색 트리에 iterator를 구현한다고 했을 때
이진 탐색 트리의 begin 함수를 호출하여
iterator에 값을 넣으면 25가 대입되겠죠?
iterator가 특정 노드를 가리키고 있는 상태에서
++ 연산을 하면 다음 노드를 가리켜야겠죠?
iterator가 100이 저장된 루트 노드를 가리키고 있다고 합시다.
해당 iterator에 ++ 연산을 하면 중위 순회 기준으로,
150이 저장된 노드를 가리켜야 할 겁니다.
현재 노드로부터 다음에 있는 노드를 '중위 후속자'라고 합니다.
반대로 100이 저장된 루트 노드를 가리키는
iterator에 -- 연산을 하면 중위 순회 기준으로,
75가 저장된 노드를 가리켜야겠죠.
현재 노드로부터 이전에 있는 노드를 '중위 선행자'라고 합니다.
위 이진 탐색 트리에서 500을 찾고자 한다면
일단 루트 노드부터 비교합니다.
500은 100보다 크니까
오른쪽에 있을 것이므로 왼쪽을 배제합니다.
이후 300과 비교하는데
300보다 크므로 오른쪽에 있을 것이므로
왼쪽을 배제하죠.
이런 식으로 왼쪽 또는 오른쪽의 데이터를 덜어 내면서
원하는 데이터를 O( logN )의 효율로 찾아낼 수 있는 겁니다.
추가로, 트리를 순회하는 방식 중에는
전위 순회(preorder), 후위 순회(postorder) 방식이 있습니다.
아래 그림처럼
전위 순회는 부모 노드를 가장 먼저 탐색하고
왼쪽 자식 노드, 오른쪽 자식 노드순으로 탐색하는 방식입니다.
전위 순회를 통해 아래 이진 트리를 탐색하면
100 - 50 - 25 - 75 - 300 - 150 - 500순으로
데이터를 얻게 되겠죠.
아래 그림처럼
후위 순회는 왼쪽 자식 노드를 먼저 탐색하고
이후 오른쪽 자식 노드, 부모 노드순으로 탐색하는 방식입니다.
후위 순회를 통해 아래 이진 트리를 탐색하면
25 - 75 - 50 - 150 - 500 - 300 - 100순으로
데이터를 얻게 되겠죠.
이진 탐색 트리가 언제나
이상적으로 작동할 수 있는 건 아닙니다.
만약 1 ~ 1000이라는 데이터가
순차적으로 입력된다고 가정해 보죠.
1이 입력되고 다음 2가 입력되면서
오른쪽에 배치되겠죠. 다음에 입력된 3도
오른쪽에 배치됩니다. 이렇게 순차적으로
1000까지 입력되었습니다.
모두 오른쪽에 배치됐을 겁니다.
이러한 상황에서 1000을 찾는다고 하죠.
루트 노드에는 1이 저장되어 있습니다.
찾고하 하는 값인 1000이 더 크므로
오른쪽을 탐색하게 될 겁니다.
그런데 왼쪽에는 데이터가 없습니다.
배제되는 데이터가 없으므로
여전히 999개의 노드를 탐색해야 합니다.
이진 탐색 트리로 구성하였으나
이점이 전혀 발휘되고 있지 않죠.
이진 탐색 트리의 모양이 삼각형으로
밸런스가 잡혀 있어야 탐색 효율이 나오는 것이죠.
하지만 데이터가 어떤순으로 들어갈지는
알 수가 없기 때문에 언제나 이상적인 모양이
나올 수가 없습니다.
이러한 문제가 있기 때문에
보통 이진 탐색 트리만
가지고 구현을 하지 않습니다.
자동으로 밸런스를 잡아 주는
자가 균형 이진 탐색 트리( Self-balancing binary search tree )를
통해 구현을 합니다.
대표적으로 AVL tree, Red - Black tree가 있습니다.
Red - Black tree를 시각적으로 볼 수 있는 사이트가 있습니다.
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
Red/Black Tree Visualization
www.cs.usfca.edu
위 사이트에 접속하면
위와 같은 화면이 나옵니다.
Insert 앞 빈칸에 값을 넣고 Insert를 누르면
입력한 값을 가진 노드가 하나 생성됩니다.
3까지 입력하였더니
루트 노드가 바뀌었습니다.
기존에는 1을 저장한 노드가 루트 노드였는데
이제는 2를 저장한 노드가 루트 노드가 되었죠.
자칫하면 트리가 오른쪽으로 치우칠 수 있는
값이었는데 자동으로 균형을 잡아 주는 모습이죠.
순차적으로 값을 9까지 입력하였습니다.
그랬더니 일반 이진 탐색 트리와는 다르게
밸런스를 자동으로 잡아 주면서 이상적인 모습의
이진 탐색 트리가 구성된 것을 볼 수 있습니다.
실제 문법에 구현된 자료 구조에서는
이러한 시스템이 다 구현되어 있어야겠죠?
그래서 사실 이진 탐색 트리의
데이터 입력 효율이 딱 O( logN )이라고
할 수는 없습니다. 왜냐하면 데이터 입력 과정에서
밸런스가 무너졌냐를 판단해야 하고,
만약 무너졌다면 루트 노드를 바꾸면서
노드들이 회전을 해야 하기 때문이죠.
자가 균형 기능이 들어간 트리,
Red - Black tree 가 구현된 자료 구조는
C++에서 제공하는 'map' 이 있습니다.
강의 출처 : https://www.youtube.com/watch?v=PFc4g8mxOiI&list=PL4SIC1d_ab-aOxWPucn31NHkQvNPHK1D1&pp=iAQB
'C++ > 기초' 카테고리의 다른 글
| C++ 기초 : tree (5) (0) | 2024.04.27 |
|---|---|
| C++ 기초 : tree (4) (0) | 2024.04.26 |
| C++ 기초 : tree (2) (0) | 2024.04.26 |
| C++ 기초 : tree (1) (0) | 2024.04.26 |
| C++ 기초 : inline (2) | 2024.04.26 |
