이진 트리(Binary Tree) - 이진 트리?

안녕하세요...늦어서 죄송합니다 테슬라입니다.
모종의 사유로 인해 이제서야 글을 올리게 되었네요.
오늘은 이진트리에 대하여 글을 쓰고자 합니다.

우선 이진트리가 무엇일까?
음 저번시간에 트리에 대해서 했죠?
음 부모에서 자식으로 노드가 연결되는 것이였지요?
일단 트리의 기본 법칙은 거의 그대로 갑니다.
하지만 이진트리는 0개이상의 노드들의 유한집합으로 된 루트라는 특벽한 노드가 있고,
나머지 노드들은 각각 교차하지 않는 2개의 분리집합으로 분할된다는 것이지요
음 분리집합이 언제나 2개로 나뉘는거랑 공집합일 수 점을 빼면 같은 내용입니다.
무슨말인고 하니 부모에서 자식으로 갈때 최대 2개까지 연결될 수 있는것이 이진노드입니다.
음...음...간단한걸까요?

뭐 이런거지요 음 이 이상으로 형제 노드가 생길수 없습니다. 그렇다면

이런식의 노드도 이진 노드일까요?
네 맞습니다. 이진노드입니다. 단지 한쪽 방향으로만 연결 되어있는 것뿐이지요.
좀 있다가 나오겠지만 이런 이진트리를 사향이진트리라고 하지요.
아 이진트리는 자식노드의 순서를 구별합니다. 뭐 이건 다음에 말씀드리겠습니다.
 
자 지금부터 여러가지 이진트리의 종류에 대해서 말해볼까요?
우선 포화이진트리(Full Binary Tree)라는 것이 있습니다.
이건 말그대로 꽉 차있는 상태, 즉 모든 레벨의 노드가 꽉 차있는 상태의 트리를 말합니다.

으아 그리기 귀찮았어요.
암튼 이런식으로 꽉꽉 차있는 이진트리를 말하는 것이지요
음 이것들은 1-> 2-> 4-> 8-> 16->...
이런식으로 노드가 증가합니다.
때문에 각 레벨에서는 2^(n-1)개이고 그 레벨까지는 2^n-1개의 노드들을 가집니다.
예를 들어 2레벨 까지라면 2^2-1=3개, 4레벨은 2^4-1=15
뭐 이런식이지요.

음 다음으로는 완전이진트리(Complete Binary Tree)가 있습니다.
이거는 포화이진트리처럼 마지막 레벨의 노드가 완벽하게 꽉꽉 차있지는 않더라도
대충 어느정도는 차례대로 채워져있는 형태의 트리를 말합니다.
몇 개씩 빠진다고 뭐라고 할 정도는 아니라는 것이지요.

뭐 이런식으로 대충 채워져있으면 완전이진트리라고 할수 있습니다.
음 포화이진트리는 완전이진트리라고 할수 있겠지요.
마지막레벨에 꽉차있는 형태의 완전이진트리라고 할수 있으니까요.
하지만 반대로는 안되겠지요?
완전이진트리는 마지막 레벨에 하나 있는거부터 꽉 차있는 거 까지니까
(2^(n-1)-1)+1 ~ (2^n-1)까지 라고 할 수 있겠죠?

음 마지막으로 아까 말했던 사향이진트리(Skewed Binary Tree)라는게 있는데요
뭐 이진트리인 주제에 한쪽방향으로만 모든 노드가 쏠려있는 모양이 되는 것 이지요.

이런 모양이지요 이러면 나중에 이진검색트리에서 나오겠는데요. 이진트리의 장점이 없어지는 결과를 가지지요.
뭐 이건 링크드리스트같은 모양이 되지요. 검색시간도 링크드리스트 같이 걸리게 됩니다.
이 이야기는 이진검색트리 할 때 다루도록 하겠습니다.
암튼 이진트리를 만들때에는 사향트리가 되지 않도록 조심해야 합니다.