트리 추상 데이터 형식

Question

데이터 구조 및 알고리즘이라는 유닛을 만들고 있습니다. 방금 시작했는데 교수님은 방금 대수학 의미론이 무엇인지, 공리가 무엇인지 등을 가르쳐 주셨습니다. 지금까지 배열의 형태로 나무를 사용했습니다. 트리 (값, 트리, 트리)로 미리 정렬 된 트리에 대한 시그니처를 사용하지 않습니다. 여기서 value는 노드의 값이고 왼쪽 노드는 첫 번째 트리이고 오른쪽 노드는 두 번째 트리입니다.

트리 (값, 트리, 트리) 또는 Nil로 트리를 정의 했으므로 addNode (value, tree)에 대한 대수를 정의하는 방법을 알아낼 수 없습니다.

각 레벨마다 점점 더 복잡해질뿐만 아니라 어쨌든 한 번에 한 레벨을 스캔하여 한 시간 이후로 시도해 볼 수는 없습니다. 대수학은 우리가 나무 아래로 내려갈 때 점점 더 많은 elles로 나옵니다. 내가 제대로하고 있니? 올바른 방향으로 나를 가리킬 수 있습니까? 또는 트리를 트리 (값, 트리, 트리)로 구현할 수 없습니까?

그것은 내 자습서의 일부이며 (추가 질문에서는 가치가 없음), 즉각적인 대답을 찾고 있지는 않습니다. 주제가 마음에 들고, 더 많이 배우고 싶습니다.

편집 1 : 위키피디아를 확인한 결과 확실한 답을 얻기 위해 교과서를 사용하고 싶지 않습니다. 올바른 접근 방식이 올바른지 또는 완전히 불가능한 지 여부에 대한 힌트를 찾고 있습니다. 트리를 트리 (값, 트리, 트리)로 정의하십시오. 양식 ADT를 목록으로 표현할 수 있다는 것을 알고 있습니다. 그러나 나는 그것에 대해 정말로 생각하고 싶었다. 그것이 의미가 있기를 바랍니다. 고마워요!

편집 2 : 음, 인터넷을 통해 설명하기가 어렵습니다. "tree"라는 새로운 데이터 구조를 정의한다고 가정 해 봅시다. 내가 원하는대로 정의 할 수 있고, 균형 잡힌 이진 트리처럼 행동해야한다. (부모님과 자식의 가치관은 중요하지 않다.) 그래서 tree로 정의한다 : tree (value, tree, tree) 또는 nil 그렇지 않다. 프로그래밍 코드는 정의 방법에 불과합니다. 트리는 + 2 개의 다른 트리이거나 Tree는 0입니다. 이제 addNode (value, tree)는 노드를 트리에 추가하면서 균형을 유지합니다. 이것은 프로그래밍 코드가 아니라 대수적 의미론입니다. 내가 제대로 설명 할 수 있을지 모르겠다. 하지만 큐 또는 스택을 사용하여 달성 할 수있는 솔루션을 얻었지만이를 정의해야하는 또 다른 ADT가 있는데 이는 유효하지 않습니다.

편집 3 : 내가 생각했던 것보다 문제를 더 어렵게 만든 많은 것을 생각한 것 같습니다. 우선, 내가 준 작은 설명에서, Gamecat의 대답은 완벽했습니다. 그러나 저는 의견에 동의합니다. 다른 ADT를 포함하는 것이 타당합니다. 사실, 우리가 Int를 사용하는 것을 만들 때, 우리는 그 구조에 대해 ADT를 사용하고 있습니다. 각 ADT는 고유해야한다고 생각했습니다. 어쨌든, 당신 대답에 많은 사람들 감사합니다!

Answer 1

노드를 트리에 추가하려는 경우 재귀 함수를 사용할 수 있습니다.

나무가 주문되었다고 가정합니다. 따라서 다음과 같은 내용을 가져야합니다.

AddNode(value, tree) 

if tree is empty, create a new tree with value as node and no subtrees. 
if value lesser than the treenode, call AddNode on the left branch. 
else call AddNode on the right branch. (if duplicates are allowed). 

하위 트리가 변경되면 업데이트해야합니다.나무가 균형해야하는 경우

if tree is empty, return a new tree with value as node and no subtrees. 
if value is lesser than treenode, and there is no left subtree, create a new left subtree with value as node and no subtrees. 
if value is lesser that treenode, and there is a left subtree, try again with the left subtree. 
if value is greater or equal than treenode, and there is no right subtree, create a new right subtree with value as node and no subtrees. 
if value is greater or equal than treenode, and there is a right subtree, try again with the right subtree. 

:

는 다음과 같은 방법으로 비 재귀 기능이 변환 할 수 있습니다. 균형 무게 (-1, 0 또는 1이 될 수 있음)를 저장해야합니다. "무거운"사이트에 노드를 추가해야하는 경우이를 다시 셔플해야합니다. 예를 들어 왼쪽에 오른쪽보다 하나의 노드가 있고 왼쪽에 노드를 하나 더 추가해야하는 경우를 예로들 수 있습니다. 왼쪽 하위 트리에서 가장 높은 값을 가진 노드를 가져와 현재 상위로 승격시켜야합니다. 이전 맨 위가 오른쪽 하위 트리에 추가됩니다. 하위 트리의 균형을 유지해야합니다.

예 : 문제가 무엇인지 나에게 그것은 분명하지 않다 노드 0,1,2,3,4

Add(0)   0 

Add(1)   0 
        \ 
        1 

Add(2)   0 (2) =>  1 (2) => 1 
        \   /  /\ 
        1   0   0 2 

Add(3)   1 
       /\ 
       0 2 
        \ 
        3 

Add(4)   1 (4)  => 2 (4) =>  2 
       /\  /\   /\ 
       0 2  1 3   1 3 
        \ /   / \ 
        3 0    0  4 

Answer 2

매우 모호하기 때문에 이것은 어려운 질문입니다. 나는 당신이 교과서의 일부로 텍스트 북이나 비슷한 것을 가지고 있다고 가정합니다. 그렇더라도 문제가있는 많은 것들이 바이너리 트리와 같은 기본 리소스로 설명되는 것처럼 느껴집니다.

이 페이지에서는 다양한 트리 탐색을 수행하는 방법과 트리를 표현하는 방법에 대해 설명합니다.