이진 거래의 장점

• 마지막 레벨을 제외하고 포화 이진 트리이며, 최하위 레벨의 단말 노드들은 왼쪽에서부터 채워진 형태로 되어 있는 경우를 의미
• 중간 노드의 자식 수가 2일 때, 이진 거래의 장점 단말 노드의 수가 n이면, 전체 노드 수는 N = 2n-1개가 됨
• 완전 이진트리 또한 포화 이진트리와 노드 번호와 일치합니다.

코인하는 프로그래머

다른이름으로 순차 검색(Sequential Search) 이라고도 하는 선형검색에 대하여 먼저 알아보겠습니다.

선형 검색은 데이터가 모인 집합(배열, 링크드리스트 등)의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 알고리즘입니다.

데이터를 이진 거래의 장점 정렬하거나 따로 건드릴 필요가 없고, 난이도가 쉬운 편이나, 데이터의 양이 많아지면 검색에 소요되는 시간도 비례하여 많아지고, 하나씩 일일이 비교하기 때문에 비효율적이라는 단점이 있습니다. 예를들어 위와 이진 거래의 장점 같은 데이터의 집합이 있을경우 4를 찾으려면 10번의 비교를 거쳐야 합니다. 100만개의 데이터가 있고 찾고자 하는 데이터가 100만번째에 있다면 100만번의 비교를 해야 한다는 뜻 입니다. 이와 같은 상황을 Worst Case라고 합니다. 관련된 용어로 평균적인 상황을 Average Case 좋은 상황을 Best Case라고 합니다.

코드를 통하여 살펴보도록 하겠습니다.

반복문을 size만큼 실행시킬텐데, 배열의 0번째 방부터 찾는 값이 있는지 훑어 나갑니다. 위 표를 예시로 삼으면 size는 10이고, target은 4가 되겠습니다. 반복문을 통해 arr[0]부터 i의 값을 증가시키면서 진행이 되겠죠. arr[9]에서 target이 되는 4라는 값을 찾았으니, 방의 번호 9를 리턴합니다.

이진검색(Binary Search)

이진검색은 다른말로 이분 (二分) 검색이라고도 합니다. 반으로 나누어서 연산하기 때문이죠. 선형검색의 경우 데이터 집합의 처음에서 시작하여 끝까지 탐색하는 알고리즘 이지만 이진검색은 중간값부터 탐색을 합니다. 선형검색은 링크드리스트에서 자주 쓰이는 반면에 이진검색은 트리구조에서 자주 쓰이는 형식입니다.

이진검색은 데이터를 계속 반으로 나누면서 연산하기 때문에 처리속도가 매우 빠르다는 장점을 가지고 있습니다. 그러나 이진검색을 하기 위해서 데이터의 집합이 반드시 정렬(Sort)되어야 한다는 단점이 있습니다. 이렇게 이야기하면 얼마나 빠른지 이진 거래의 장점 감이 잘 안올텐데, 예를들어 70억명의 사람중 한사람을 찾으려고 한다면, 선형검색은 Worst Case의 경우 70억번, 대략적으로 생각해도 35억번은 비교연산을 해야 하는데, 이진 검색은 최대 33번의 비교만으로도 이진 거래의 장점 원하는 데이터를 찾을 수 있습니다.

일단 선택된 중간값인 5와 타겟인 9의 값을 비교합니다. 9가 더 큰 숫자이기 때문에 오른쪽으로 진행됩니다. 5보다 작은수인 0부터 4까지는 비교연산을 할 필요가 없습니다. 이제 5부터 9까지의 중간값을 다시 선택합니다.

함수 내부에서는 로컬변수로 first와 last, mid를 각각 선언 및 초기화 합니다. first는 arr의 첫번째 방을 뜻하는 이진 거래의 장점 0으로, last는 arr의 마지막 방인 size - 1 (예를들어 배열의 크기가 10이면 방의 번호는 0부터 9까지 이므로 9가 되겠음), mid는 담을 값이 아직 없으므로 선언만 하고 이진 거래의 장점 초기화는 하지 않았습니다.

