트리
- 계층적인 자료를 표현하는데 적합한 자료구조
> 트리는 한 개 이상의 노드로 이루어진 유한 집합. 노드는 루트노드라 불리고 나머지 노드는 서브트리라고 불림.
> 계층적인 구조에서 가장 높은 곳에 있는 노드가 루트가 된다. 그리고 나머지 루트들은 서브트리라고 한다. 서브트리는 다시 루트와 서브트리로 나눌 수 있다.
> 트리에는 루트와 서브트리는 선으로 연결한다. 이 선을 간선이라고 한다.
> 노드들 간에는 부모, 형제, 조상, 자손 관계가 존재한다.
조상노드: 루트 노트에서 임의의 노드까지의 경로를 이루고 있는 노드
후손노드: 노드의 서브 트리에 속하는 모든 노드
> 자식 노드가 없는 노드를 단말노드( terminal node, leaf node), 그 반대를 비단말 노드(nontermianl noade)라고 한다.
> 노드의 차수(degree)는 어떤 노드가 가지고 있는 자식 노드의 개수를 말한다. 트리의 차수는 트리가 가지고 있는 노드의 차수 중에서 가장 큰 값이다.
> 트리의 레벨(level)은 트리의 각층에 번호를 매기는 것으로서 정의에 의하여 루트 레벨은 1이 되고 한층 씩 내려갈 수록 1씩 증가한다.
> 나무가 모이는 숲이 되듯이 트리들의 집합을 포레스트(forest)라고 한다.
트리의 통류
> 트리를 표현하는 가장 일반적인 방식은 각 노드가 데이터를 저장하는 데이터필드와 자식 노드를 가리키는 링크필드를 가지게 하는 것이다. 일반적인 트리에서 각 노드들은 서로 다른 개수의 자식 노드를 가지므로 노드에 따라서 링크필드의 개수가 달라진다.
문제점 > 노드의 크기가 고정되지 않고, 노드에 붙어 있는 자식 노드의 개수에 따라서 노드의 크기가 커지기도 하고 작아지기도 한다. 이처럼 노드의 크기가 일정하지 않으면 프로그램이 복잡하게 된다.
이진트리
- 트리 중에서 가장 많이 사용되는 트리
- 모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진트리(binary tree)라고 한다.
> 서브 트리는 공집합일 수 있으며, 이진트리의 노드에는 최대 2개까지의 자식 노드가 존재할 수 있고 모든 노드의 차수는 2이하가 된다. 공집합도 이진트리라는 점에 주의해야 한다.
> 이진 트리에는 서브 트리간의 순서가 존재한다. 그리고 왼쪽 서브트리와 오른쪽 서브 트리는 구분된다.
-이진트리와 일반 트리의 차이점
- 이진트리의 모든 노드의 차수는 2 이하이다. 따라서 자식 노드의 개수가 2 이하이다. 반면 일반트리는 자식 노드의 개수에 제한이 없다
- 일반 트리와는 달리 이진트리는 노드를 하나도 갖지 않을 수도 있다
- 서브 트리간에 순서가 존재한다. 따라서 왼쪽 서브트리와 오른쪽 서브트리를 구분한다.
- 이진트리의 성질
- n개의 노드를 가진 이진트리는 n-1의 간선을 가진다. 왜냐하면 이진트리에서 노드는 루트를 제외하면 정확하게 하나의 부모 노드를 가지기 때문이다. 그리고 부모와 자식 간에는 정확하게 하나의 간선만이 존재한다. 따라서 간선의 개수는 n-1개이다.
- 높이가 k인 이진트리의 경우 최소 k개의 노드를 가지며 최대 2^k-1개의 노드를 가진다. 왜냐하면 한 레벨에는 적어도 하나의 노드가 존재히야 하므로 노드가 k인 이진트리는 적어도 k개의 노드를 가진다 또한 하나의 노드는 최대 2개의 자식을 가질 수 있으므로 레벨 i에서의 노드의 최대개수는 2^(i-1)이 된다.
- n개의 노드를 가지는 이진트리의 높이는 최대 n이거나 최소 log2(n+1)이 된다. 왜냐하면 레벨 단 최소한 하나의 노드는 있어야하므로 높이가 n을 넘을 수 없다. 그리고 앞의 성질에서 높이 h의 이진트리가 가질 수 있는 노드의 최댓값은 2^(k-1)이다
- 이진트리의 분류
- 포화이진트리(full binary tree)
- 완전이진트리(complete binary tree)
- 기타 이진 트리
- 포화 이진트리
> 트리의 각 레벨에 노드가 꽉 차있는 이진트리
> 높이 k인포화 이진트리는 정확하게 2^k-1개의 노드를 가진다
> 각 노드에 번호를 붙일 수 있으며, 부여하는 방식은 레벨 단위로 왼쪽에서 오른쪽으로 번호를 붙이면 된다. 그리고 번호는 항상 일정한데 루트 노드의 오른쪽 자식 노드의 번호는 항상 3이다.
- 완전 이진트리
> 높이 k일 때 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리이다. 마지막 레벨에서는 노드가 꽉 차있지 않아도 되지만, 중간에 빈 곳이 있어서는 안 된다. 따라서 포화 이진트리는 항상 완전 이진트리이지만 그 역은 항상 성립하지 않는다. 포화 이진트리의 노드 번호와 이진트리의 노드 번호는 1대 1로 대응한다.
이진트리의 표현법
- 배열을 이용하는 방법
- 포인터를 이용하는 방법
- 배열 이용하는 방법
> 배열을 이용하는 방법은 주로 포화 이진트리나 완전이진트리 같은 경우 많이 쓰인다. 저장하고자 하는 이진트리를 일단 완전이진트리라고 가정하면 이진트리의 깊이가 k일 때 최대 2^k-1개의 공간을 연속적으로 할당한 다음 완전이진트리의 번호대로 노드를 저장한다.
> 완전 이진트리가 아닌 경우에는 배열 표현법을 사용하면 저장할 수 있지만 기억공간의 낭비가 심해진다.
> 배열 표현법에서 부모와 자식의 인덱스에는 다음과 같은 공식이 사용된다.
- 노드 i의 부모 노드 인덱스=i/2
- 노드 i의 왼쪽 자식 노드 인덱스=2i
- 노드 i의 오른쪽 자식 노드 인덱스=2i+1
- 링크 표현법(포인터 사용 방법)
- 트리에서 노드가 구조체로 표현되고 각노드가 포인터를 가지고 있어서 이 포인터를 이용해서 노드와 노드를 연결하는 방법
> 이진트리를 링크 표현법으로 표현하면 하나의 노드가 3개의 필드를 가지는데, 데이터를 저장하는 필드와 왼쪽자식노드와 오른쪽 자식 노드를 가리키는 2개의 포인터 필드를 가진다. 이 2개의 포인터를 이용해서 부모노드와 자식노드를 연결한다.
구조체 사용 노드의 구조 정의
typedef struct TreeNode{
int data;
struct TreeNode *left, *right;
}TreeNode;> 링크법으로 표현된 트리는 루트 노드를 가리키는 포인터만 있으면 트리안의 모든 노드들에 접근할 수 있다.
> 연결 리스트는 1차원적인 연결 구조라면 링크법으로 표현된 이진트리는 2차원적으로 연결된 구조이다.
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
} TreeNode;
int main(void)
{
TreeNode *n1, *n2, *n3;
n1 = (TreeNode *)malloc(sizeof(TreeNode));
n2 = (TreeNode *)malloc(sizeof(TreeNode));
n3 = (TreeNode *)malloc(sizeof(TreeNode));
n1->data = 10; // 첫 번째 노드를 설정한다.
n1->left = n2;
n1->right = n3;
n2->data = 20; // 두 번째 노드를 설정한다.
n2->left = NULL;
n2->right = NULL;
n3->data = 30; // 세 번째 노드를 설정한다.
n3->left = NULL;
n3->right = NULL;
free(n1); free(n2); free(n3);
return 0;
}
이진트리의 순회
- 이진트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것.
- 이진트리 순회방법
> 루트와 왼쪽 서브트리, 오른쪽 서브트리 중에서 루트를 언제 방문하는지에 따라서 구분한다. 만약 루트를 방문하는 작업을 V라고 하고 왼쪽 서브트리방문을 L, 오른쪽 서브트리 방문을 R이라고 하면 다음과 같은 방법을 생각할 수 있다.
- 전위순회(preorder traversal) : VLR
- 중위순회(inorder traversal): LVR
- 후위순회(postorder traversal): LRV
> 트리 순회 알고리즘은 순환 기법을 사용한다.
> 이진트리에서 전체트리나 서브트리나 그 구조는 동일하다. 따라서 전체 트리 순회에 사용된 알고리즘을 똑같이 서브트리에 적용할 수 있다.
- 전위 순회
- 전위 순회는 루트를 먼저 방문하고 왼쪽 서브트리, 오른쪽 서브트리를 마지막으로 방문하는 방법이다.
- 전회순위에서 루트 노드의 방문을 마쳤다고 가정한다
- 왼쪽 서브트리도 하나의 이진트리이다. 따라서 전체 트리와 똑같은 방식으로 서브 트리를 방문하면 된다
- 왼쪽 서브트리의 루트를 먼저 방문하고 왼쪽 서브트리의 왼쪽 서브트리를 방문한다
- 마지막으로 왼쪽 서브트리의 오른쪽 서브트리를 방문하면 된다.
- 모든 서브트리에 대해서 같은 알고리즘을 반복한다.
- 중위 순회
- 중위 순회는 먼저 왼쪽 서브트리, 루트, 오른쪽 서브트리 순서대로 방문한다
inorder(x)
if x != NULL //노드 x가 null이면 더이상 순환호출을 하지 않는다
than inorder(Left(x)); //x의 왼쪽 서브트리를 순환 호출하여 방문한다
print DATA(x); //x의 데이터를 출력한다
inorder(Right(x)); //x의 오른쪽 서브트리를 순환 호출하여 방문한다.
}
- 후위 순회
- 후위 순회는 왼쪽 서브트리, 오른쪽 서브트리, 루트 순서대로 방문한다.
postorder(x)
if x != NULL //노드 x가 null이면 더이상 순환호출을 하지 않는다
than postorder(Left(x)); //x의 왼쪽 서브트리를 순환 호출하여 방문한다
postorder(Right(x)); //x의 오른쪽 서브트리를 순환 호출하여 방문한다.
print DATA(x); //x의 데이터를 출력한다
}
- 순회 구현
> 함수의 매개 변수는 루트를 가리키는 포인터가 된다. 표준적인 순회방법이 순환적으로 정의되어 있다는 것에 착안해야 한다.
> 왼쪽이나 오른쪽 서브트리를 방문하는 것은 전체 트리를 방문하는 것이나 다름이 없다. 따라서 전체 트리를 방문 함수를 다시 한번 호출해 주면 된다. 차이점은 함수의 매개변수가 달라지게 되면서 서브트리를 방문하는 경우에는 서브트리의 루트 노드 포인터를 함수의 매개변수고 전달하면 된다.
// 중위 순회
void inorder(TreeNode *root) {
if (root != NULL) {
inorder(root->left);// 왼쪽서브트리 순회
printf("[%d] ", root->data); // 노드 방문
inorder(root->right);// 오른쪽서브트리 순회
}
}
// 전위 순회
void preorder(TreeNode *root) {
if (root != NULL) {
printf("[%d] ", root->data); // 노드 방문
preorder(root->left);// 왼쪽서브트리 순회
preorder(root->right);// 오른쪽서브트리 순회
}
}
// 후위 순회
void postorder(TreeNode *root) {
if (root != NULL) {
postorder(root->left);// 왼쪽서브트리 순회
postorder(root->right);// 오른쪽서브트리순회
printf("[%d] ", root->data); // 노드 방문
}
}> 상황에 따라서 맞는 순회방법을 사용하면 되는데, 자식 노드를 처리한 다음에 부모노드를 처리해야 한다면 후위순회를 사용하고 부모노드를 처리한 다음에 자식 노드를 처리해야 하면 전위 순회를 사용한다.
수식 트리 처리
> 이진트리는 수식트리를 처리하는 데 사용될 수 있다. 수식 트리는 산술연산자와 피연산자로 만들어진다. 피연산자들은 단말 노드가 되며 연산자는 비단말 노드가 된다.
| 수식 | a+b | a - ( b x c ) | (a<b) or (c<d) |
| 전위수식 | +ab | - a x b c | or <a b < c d |
| 중위수식 | a+b | a - ( b x c) | (a < b) or (c < d) |
| 후위수식 | ab+ | abc x - | a b < c d < or |
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
} TreeNode;
// +
// * +
// 1 4 16 25
TreeNode n1 = { 1, NULL, NULL };
TreeNode n2 = { 4, NULL, NULL };
TreeNode n3 = { '*', &n1, &n2 };
TreeNode n4 = { 16, NULL, NULL };
TreeNode n5 = { 25, NULL, NULL };
TreeNode n6 = { '+', &n4, &n5 };
TreeNode n7 = { '+', &n3, &n6 };
TreeNode *exp = &n7;
// 수식 계산 함수
int evaluate(TreeNode *root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return root->data;
else {
int op1 = evaluate(root->left);
int op2 = evaluate(root->right);
printf("%d %c %d을 계산합니다.\n", op1, root->data, op2);
switch (root->data) {
case '+':
return op1 + op2;
case '-':
return op1 - op2;
case '*':
return op1 * op2;
case '/':
return op1 / op2;
}
}
return 0;
}
//
int main(void)
{
printf("수식의 값은 %d입니다. \n", evaluate(exp));
return 0;
}
이진트리의 추가 연산
- 노드의 개수
> 탐색 트리안의 노드의 개수를 세어 표시한다. 노드의 개수를 세기 위해서는 트리안의 노드들을 전체적으로 순회해야 한다. 각각의 서브트리에 대해서 순환 호출 한 다음, 반환되는 값에 1을 더하여 반복한다.
get_node_count(x):
if x!= NULL then
return 1+get_count(x.left)+get_count(x.right)
- 단말 노드 개수 구하기
> 단말 노드의 개수를 세기 위해서는 트리안의 노드들을 전체적으로 순회해야 한다. 순회하면서 만약 왼쪽 자식과 오른쪽 자식이 동시에 0이 되면 단말노드이므로 1을 반환한다. 만약 그렇지 않으면 비단말 노드이므로 각각의 서브트리에 대하여 순환 호출한 다음, 반환되는 값을 서로 더하면 된다.
get_leaf_count(T):
if T != NULL then
if t.left == NULL and T.right == NULL
then return 1;
else return get_leaf_count (T.left)+get_leaf_count(T.right)
- 높이 구하기
> 각 서브 트리에 대하여 순환 호출을 해야 한다. 순환 호출이 끝나면 각각 서브 트리의 높이가 반환되어 왔을 것이다. 그러면 여기서 서브 트리들의 반호나 값 중에서 최대 값을 구하여 반환하면 된다.
get_height(T):
if T != NULL
return 1+max(get_height(t.left), get_height(T.right))
이진 탐색 트리
> 이진 탐색트리는 이진트리 기반의 탐색을 위한 자료구조이다
- 컴퓨터 프로그램에서 탐색은 레코드(record)의 집합에서 특정한 레코드를 찾아내는 작업을 의미한다. 레코드는 하나 이상의 필드(field)로 구성된다. 레코드들의 집합을 테이블(table)이라고 한다. 레코드들은 보통 키(key)라고 불리는 하나의 필드에 의해 식별될 수 있다.
- 일반적인 경우 어떤 키는 다른 키와 중복되지 않는 고유한 값을 가지며 이러한 키를 사용하면 각각의 레코드들을 구별할 수 있다. 이러한 키를 주요 키(primary key)라고 부른다. 탐색 작업을 할 때 이러한 키가 입력이 되어 특정한 키를 가진 레코드를 찾는다. 이진 탐색트리는 이러한 작업을 효율적으로 하기 위한 자료구조이다.
- 이진 탐색 트리란
> 찾고자 하는 키값이 이진트리의 루트 노드의 킷값과 비교하여 루트 노드보다 작으면 원하는 키 값은 왼쪽 서브트리에 있고 루트 노드보다 크면 원하는 키 값은 오른쪽 서브트리에 있음을 알 수 있다.
- 순환적인 탐색연산
- 비교한 결과가 같으면 탐색이 성공적으로 끝난다
- 비교한 결과가, 주어진 키 값이 루트노드의 키 값보다 작으면 탐색은 이 루트 노드의 왼쪽 자식을 기준으로 다시 시작한다
- 비교한 결과가, 주어진 키 값이 루트 노드의 키 값보다 크면 탐색은 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작한다.
이진 탐색 트리 탐색 알고리즘
search(root, key):
if root == NULL
then return NULL
if key == KEY(root)
then return root
else if key < KEY(root)
than return search(LEFT(root),k)
else return search(RIGHT(root), k)
-반복적인 탐색 연산
- 반복적인 탐색연산은 매개변수 node가 null이 아니면 반복을 계속한다
- 반복 루프 안에서 현재 node의 키 값이 key와 같은지 검사한다. 만약 같으면 탐색 성공이므로 현재 노드 포인터를 반환하고 끝낸다
- key가 현재 노드 키 값보다 작으면 node 변수를 node의 왼쪽 자식을 가리키도록 변경한다
- key값이 현재 노드 키값보다 크면 node변수를 node의 오른쪽 자식을 가리키도록 변경한다
- 이 반복을 node가 결국 단말 노드까지 내려가서 null값이 될 때 가지 계속한다.
- 만약 반복이 종료되었는데 아직 함수가 리턴되지 않았다면 탐식이 실패한 것이므로 null을 반환한다.
- 함수는 매개변수 node를 직접 사용했는데 사실 매개변수는 원본 변수의 복사본이므로 변경하여도 원본 변수에는 별 영향이 없다.
- 삽입연산
> 이진탐색 트리에 원소를 삽입하기 위해서 먼저 탐색을 수행하는 것이 필요하다. 왜냐하면 이진탐색 트리에서는 같은 키 값을 갖는 노드가 없어야 하기 때문이고, 탐색에 실패한 위치가 새로운 노드를 삽입하는 위치가 되기 때문이다.
insert (root, n):
if Key(n) == Key(root) //root와 key가 같아면
then return; //return
else if key(n) < Key(root) then // root보다 key가 크면
if Left(root) == null //root의 왼쪽 자식이
then Left(root) <- n //없으면 n이 왼쪽 자식
else insert (Left(root),n) //있으면 순환 호출
else
if Right(root) == null
then Right(root)<-n
else insert (Right(root),n)
- 삭제연산
> 노드를 삭제하는 것은 이진탐색 트리에서 가장 복잡한 연산이다. 먼저 노드를 삭제하기 위해서 먼저 노드를 탐색해야 한다. 삭제하려고 하는 키값이 트리 안에 어디 있는지를 알아야 지울 수 있다
- 삭제하려고 하는 노드가 단말일 경우
- 삭제하려는 노드가 하나의 왼쪽이나 오른쪽 서브 트리 중 하나만 가지고 있는 경우
- 삭제하려는 노드가 두 개의 서브트리 모두 가지고 있는 경우
- 삭제하려고 하는 노드가 단말일 경우
> 단말 노드아래 더 이상의 노드가 없으면 가장 쉽게 제거할 수 있다. 단말 노드만 지우면 된다. 단말 노드를 지운다는 것은 단말 노드의 부모 노드를 찾아서 부모 노드 안의 링크 필드를 null로 만들어서 연결을 끊으면 된다. 다음으로 노드를 동적으로 생성했으면 단말 노드를 동적 메모리 해제시키면 된다
- 삭제하려는 노드가 하나의 서브트리만 가지고 있는 경우
> 삭제되는 노드가 왼쪽이나 오른쪽 서브트리 중 하나만 가지고 있는 경우에는 자기 노드는 삭제하고 서브트리는 자기 노드의 부모 노드를 붙여주면 된다.
- 삭제하려는 노드가 두 개의 서브트리를 가지는 경우
> 서브트리에 어떤 노드를 삭제 노드 위치로 가져올 것이냐 인데 확실한 것은 왼쪽 자식이나 오른쪽 자식이나 그냥 가져오면 안 된다.
> 삭제되는 노드와 가장 값이 비슷한 노드를 후계자로 선택해야 마찰이 적다. 그래야만 다른 노드를 이동시키지 않아도 이진 탐색 트리가 그대로 유지된다.
> 왼쪽 서브트리에서 가장 큰 값이나 오른쪽 서브트리에서 가장 작은 값이 삭제되는 노드가 가장 가까운 경우가 많다. 왼쪽 서부트리에서 가장 큰 값은 왼쪽 서브트리의 가장 오른쪽에 있는 노드이며 오른쪽 서브트리에서 가장 작은 값은 오른쪽 서브트리의 가장 왼쪽에 있는 노드가 된다. 또한 노드는 이진 탐색 트리를 중위 순회하였을 경우 각각 선생 노드와 후속 노드에 해당된다.
- 후계자 대상 노드 중에서 어떤 것을 선택해도 상관은 없다. 삭제되는 노드의 오른쪽 서브트리에서 가장 작은 값을 갖는 노드는 오른쪽 서브 트리에서 왼쪽 자식 링크를 타고 null을 만날 때 가지 계속 진행하면 된다
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct TreeNode {
element key;
struct TreeNode *left, *right;
} TreeNode;
// 순환적인 탐색 함수
TreeNode * search(TreeNode * node, int key)
{
if (node == NULL) return NULL;
if (key == node->key) return node;
else if (key < node->key)
return search(node->left, key);
else
return search(node->right, key);
}
TreeNode * new_node(int item)
{
TreeNode * temp = (TreeNode *)malloc(sizeof(TreeNode));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
TreeNode * insert_node(TreeNode * node, int key)
{
// 트리가 공백이면 새로운 노드를 반환한다.
if (node == NULL) return new_node(key);
// 그렇지 않으면 순환적으로 트리를 내려간다.
if (key < node->key)
node->left = insert_node(node->left, key);
else if (key > node->key)
node->right = insert_node(node->right, key);
// 변경된 루트 포인터를 반환한다.
return node;
}
TreeNode * min_value_node(TreeNode * node)
{
TreeNode * current = node;
// 맨 왼쪽 단말 노드를 찾으러 내려간다.
while (current->left != NULL)
current = current->left;
return current;
}
// 이진 탐색 트리와 키가 주어지면 키가 저장된 노드를 삭제하고
// 새로운 루트 노드를 반환한다.
TreeNode * delete_node(TreeNode * root, int key)
{
if (root == NULL) return root;
// 만약 키가 루트보다 작으면 왼쪽 서브 트리에 있는 것
if (key < root->key)
root->left = delete_node(root->left, key);
// 만약 키가 루트보다 크면 오른쪽 서브 트리에 있는 것
else if (key > root->key)
root->right = delete_node(root->right, key);
// 키가 루트와 같으면 이 노드를 삭제
else {
// 첫 번째나 두 번째 경우
if (root->left == NULL) {
TreeNode * temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
TreeNode * temp = root->left;
free(root);
return temp;
}
// 세 번째 경우
TreeNode * temp = min_value_node(root->right);
// 중외 순회시 후계 노드를 복사
root->key = temp->key;
// 중외 순회시 후계 노드를 삭제
root->right = delete_node(root->right, temp->key);
}
return root;
}
// 중위 순회
void inorder(TreeNode * root) {
if (root) {
inorder(root->left);// 왼쪽서브트리 순회
printf("[%d] ", root->key); // 노드 방문
inorder(root->right);// 오른쪽서브트리 순회
}
}
int main(void)
{
TreeNode * root = NULL;
TreeNode * tmp = NULL;
root = insert_node(root, 30);
root = insert_node(root, 20);
root = insert_node(root, 10);
root = insert_node(root, 40);
root = insert_node(root, 50);
root = insert_node(root, 60);
printf("이진 탐색 트리 중위 순회 결과 \n");
inorder(root);
printf("\n\n");
if (search(root, 30) != NULL)
printf("이진 탐색 트리에서 30을 발견함 \n");
else
printf("이진 탐색 트리에서 30을 발견못함 \n");
return 0;
}
이진탐색 트리 분석
> 이진탐색 트링에서 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 k라고 했을 때 O(h)가 된다. 따라서 n개의 노드를 가지는 이진 탐색트리의 경우, 일반적인 이진트리의 높이는 log2n이므로 이진 탐색 트리 연산의 평균적인 경우 시간복잡도는 O(log2 h)이다
> 최악의 경우 한쪽으로 치우치는 경사 트리가 되어서 트리의 높은 n이 될 경우 탐색, 삭제, 삽입시간이 거의 선형 탐색과 같이 O(n)이 된다
> 선형탐색에 비해 전혀 시간적으로 이득이 없어서 이러한 최악의 경우를 방지하기 위해 트리의 높이를 log2n으로 한정시키는 균형기법이 필요하다. 그래서 AVL트리를 비롯한 여러 기법이 개발되었다.