알고리즘 학습

6장. 이진 트리:손 안의 무한대

이 작품은 AI를 사용하여 번역되었습니다. 여러분의 피드백과 의견을 환영합니다: [e-mail]

이 장에서는 학습 내용을 살펴봅니다:

• 값을 삽입, 제거, 검색하여 이진 트리를 만들고 조작하는 방법을 알아봅니다.

• 전역 속성을 적용하는 이진 검색 트리를 관리하는 방법을 알아보세요:

  • 노드의 왼쪽 하위 트리에 있는 값은 모두 해당 노드의 값보다 작거나 같습니다.

  • 노드의 오른쪽 하위 트리에 있는 값은 모두 해당 노드의 값보다 크거나 같습니다.

• 이러한 검색, 삽입, 제거 작업은 균형 잡힌 이진 트리에서는 O(log N)이 될 수 있지만 주의하지 않으면 허용할 수 없는 O(N)으로 저하될 수 있습니다.

• 삽입 및 제거 작업 후 이진 검색 트리의 균형을 재조정하여 검색, 삽입 및 제거에 대해 O(log N) 성능을 보장하는 방법을 알아보세요.

• 이진 검색 트리를 트래버스하여 각 값을 오름차순으로 처리하는 방법을 O(N) 성능으로 설명합니다.

• 이진 트리 구조를 사용하여 키를 정렬된 순서대로 검색할 수 있다는 추가적인 이점이 있는 심볼 테이블 데이터 유형을 구현하는 방법.

• 이진 트리 구조를 사용하여 우선순위 큐를 구현하는 방법 우선순위 큐를 방해하지 않고 우선순위 순서대로 (키, 값) 항목을 생성할 수 있다는 추가적인 이점이 있습니다.

시작하기

링크된 목록과 배열은 정보를 선형 배열로 저장합니다. 이 장에서는 컴퓨터 과학 분야에서 가장 중요한 개념 중 하나인 이진 트리 재귀 데이터 구조에 대해 소개합니다. 5장에서는 함수가 스스로를 호출하는 재귀의 개념에 대해 배웠습니다. 이 장에서는 이진 트리가 재귀적 데이터 구조,즉 다른 이진 트리 구조를 참조한다는 것을 배우게 됩니다. 재귀 데이터 구조의 개념을 소개하기 위해 이미 살펴본 링크된 목록 데이터 구조를 다시 살펴보겠습니다.

링크된 목록은 각 노드가 하위 목록의 첫 번째 노드에 대한 next 참조를 가지고 있기 때문에 재귀 데이터 구조의 한 예입니다. 연결된 목록은 N 값 컬렉션의 동적 증가 및 감소를 지원함으로써 고정 길이 배열을 개선합니다. 목록 6-1에 표시된 sum_list() 재귀 함수는 연결된 목록을 처리하여 그 합계를 반환합니다. 이 함수의 구현을 기존의 반복 솔루션과 비교해 보세요.

목록 6-1. 연결된 목록의 값을 합산하는 재귀 및 반복 함수

class Node:
  def __init__(self, val, rest=None):
    self.value = val
    self.next = rest

def sum_iterative(n):
  total = 0                         
  while n:
    total += n.value                
    n = n.next                      
  return total

def sum_list(n):
  if n