고전 정렬 알고리즘python 회고의 네 갈래 찾기 트리 정렬
2111 단어 python두 갈래 찾기 트리 정렬
두 갈래 찾기 트리 정렬
소개
두 갈래 찾기 트리는 질서정연한 두 갈래 나무라고도 하는데, 두 갈래 나무를 정렬하는 것은 빈 나무 또는 아래의 성질을 가진 두 갈래 나무를 가리킨다.
두 갈래 검색 트리 정렬은 삽입 정렬 클래스에 속합니다. 우리는 검색 트리의 구축, 삽입 (즉 정렬 과정) 과 관련됩니다.
한 조의 수치에 대해 두 갈래 찾기 트리를 구성하는 동시에 이 조의 수치를 정렬시켰다.최악의 시간 복잡도는 O(n^2)이다.예를 들어 이 그룹의 수치가 이미 작게부터 큰 순서까지 정해져 있다면, 구조된 두 갈래 찾기 트리의 모든 노드에 왼쪽 트리가 없습니다.균형 두 갈래 찾기 트리는 상술한 단점을 극복할 수 있으며 시간 복잡도는 O(nlogn)이다.그러나 트리 정렬의 문제는 CPU Cache의 성능이 좋지 않다는 것이다. 특히 노드가 동적 메모리 분배일 때.정렬된 CPU Cache는 성능이 좋습니다.다른 한편, 트리 정렬은 가장 좋은 증량 정렬 (incrementalsorting) 알고리즘으로 하나의 수치 정렬의 질서성을 유지한다.
각 결점의 Ci는 해당 결점의 레이어 수입니다.최악의 경우 선후로 삽입된 키워드가 질서정연할 때 구성된 두 갈래 찾기 트리는 단일 트리로 탈바꿈하고 나무의 깊이는 n이며 평균 찾기 길이는 (n+1)/2(순서 찾기와 동일), 가장 좋은 상황은 두 갈래 찾기 트리의 형태와 반절절 찾기 판정 트리가 같고 평균 찾기 길이는 log2(n)와 정비례 O(log2(n)가 된다.
python 코드
class empty_node:
def __init__(self):
self.flag = 1
class binary_tree:
def __init__(self, value):
self.data = value
self.flag = 0
self.left = empty_node()
self.right = empty_node()
def insert_node(self, value):
if value < self.data:
if self.left.flag:
self.left = binary_tree(value)
else:
self.left.insert_node(value)
elif value > self.data:
if self.right.flag:
self.right = binary_tree(value)
else:
self.right.insert_node(value)
def LDR(bt):
out_list = []
if bt.left.flag:
out_list.append(bt.data)
if not bt.right.flag:
output(bt.right)
elif not bt.left.flag:
output(bt.left)
out_list.append(bt.data)
if not bt.right.flag:
output(bt.right)
return out_list
def BTS(list):
bt = binary_tree(list[0])
for i in list[1:]:
bt.insert_node(i)
return LDR(bt)
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
로마 숫자를 정수로 또는 그 반대로 변환그 중 하나는 로마 숫자를 정수로 변환하는 함수를 만드는 것이었고 두 번째는 그 반대를 수행하는 함수를 만드는 것이었습니다. 문자만 포함합니다'I', 'V', 'X', 'L', 'C', 'D', 'M' ; 문자열이 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