이제 first가 last가 될때까지 반복문을 실행합니다. 첫줄에 mid를 중간값으로 정의합니다. 이때 arr의 mid번째 방에 있는 데이터가 target과 일치한다면 mid를 리턴하면 종료합니다. 그렇지 이진 거래의 장점 않으면 target이 arr[mid]보다 클때와 작을때로 나누어서 비교를 하며, 값을 찾을때까지 범위를 줄여 나갑니다. 선형검색과 마찬가지로 데이터를 찾지 못하면 -1을 리턴하면 되겠습니다.

선형검색과 이진검색에 대하여 알아보았습니다. 도움이 되셨다면 좋겠습니다.

'C,C++' 카테고리의 다른 글

정렬(Sort) : 빠른정렬, 퀵 소트(Quick Sort) (0)	2016.03.29
자료구조 : 재귀함수(Recursive Function) (0)	2016.03.28
자료구조 : 선형검색(Linear Search)와 이진 검색(Binary Search) (11)	2016.03.17
정렬(Sort) : 선택정렬(Selection Sort) (0)	2016.03.11
정렬(Sort) : 삽입정렬(Insertion Sort) (5)	2016.03.11
데이터 캡슐화, 하이딩, 은닉기법 (0)	2016.03.10

1-1. Link 타입은 Node* 의 이름을 바꾼것입니다
즉 Link pred 라고 함은 Node* pred라고 선언함과 같습니다.
1-2. 마찬가지로 ListElementType는 int와 같습니다.
즉 int &elem 이라고 선언한것과 같죠.

2. head->next = 0
0은 ASCII 코드로 NULL을 뜻합니다. 아무것도 없다는 것이죠
head->next는 Link 즉 Node* 인데 포인터는 가리키고 있는 값의 주소값을 보여주죠 head->next = 0 이라는 것은 헤드노드의 넥스트노드가 아무것도 없다는 뜻입니다. 2016.04.10 20:36 신고 댓글 메뉴

몇개의 데이터를 insert했다고 가정해 보죠.
그림은 교수님께서 보여주셨듯이 ㅁ-ㅁ-ㅁ-ㅁ-ㅁ 처럼 데이터가 있고, 다음 노드의 주소가 저장된 포인터로 이어져 있다고 생각해 볼 수 있습니다.

이때에 우리가 LinearSearch(선형검색)을 진행한다고 가정합시다.
리스트에 저장된 데이터 중에서 어떤 데이터가 있는지 검색을 합니다.

헤드-방1-방2-방3-방4-꼬리
이런식으로 이름을 붙여서 생각해보겠습니다.
이때 숫자 3이 들어있는 곳을 찾으려고 이진 거래의 장점 합니다.

반복문은 다음과 같은 알고리즘을 거치게 됩니다.
헤드 너 3이니? 아니, 그럼 방1 네가 3이니? 아니, 그럼 방2 네가 3이니? .
이때 이런 index를 확인해야 하는데, 이걸 더미노드로 삼습니다. 즉 기존의 리스트는 건드리지 않고 Node*형 데이터를 하나를 만들고 head와 같은 곳을 가리키게 합니다.
새로 만든 임시 Node*의 이름을 pred라고 합시다.

pred = head; 이와 같은 코드를 통하여 헤드가 가리키는곳과 pred가 가리키는 곳의 주소를 같게 만들 수 있습니다.

이제 pred를 통해서 pred 너 3이니? 아니면 pred->next 너 3이니? 아니면 pred->next->next 너가 3이니? 하고 물어볼 수 있게 된것입니다.

무슨 말이냐면 기존의 head만 가지고 리니어서치를 하면 다음 노드로 이동하기위해 head가 바뀌면서 데이터가 꼬이게 되는데 head와 같은곳을 가리키는 포인터를 임시로 만들어서 사용함으로서 기존의 리스트는 건드리지 않고, 리니어서치를 할 수 있다는 뜻입니다. 복잡하게 설명한것 같은데 한번 잘 생각해보시고 이해가 안되는 점에 있어서 다시 질문해주시면 감사하겠습니다. 2016.04.10 20:44 신고 댓글 메뉴

마지막으로 링크드리스트 라는 자료구조는 다른 자료구조에 비해 포인터에 대한 충분한 이해를 필요로 하는 자료구조입니다. 포인터와 주소연산에 대해서 고민하시고 공부하시면 도움이 될 것입니다.

더미노드 pred나 pred의 next노드 등등 전부 포인터가 들어가는 부분이니까요.ㅎㅎ

