이진트리, 힙, 이진탐색트리 삽입삭제 정리다

이진트리에서는 그냥 단순히 특정 노드 아래에 삽입을 하면되는데..삭제도 마찬가지 자식들 관리만 잘하면됨

힙에서는 삽입할때 완전 이진트리의 형식으로 마지막 위치에 삽입하고 WALKUP을 한다. 부모와 비교하면서 올라가면됨

삭제역시 루트 노트를 지우고? 가장 마지막 노드를 루트에 넣고 WALKDOWN을 한다.

이진탐색트리는 삽입할때 루트에서부터 검색을 시작한다 (자신이 들어갈 위치를 검색함) 같은값이 있으면 안됨..

삭제는 좀 복잡함.

1) 자식 노드가 없으면 그냥 노드 삭제 부모 연결관리만 해주면됨

2) 자식 1개라면 삭제하고 자식 링크릉 부모의 다음 링크로 연결(현재 삭제되는 자신의 위치)

3) 자식이 2개라면 

1: 왼쪽에서 가장 큰 자식 2: 오른쪽에서 가장 작은 자식 을 찾는다 보통 1번을 함

그리고 그 삭제된 노드의 위치로 옮긴다. 근데 기존에 있는 그 왼쪽에서 큰 자식의 노드에서  왼쪽 자식이 있을 수도 없을 수도 있는데

있다면 교체된 자신의 위치로 옮겨준다.