균형 이 잡 힌 이 진 트 리 의 c 언어 구현

밸 런 스 이 진 트 리
우선 이 나 무 는 매우 간단 하 다.
대충 설명 하 자 면 이 나무의 가장 기본 적 인 조작 은 LL 과 RR 두 개의 단일 회전 함수 인 데 이 두 함수 와 링크 의 삽입 함수 가 매우 비슷 하 다.이 두 함 수 는 명심 해 야 한다.
그 다음은 LR 과 RL 두 개의 쌍 회전 함수 입 니 다. 마음속 에 이 두 나무의 모양 을 그 려 야 합 니 다. 이렇게 LL 을 호출 하 는 지 RR 을 사용 하 는 지 잘 알 수 있 습 니 다.
1. 추가 삭제 노드 를 진행 할 때 이 진 트 리 알고리즘 과 일치 합 니 다. 좌우 서브 트 리 의 높이 를 한 단계 더 판단 하고 규격 에 맞지 않 는 트 리 의 단일 회전 또는 더 블 회전 을 하 며 높이 를 업데이트 하 는 것 이 관건 입 니 다.
2. LL 함수 와 RR 함수 의 마지막 부분 에 고도 의 작업 을 추가 해 야 합 니 다.
3. 삭제 노드 는 검색 트 리 와 일치 합 니 다. 트 리 를 찾 으 면 왼쪽 트 리 의 최대 또는 오른쪽 트 리 를 최소 로 삭제 할 수 있 습 니 다. 그러나 균형 트 리 는 더 큰 하위 트 리 에서 삭제 해 야 합 니 다. (균형 을 맞 추기 위해 서 는 삭제 하지 않 으 면 루트 노드 orz 를 바 꿔 야 합 니 다)증가 하 는 노드 는 반드시 잎 노드 입 니 다. 이것 은 검색 트 리 와 같 습 니 다.
다음 코드:
4. 567913. 도 망 갔 어 요. dota 를 때 리 러 갔 어 요.