설명이 충분했는지 모르겠습니다. 생각해보시고 설명이 부족한 부분에 대해서 피드백 주세요. 모니터링 하고 있으니 하루 안으로 답변 드리도록 하겠습니다. 2016.04.10 20:49 신고 댓글 메뉴

이진트리(Binary tree) - 트리(Tree)의 기초

그 중 부모노드의 부모노드의 . 부모노드 즉 최상단의 노드를 루트노드(root node)라고 한다.

또 그 중 자식이 없는 노드를 단말 노드(terminal node) 라고 한다.

트리안에 존재하는 트리를 서브트리(subTree)라고 한다.

트리의 높이를 측정하기 위해서 가장 최상단부터 레벨을 매겨 1, 2, 3, .

가장 높은 레벨이 트리의 높이이다.

사실 용어만 보고보면 어려운 이진 거래의 장점 것이 없고 익숙해지는 것이 가장 중요할 것 같다.

1. 이진트리(Binary tree) 아이디어

위에서 가볍게 정의한 트리 중 가장 쉬운 트리중에 하나 인 이진트리에 대해서 알아보자.

이진트리는 각 노드가 자식을 최대 2명 가지는 트리를 의미한다. 상당히 간단하다.

하지만 이런 이진트리에는 꾀나 문제점이 발생하게 된다.

이상적으로 이렇게 하나하나 꽉차게 트리가 구성이 된다면 아주 좋은 징조이다.

이렇게 자식이 2개고 꽉찬 트리를 완전이진트리라고 부른다.

이런 완전이진 트리는 각 레벨당 2의 (레벨-1)승(2^level-1)만큼 노드를 가지게 된다.

다른 난이도가 있는 트리들 중 상당수는 완전이진트리 처럼 양쪽의 균형을 맞추는 것을 잘하기 위해서 여러 알고리즘을 사용한다.

2. 이진트리 순회

이진트리를 만들었으면 트리에 뭐가있는지, 내가원하는 값이 있는지 확인해야한다.

이진트리의 경우 대표적인 순회 방법 3가지가 있다. 기준은 루트노드 기준이다.

2.1 전위순회(Preorder) - 루트 -> 왼쪽서브트리 -> 오른쪽 서브트리

2.2 중위순회(Inorder) - 왼쪽서브트리 ->루트 -> 오른쪽서브트리

2.3 후위순회(Postorder) - 왼쪽서브트리 -> 오른쪽서브트리 -> 루트

그림을 보면 쉽게 이해 할 수 있겠지만 보충설명을 하자면,

가장 처음에는 root노드인 1을 방문을 하게 된다.

그러면 왼쪽에는 2,4,5로 이루어진 서브트리와 오른쪽에는 3,6,7로 이루어진 서브트리가 존재한다.

우리의 순서는 [root -> 왼쪽 -> 오른쪽] 이다. 따라서 왼쪽서브트리로 이동한다.

왼쪽 서브트리로 이동을 하게 되면 2가 서브트리의 루트이고, 4가 왼쪽서브트리 5가 오른쪽 서브트리이다.

똑가시 왼쪽 서브트리로 이동하게 되고, 그 트리의 루트는 4이다.

이런식으로 그림과 같이 반복을 하게 되면 결국엔 모든 노드를 방문할 수 있게 된다.

과정을 이해하였다면, 전위,중위,후위순회 모두 다 재귀로 쉽게 구현 할 수 있다는 것을 알았을 것이다.

또한 추가적으로 전위,중위,후위 순회 중 한두개의 순회 결과를 주고 나머지 한개의 순회순서를 알아낼수 있는데

이것은 내용을 이해하였으면 쉽게 알수 있기 때문에 생략하겠다.

3. 이진트리 구현

이진트리에 대해 알아보았으니 코드를 필수적으로 구현할 줄 알아야 한다.

다른 여러 트리들이 최적화를 위해서 멋있는 스킬들을 사용해서 구현 할 수있지만,

구현할 이진트리의 경우는 쉽게 배열로 구현을 하여도 좋은 성능을 보일 수 있다. 물론 편향된 경우는 어쩔수 없지만.

가장 직관적으로 구현을 하기 위해서 배열의 0번째 칸은 비워두고 구현을 하였다.

