1
밸런스 된/완전한 이진 트리를 생성하기 위해 바인딩되는 정수의 입력 패턴이 있습니까?균형 이진 검색 트리를 생성하기위한 입력
A
답변
2
길이가 n 인 a - 정렬 된 입력 배열을 예로 들어 보겠습니다. 그런 다음 a[mid]으로 BST를 시작하십시오. mid - 중간 요소 (n/2). 일단 우리가 a[mid]을 BST에 푸시하면 우리 배열은 두 개의 새로운 정렬 된 배열 : [0 : mid-1]과 [mid +1, n-1]로 나뉘어집니다.
둘 다 동일한 논리를 사용하십시오 (하위 배열이 비어 있지 않은 경우). 각 하위 배열에 대해 새 mid 요소를 선택하고 BST로 푸시합니다. 그러면 4 개의 새로운 배열이 생성됩니다.
모든 하위 배열에 대해이 프로세스를 완료하면 해당 입력에 대해 가장 균형 잡힌 BST를 얻을 수 있습니다.
관련 문제
- 1. 균형 이진 검색 트리
- 2. 균형 이진 검색 트리의 정의
- 3. 이진 검색 트리 균형
- 4. Lisp에서 이진 트리를 검색
- 5. 정수 스트림에서 균형 이진 검색 트리 만들기
- 6. Backtrcking이있는 균형 이진 검색 트리
- 7. 균형 이진 검색 트리의 높이
- 8. 이진 검색 트리 균형 조정
- 9. 이진 검색 트리를 순차적으로 인쇄하기
- 10. 이진 검색 트리를 만드는 것은
- 11. 문자열과 이진 검색 트리를 생성
- 12. 이진 트리를 균형 잡히기 위해 추가해야하는 노드의 최소 수 찾기?
- 13. 순서 제약없이 균형 잡힌 이진 트리를 점진적으로 구축하기위한 알고리즘은 무엇입니까?
- 14. 균형 이진 검색 트리의 상각 된 복잡도
- 15. 비효율적 인 이진 검색 트리 균형 알고리즘
- 16. 또한 힙인 균형 이진 검색 트리
- 17. 완전히 균형 잡힌 이진 검색 트리가 될 요소 삽입 순서?
- 18. 사전 구현 (이진 검색 트리 vS. 해시 테이블 균형)
- 19. Java를 사용하여 균형 이진 트리를 만드는 중 오류가 발생했습니다
- 20. 이진 검색 트리를 기반으로 배열에 요소 추가
- 21. C++ 전체 이진 검색 트리를 삭제합니다.
- 22. Java : 이진 검색 트리를 문자열로 변환하는 방법
- 23. 이진 검색 트리를 인쇄하는 방법은 무엇입니까?
- 24. 이진 검색 트리를 시각화하기위한 그래픽 라이브러리
- 25. 알고리즘에서 이진 검색 트리를 호출하는 방법
- 26. 침입 형/이진 검색 트리를 부스트
- 27. 초보자 구성표 : 이진 검색 트리를 목록으로 바꾸기
- 28. 은 파이썬에서 이진 검색 트리를 나타냅니다.
- 29. 자바의 연결 목록으로 이진 검색 트리를 변환하십시오.
- 30. 일반 트리에서 이진 검색 트리를 만드는 방법
그래, 그렇다고해서 재귀 적으로 노드를 추가하도록 BST의 삽입 기능을 수정해야합니다. 데이터 구조 구현을 변경하지 않고 균형 잡힌 BST를 산출 할 입력 시퀀스를 찾고있었습니다. –
@HaseebJaved 삽입 기능을 변경해야한다는 것은 아닙니다. 정렬 된 배열에서 BST를 작성하는 함수를 추가하기 만하면됩니다. 그 후 다른 요소를 추가하려면 일반 삽입 기능을 사용하십시오. –
@ A. 충분한 공정한. 하지만 BST에 삽입 할 때 균형 잡힌 BST를 생성 할 수있는 시퀀스 패턴이 없다는 것을 의미합니까? 즉, 도우미 기능을 사용하지 않고? –