이진검색트리,이진삽입트리, 이진트리 정렬

이진트리(바이너리트리)를 이용하여 검색하는 방법 O(logN) 의 성능 : 성능이 괜챃다

이진검색트리는 이진트리(바이너리트리)를 이용한 검색 방법

조건 Heap 은 부모노드가 두개의 자식노드보다 커야 하지만

1.이진검색트리는 부모노드는 왼쪽 sub-tree 의 모든 노드보다 크고

2.부모노드는 오른쪽 sub-tree 의 모든 노드보다 작아야 한다

재귀적으로 모든 조건을 만족해야 한다

그랫 In-Order Traversal 하면 정렬된 순서가 된다 (왼쪽 부모, 오른쪽 노드순으로 방문)

트리는 부모가 양 자식노드의 포인터를 가지고 있는 상태

검색

1.. 루트부터 검색 시작

2. 각 노드와 찾을 값을 비교해가면서 노드에서 좌측은 작고 우측은 큰것이기 때문에 키값이 같을때까지 비교를 반복해간다

=> 조건에 따라 자식 포인터를 타고 계속 내려간다 키를 찾을때까지

마지막 까리 노드까지 내려가서 찾지 못하면 fail

삽입

루트부터 비교를 하면서 새로운 노드는 항상 leaf 에 배치한다

(이때 트리 구조상 부모가 자식을 가르키고 있어야 함으로

포인터를 두개를 두어 이전 포인터 값을 유지하고 있어야 한다

하나는 현재 노드 하나는 이전노드를 가르키는 포인터)

또한 마지막 노드의 왼쪽 오른쪽에 들어가야 하므로

부모노드를 저장하고 있는 포인터가 P 였고 P 의 오른쪽에 노드가 추가 되어야 한다면

P 의 Right 에 노드 하나가 추가 되면서 추가된 노드 또한 아무것도 가르키고 있지 않은 포인터 두개(자식2개) 를 갖는 노드가 되어

추가 되어야 한다

삭제

삭제를 하고도 이진트리의 조건에 맞아야 한다

마지막 노드는 그냥 삭제 하면 되지만 중간에 잇는 노드를 삭제할때는

자신보다 작은 노드중 최대노드 또는

자신보다 큰 노드중 최소 노드를 선택

선택 방법은 부모 노드에서 왼쪽은 모두 부모모다 작은 것임으로

자신보다 작은 노드중 최대노드는 부모에서 왼쪽으로 한번갔다가 오른쪽으로 쭉 가는 순서

=>부모의 왼쪽 트리중에서(부모제외한) 중위순회를 해서 제일 마지막에 나오는 노드가 작은것중에 큰것

자신보다 큰 노드중 최소 노드는 부모를 제외한 오른쪽 노드트리에서 중위순회를 하여 가장 첫번째 나오는 것이

부모를 제외한 오른쪽 노드트리에서 가장 작은 값이다

...자식의 자식에 대한 처리 이하 생략..

---

이진 트리는 좌우로 균형이 맞을때 성능이 가장 좋다

입력 순서가 중요하다,

만약 정렬된 순서(순차 or 역순)로 입력이 될 경우 링크드리스트 처럼 입력이 될 수 있다 => 최악의 경우로 가게 된다

find, insert 최악의 경우 O(N), 균형이 맞으면 O(logN)

remove O(logN) => 삭제할때 insert 시 O(N)의 성능을 가져도 노드끼리의 포인터 연결이 간단해 짐으로 결론적으로 O(logN) 의 성능을 가짐

insert, find, remove 평균적으로는 O(logN) 의 성능을 갖는다

결국 트리의 균형을 맞추는 것이 중요하다 그래서 Balanced Tree 가 많이 연구됨

그래서 이진트리의 삽입을 개선한다

---

이진트리를 중위순회 하면 정렬된 순서가 나온다

자료가 균형에 맞게 대강 들어가는데 O(NlogN)의 성능을 갖는다

하나가 insert 되는데 logN 이 걸림으로 N 개의 자료에 대해 걸쳐 수행하는 것이니 N*logN

그런데 정렬된 순서나 역순이면 최악의 성능 O(N^2) 의 성능을 가진다

---

[이진트리 균형 맞추기]

정렬된 데이터를 배열로 가지고 있고 이것을 이진트리에 저장하려고 할때

트리를 중위순회 방식으로 순회하면서 트리를 생성할때 중위순회시 데이터를 노드에 저장하면 한쪽으로 치우친 형태가 아닌

균형이 맞는 balance 형태의 트리로구성할 수 있다

- 성능이 않좋을때 balance 로 균형을 한번 맞춰준다

---

중복키 문제

이진트리는 중복키에 대해서 제대로 처리 하지는 못하는데 이걸 해결 하기 위해 링크드 리스트와 바이너리 리스트를 결합해 해결한다

중복되는 키를 가지고 있는 노드에 대해서 링크드 리스트를 두어 링크드 리스트 뒤에 넣어주는 식으로 해놓고

키에 대해서 next 를 호출하면 중복된 키들의 첫번째에서 두번째로 이동하여 해당 데이터를 리턴

---

이진트리 특징

all nodes in left subtree < parent < all nodes in right subtree

성능이 트리의 균형에 좌우된다