잘 보게 되면 , 재밌는 특징이 있는데

자식으로 이동하기위해서는 자신의 인덱스 곱하기 2 를 하면되고,

자신의 부모로 이동하기 위해서는 자신의 인덱스 나누기 2를 하면 된다.

아주 간단한 구현이지만 소스코드는 첨부해 두었다. 간단하게 짯기 떄문에 제대로된 트리를 원한다면 다른 종류의 트리를 이용하는 것을 추천한다.

꿈꾸는 개발자의 블로그

목적 : 이진탐색 + 연결리스트 : 이 두가지를 합하여 장점을 모두 얻는 것이 이진탐색트리 이다.

- 이진탐색 : 탐색에 소요되는 시간복잡도는 O(logN), 삽입/ 삭제는 불가능

- 연결리스트 : 삽입 , 삭제의 시간복잡도는 O(1), 탐색하는 시간복잡도는 O(N)

시간 복잡도 : 삽입 및 삭제 , 탐색까지 이상적일 때는 모두 O(logN) 가능하지만, 만약 편향된 트리면 O(N) 으로 최악의 경우가 발생한다.

문제 : 편향된 트리 ( 정렬된 상태 값을 트리로 만들면 한쪽으로만 뻗음 ), 이를 바로 잡도록 도와주는 개선된 트리가 AVL, RedBlack 트리이다.

1. 높이 : logN
2. 각 노드의 자식이 2개 이하이다.
3. 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 크다.
4. 중복된 노드가 없어야 한다. (검색 목적 자료구조이기 때문에 굳이 중복이 많은 경우에 트리를 사용하여 검색 속도를 느리게 할 필요가 없음, 트리에 삽입하는 것보다 노드에 count 값을 가지게 하여 처리하는 것이 훨씬 효율적 )
5. 순회 방식 : 중위 순회로 정렬된 순서를 읽을 수 있다.

B Tree & B+ Tree

이진 트리는 하나의 부모가 두 개의 자식밖에 가지질 못하고 , 균형이 맞지 않으면 검색 효율이 선형검색 급으로 떨어진다 . 하지만 이진 트리 구조의 간결함과 균형만 맞다면 검색 , 삽입 , 삭제 모두 O(logN) 의 성능을 보이는 장점이 있기 때문에 계속 개선시키기 위한 노력이 이루어지고 있다 .

B Tree

데이터베이스 , 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해서 더 많은 수의 자식을 가질 수 있게 일반화 시킨 것이다. 자식 수에 대한 일반화를 진행하면서 , 하나의 레벨에 더 저장되는 것 뿐만 아니라 트리의 균형을 자동으로 맞춰주는 로직까지 갖추었다 . ( 단순하고 효율적이며 , 레벨로만 따지면 완전히 균형을 맞춘 트리)

대량의 데이터를 처리해야 할 때 , 검색 구조의 경우 하나의 노드에 많은 데이터를 가질 수 있다.

ex) 대량의 데이터는 메모리보다 블럭 단위로 입출력하는 하드디스크 or SSD 에 저장해야하기 때문이다. 한 블럭이 1024 바이트면 , 2 바이트를 읽으나 1024 바이트를 읽으나 똑같은 입출력 비용 발생 . 따라서 하나의 노드를 모두 1024 바이트로 꽉 채워서 조절할 수 있으면 입출력에 있어서 효율적인 구성을 갖출 수 있다 . B Tree 는 이러한 장점을 토대로 많은 데이터베이스 시스템의 인덱스 저장 방법으로 애용하고 있다.

1. 노드의 자료수가 N이면, 자식 수는 N+1이어야 한다.
2. 각 노드의 자료는 정렬된 상태여야한다.
3. 루트 노드는 적어도 2개 이상의 자식을 가져야한다.
4. 루트 노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야한다.
5. 외부 노드로 가는 경로의 길이는 모두 같다.
6. 입력 자료는 중복 될 수 없다.

B+ Tree

데이터의 빠른 접근을 위한 인덱스 역할만 하는 비단말 노드 (not Leaf) 가 추가로 있다. ( 기존의 B-Tree 와 데이터의 연결리스트로 구현된 색인구조 ) B-Tree 의 변형 구조로 , index 부분과 leaf 노드로 구성된 순차 데이터 부분으로 이루어진다 . 인덱스 부분의 key 값은 leaf 에 있는 key 값을 직접 찾아가는데 사용한다.

