[자료구조]이진탐색트리

이진 탐색 트리

이진 탐색 트리는 이진트리와 다르게 저장 규칙이 있기 때문에 이진 탐색 트리이다

저장규칙

• 이진 탐색 트리의 노드에 저장된 키는 유일
• 루트 노드의 키가 왼쪽 서브 트리를 구성하는 노드의 키보다 크다
• 루트 노드의 키가 오른쪽 서브 트리를 구성하는 노드의 키보다 작다
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다

즉 루트 노드 키보다 작으면 왼쪽 크면 오른쪽

 

이진 탐색 트리 구현

기존 이진 트리를 활용해서 구현하다

 

삽입, 탐색 연산

 

삽입 :

1. 새로운 노드가 추가될 위치를 찾는다
2. 중복을 검사
3. 새 노드를 생성
4. 찾은 위치에 노드 삽입

탐색 : 

1. 현재 노드 데이터와 타겟 데이터를 비교
2. 타겟 데이터 크다면 현재 노드를 오른쪽 서브트리로 작다면 현재 노드를 왼쪽 서브트리로
3. 반복해서 타겟데이터를 찾으면 retrun 없으면 undefined

 

 

 

삭제 연산

 

삭제 연산 같은 경우 삭제 할 때 경우에 수가 많아 그 만큼 처리 해줘야 한다

총 세가지의 경우가 있는데 삭제를 해도 이진 탐색 트리가 유지 되어야 하기 때문에 삭제 연산은 매우 복잡하다

 

삭제 : 삭제할 노드가 단말 노드인 경우, 삭제할 노드가 하나의 자식 노드를 갖는 경우, 삭제할 노드가 두 개의 자식 노드를 갖는 경우

 

먼저 클래스 내부에 왼쪽 서브트리를 삭제하는 함수,

오른쪽 서브트리를 삭제하는 함수,

위 함수들을 활용해서 target 값이 들어왔을 때 그 노드를 삭제하는 함수를 추가한다

 

최초 target 값을 가진 노드를 찾아 현재 노드에 저장한다

 

1. 삭제할 노드가 단말 노드인 경우
   
   1. target과 일치하는 현재 노드에 서브트리가 있는지 확인
   2. 없으면 삭제할 노드가 부모노드의 왼쪽 인지 오른쪽 인지 확인해서 삭제한다
2. 삭제할 노드가 하나의 자식 노드를 갖는 경우
   1. target과 일치하는 현재 노드에 서브트리가 있는지 확인
   2. 하나라도 있는지 확인이 되면 왼쪽인지 오른쪽인지 확인후 삭제할 노드의 자식노드로 저장
   3. 삭제할 노드의 부모노드와 삭제할 노드의 자식노드를 이어 준다
3. 삭제할 노드가 두 개의 자식 노드를 갖는 경우(제일 복잡하다)
   1. 루트 노드가 삭제대상일 경우가 있으니 가상 노드를 만들어 루트노드로 만든다
   2. 삭제할 노드의 오른쪽 서브트리를 대체 노드로 저장(오른쪽 서브트리의 제일 작은 값으로 대체하기 위해서)
   3. 대체 노드의 제일 작은 값으로 삭제할 노드를 대체해야 하기 때문에 대체 노드의 왼쪽 서브트리가 존재 하지 않을때 까지 계속 내려간다 대체노드와 대체노드의 부모노드 같이 내려간다
   4. 왼쪽 서브트리가 undefined 이면 대체노드의 값을 삭제할 노드에 대입한다
   5. 대체노드가 삭제할 노드에 올라가있으니 대체노드는 삭제해도 되기 때문에 대체노드의 오른쪽 서브트리와 대체노드의 부모노드와 연결한다
   6. 삭제하기 어려운 삭제할 노드를 삭제하지 않고 대체할 노드를 찾아 값을 대입해 삭제하기 쉬운 대체노드를 삭제했다

 

typescript 

기존 이진트리 코드에서 추가된 내용