leetcode 트리 두 갈래 검색 트리 균형 두 갈래 트리 제목 총결산
4178 단어 학습 노트
나무가 두루 다니다
중, 후, 앞 순서 반복 문제, n갈래 나무, 두 갈래 나무의 반복 차원 반복(간단)(주로 비귀속 해법 복습)
두 갈래 검색 트리
배운 새로운 지식
모리스의 차례차례
모리스의 순서는 먼저 명확하다. 두 갈래 검색 트리에서 만약에 하나의 결점에 선구 결점이 있다면 선구 결점의 오른쪽 바늘은 두 가지 경우만 비어 있다. 이 결점 자체(즉 선구는 그의 부결점)이기 때문에 우리는 선구 결점의 오른쪽 바늘이라는 특성을 이용하여 공간의 복잡도를 낮출 수 있다
Morris 스트리밍 알고리즘의 단계는 다음과 같습니다.
현재 결점을 검사하는 왼쪽 아이:
현재 결점의 왼쪽 아이가 비어 있으면 선구가 없거나 선구가 아버지의 결점이기 때문에 검사를 하고 오른쪽 아이로 들어간다.만약에 현재 결점의 왼쪽 아이가 비어 있지 않으면 왼쪽 나무에 틀림없이 그 전구가 있다는 것을 의미한다. 그러면 이 전구를 찾아라. 만약에 전구 결점의 오른쪽 아이가 비어 있다면 아직 왼쪽 나무를 검사하지 않았다는 것을 설명한다. 그러면 전구 결점의 오른쪽 아이를 현재 결점을 가리키고 현재 결점의 왼쪽 아이로 들어간다.만약에 현재 결점의 전구 결점이 오른쪽 아이가 그 자체를 가리키고 왼쪽 나무가 검사되었다는 것을 설명한다면 직접 검사를 한 다음에 전구 결점의 오른쪽 아이를 비워 원래의 나무를 회복하고 오른쪽 아이로 들어간다.
반복 과정에서 각 노드는 최대 두 번, 한 번은 부모 노드에서 현재 노드로, 두 번째는 접두사 노드의 오른쪽 아이 바늘에서 현재 노드로 되돌아오기 때문에 모리스 반복 알고리즘의 복잡도는 O(n)이다.반복 과정에서 새로운 메모리를 신청하지 않았기 때문에 알고리즘의 공간 복잡도는 O(1)이다.
평형 두 갈래 나무
DFS 깊이 우선 순위 검색
C++에서 find() 함수 사용
//find() ，
find(track.begin(), track.end(), nums[i]) == track.end()
C++ std::unordered_맵 사용법
용기에서 키 값이 k인 요소를 검색하고 찾으면 이 요소를 가리키는 교체기를 되돌려줍니다. 그렇지 않으면 unordered_map::end의 교체기.
동적 계획
탐욕 알고리즘
윈도우
기타:
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
STL 학습노트(6) 함수 객체모방 함수는 모두pass-by-value이다 함수 대상은 값에 따라 전달되고 값에 따라 되돌아오기 때문에 함수 대상은 가능한 한 작아야 한다(대상 복사 비용이 크다) 함수 f와 대상 x, x 대상에서 f를 호출하면:...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