1. 블럭 사이즈를 더 많이 이용할 수 있다. (key 값에 대한 하드디스크 액세스 주소가 없기 때문)
2. leaf 노드끼리 연결 리스트로 연결되어 있어서 범위 탐색에 매우 유리하다.

1. B-tree의 경우 최상 케이스에서는 루트에서 끝날 수 있지만, B+tree는 무조건 이진 거래의 장점 leaf 노드까지 내려가봐야 한다.

B Tree & B+ Tree 차이점

B Tree 는 각 노드에 데이터가 저장된다.

B+ Tree 는 index 노드와 leaf 노드로 분리되어 저장된다. ( 또한 , 이진 거래의 장점 이진 거래의 장점 leaf 노드는 서로 연결되어 있어서 임의접근이나 순차접근 모두 성능이 우수함 )

B Tree 는 각 노드에서 key 와 data 모두 들어갈 수 있고 , data 는 disk block 으로 포인터가 될 수 있다.

B+ Tree 는 각 노드에서 key 만 들어감 . 따라서 data 는 모두 leaf 노드에만 존재한다.

B+ Tree 는 add 와 delete 가 모두 leaf 노드에서만 이루어진다.

힙 (Heap)

완전 이진 트리의 일종으로 여러 값 중 , 최대값과 최소값을 빠르게 찾아내도록 만들어진 자료구조이다.

힙 트리는 중복된 값 허용한다. ( 이진 탐색 트리는 중복값 허용 X)

