이진 트리 챌린지 예제

Question

나는 우수한 Richard Buckland에서 몇 가지 강의를 보았고 이진 트리를 실험했지만 완전히 구현하는 방법을 완전히 이해하지 못했습니다. 아래는 제가 가진 것입니다.

class Tree(object): 
    def __init__(self, val, left=None, right=None): 
     self.val = val 
     self.left = left 
     self.right = right 

t = Tree(4, Tree(2, Tree(1), Tree(3)), Tree(6, Tree(5), Tree(7))) 

누군가 이진 트리를 사용하여 해결할 수있는 간단한 예제 문제를 참조 할 수 있습니까? 나는 나무를 만들기 위해 어떤 자료를 제시 할 것인지, 어떻게 실제로 사용할 수 있는지 이해하지 못합니다. 다른 누군가의 소스 코드를 원하지 않기 때문에 몇 가지 예를 들어 Google에 두려워합니다. 직접 구현을 해보고 싶습니다.하지만 이렇게하기 전에 해결해야 할 문제가 필요하다고 느낍니다. 이상적으로, 나는 한 쌍의 상당히 사소한 예제 문제와 몇 가지 중간 문제를 원한다. http://www.spoj.com/problems/THREECOL/

http://www.spoj.com/problems/NWERC11B/

이러한 문제는 사소한하지 않고, 시간을 물어볼 것입니다,하지만 당신은 확실히이 배울 것 : http://www.spoj.com/problems/TREE/

또는이 :

Answer 1

음,이 시도.

기본적으로 어떤면에서는 기본적으로 이진 트리가 필요한 수많은 문제가 있습니다. 예를 들어, 명제 논리에서 추론 알고리즘을 구축합니다.

예, Sedgewick의 알고리즘을 사용할 수 있다면 바이너리 검색 트리에 대한 장이 있습니다. 예를 들어, 매우 유용합니다.

Answer 2

위의 코드는 이진 트리의 "유효한"구현입니다 ... 이미 완료되었습니다. 당신은 노드 (당신은 Tree이라고 부름)를 가지고 있고 각 노드는 0, 1, 또는 2 개의 자식을 가질 수 있습니다. 편집 사실 나는 방금 구현 한 것을 사용하여 빈 트리를 구현할 수 없다는 것을 깨달았습니다.하지만 이는 작은 단서입니다.

이것은 의미 론적 일이지만 "중요한 것"입니다. 자체적으로 이진 트리는 실제로 문제에 전혀 사용되지 않습니다. 표준 바이너리 트리는 실제로 유용하지 않습니다. 각 노드에 최대 두 명의 자식이있는 나무 일뿐입니다. 이 링크는 내가 무엇을 말하고 있는지 (그리고 아마도 당신의 질문에 대한 충분한 대답을 포함하고있을 것입니다) : https://stackoverflow.com/a/2159506을 명확히해야합니다.

실제로 관심있는 내용은 추가 속성이있는 "균형 이진 검색 트리"입니다. 특히 그것은 왼쪽에서 오른쪽으로 "정렬"되어 있습니다 (모호한 설명이지만 손으로 ​​물결 모양이되어 실제로 존재할 수있을 때 왼쪽 자식이 부모와 형제보다 적다고 말하기는 싫습니다). 일부 구현에서는 동일 함). 또한 O(log(n))의 경계가 있습니다 (너비가 n 인 나무는 n 개가 아니며 링크 된 목록 임).

어쨌든, 귀하의 질문에 대답 : 그것은 지루한 일이지만 일반적인 제안은 힙이나 사전과 같은 추상적 인 데이터 구조를 구현하는 것입니다. 용어에 유의하십시오. 힙 은 이진 검색 트리를 사용하여으로 구현할 수 있습니다. 정의상 힙은 모든 구현과 관련이 없습니다. 특정 작업 (예 : peek(), min(), add() 등) 만 수행하면됩니다. 힙을 생성하려면 이진 트리와 같은 원시 데이터 구조를 선택해야합니다 (그렇지 않으면 머리에 떠있는 추상적 인 것입니다). 균형 잡힌 이진 검색 트리를 선택하면 해당 작업에 시간이 많이 소요됩니다 (예 : 균형 이진 검색 트리로 구현 된 힙이 O(log(n)) peek()). 자세한 내용은 위키 링크 (http://en.wikipedia.org/wiki/Heap_(data_structure)#Comparison_of_theoretic_bounds_for_variants)를 참조하십시오.

일단 힙을 작성하면 알고리즘에서 힙을 사용하는 문제를 볼 수 있습니다. 선형 시간에 k 번째로 큰 요소를 찾고 싶다고합시다. 힙 (이것은 조금 까다 롭습니다.) Prim의 알고리즘을 구현하려면 어떻게해야할까요? 더미. 최악의 경우 O(n log(n))으로 임의의 객체를 정렬하려면 어떻게해야합니까? Heaport (보통 사람들은 힙 정렬을 사용하지 않는다. 왜냐하면 실제로는 빠르지 않기 때문이다).