• 최대 힙(max heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• 최소 힙(min heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

힙을 저장하는 표준적인 자료구조는 배열로써, 구현을 쉽게 하기 위해 배열의 첫번째 인덱스인 0 은 사용되지 않는다.

특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.

(ex. 루트 노드 (1) 의 오른쪽 노드 번호는 항상 3)

부모 노드와 자식 노드 관계

1. 힙에 새로운 요소가 들어오면 , 일단 새로운 노드를 힙의 마지막 노드에 삽입한다.

2. 새로운 노드를 부모 노드들과 교환한다. 부모 노드는 자신의 인덱스의 /2 이므로 , 비교하고 자신이 더 크면 swap 하는 방식이다.

Kim's Programming

이진트리의 모든 노드는 왼쪽 자식노드와 오른쪽 자식 노드를 가집니다. 자식노드는 최소 0개부터 최대 2개 까지 가질 수 있습니다.

이진 트리 (Binary Tree) - 특성

이진트리는 노드의 개수가 n개일때 n-1개의 간선의 개수를 가지게 됩니다. root를 제외한 (n-1)개의 노드가 부모 노드와 연결되는 한개의 간선을 가지기 때문에 이런 결과가 나오게됩니다.

또한 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 h+1개가 이진 거래의 장점 되며, 최대 개수는 (2^(h+1)) + 1개가 됩니다.

최소 노드 개수 : 이진 트리 높이가 h가 되려면, 한 레벨에 최소한 한 개의 노드가 있어야 하기 떄문에 h+1개가 나오게 된다.

추가로 왼쪽에 있는 트리를 지칭해서 편향 이진 트리(skewed binary tree) 라고 하며 오른쪽에 있는 트리를 포화 이진 트리 라고 합니다.

n개의 노드를 가지는 이진트리의 높이의 최대값은 n-1개가 되며 최소는 이 됩니다.

이진 트리 (Binary Tree) - 이진 트리의 분류

위 그림에서 왼쪽부터 포화이진트리, 완전이진트리, 기타이진트리라고 부릅니다.


포화이진트리 : 모든 단말 노드가 같은 레벨에 있으며, 모든 중간 노드는 두 개의 자식노드를 가지는 경우를 의미

• 단말 노드의 수가 n일때 전체 노드의 수 N = 2n -1개
• 아래와 같이 각 노드에 번호를 붙일 수 있음.
  
• 완전이진트리 : 위에서 아래로 왼쪽에서 오른쪽으로 순차적으로 채워가는 트리

• 마지막 레벨을 제외하고 포화 이진 트리이며, 최하위 레벨의 단말 노드들은 왼쪽에서부터 채워진 형태로 되어 있는 경우를 의미
• 중간 노드의 자식 수가 2일 때, 단말 노드의 수가 n이면, 전체 노드 수는 N = 2n-1개가 됨
• 완전 이진트리 또한 포화 이진트리와 노드 번호와 일치합니다.

이진 트리 (Binary Tree) - 이진 트리의 구현 - 배열


이진트리는 다음과 같은 구조를 가지게됩니다.

이진 트리는 순환적 구성을 가지기 때문에 재귀함수로 구현이 가능합니다. 노드의 왼쪽 자식을 루트로 했을때도 트리 오른쪽 자식 노드를 루트로 해도 트리인 것이 그 이유입니다.


트리구현은 배열로도 할 수 있고 동적으로도 할 수 있는데 배열기반을 먼져 해보겠습니다. 트리를 배열로 구현할 때는 1차원 배열을 이용하며 트리의 노드번호들이 배열의 인덱스 번호와 일치하게 만듭니다.


코드 연구소

[자료구조] 이진탐색트리(Binary Search Tree)의 개념, 이해 | C언어 이진탐색트리 구현

• 코드연구원
• Computer Science/[자료구조]
• 2021. 7. 20.

이진탐색트리(Binary Search Tree)이란?

이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. ( #이진트리 - 각 노드의 자식 노드가 최대 2개인 트리)

1. 각 노드에 중복되지 않는 키(key)가 있다.
2. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다.
3. 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다.
4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다.

예를 들어 다음과 같은 트리가 이진탐색트리이다.



이진탐색트리

이진 탐색 트리의 특징

이진 탐색 트리는 기존 이진트리보다 탐색이 빠르다. 이진 탐색 트리의 탐색 연산은 트리의 높이(height)가 h라면 O(h)의 시간 복잡도를 갖는다. 이러한 효율적인 탐색이 가능한 이유는 탐색 과정에서 자세히 알아보자. 혹시라도 트리에 관한 용어가 헷갈린다면 다음 포스팅을 참고하자.

[자료구조] 트리(Tree)의 개념, 이해, 종류 | 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진

트리(Tree)의 개념 트리는 노드로 이루어진 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계를 표현하는 자료구조이다. 트리는 다음과 같은 특징들을

이진 탐색 트리 탐색(Search)

이진 탐색 트리의 탐색은 다음과 같은 과정을 거친다.

1. 루트 노드의 키와 찾고자 하는 값을 비교한다. 찾고자 이진 거래의 장점 하는 값이라면 탐색을 종료한다.
2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행한다.
3. 찾고자 하는 값이 루트노드의 키보다 크다면 오른쪽 서브트리로 탐색을 진행한다.

위 과정을 찾고자 하는 값을 찾을 때까지 반복해서 진행한다. 만약 값을 찾지 못한다면 그대로 종료한다.

이러한 탐색 과정을 거치면 최대 트리의 높이(h)만큼의 탐색이 진행되게 된다. 예를 들어보자.



탐색과정

위와 같은 트리에서 키가 5인 노드를 찾고자 한다면, 가장 먼저 루트 노드와의 비교가 이루어진다.

5가 7보다 작으므로 왼쪽 서브 트리로의 탐색이 이루어지고, 이후 5가 3보다 크므로 오른쪽 서브트리로 탐색이 이루어진다. 마지막으로 키가 5인 노드를 찾았으므로 탐색이 종료된다. 즉 트리의 높이인 3번 만큼의 탐색이 이루어졌다. 만약 8을 찾는다면 2번의 연산이 진행되었을 것이다. 즉, 트리 안의 값을 찾는다면 무조건 트리의 높이(h) 이하의 탐색이 이루어지게 된다.

트리 안에 찾고자 이진 거래의 장점 하는 값이 없더라도 최대 h 번 만큼만의 탐색이 진행된다. 예를 들어 위 트리에서 6이라는 값을 찾는다고 하면 위 그림과 같은 과정을 거치고 탐색이 종료된다. (직접 위 그림에서 과정을 생각해보자) 마지막으로 탐색하게 되는 5를 키로 갖는 노드에서 6은 5보다 크므로 오른쪽 서브트리로 탐색을 진행해야 하는데 오른쪽 서브 트리가 없으므로 탐색이 종료되는 것이다.