바이너리 검색 트리 노드를 -1 배 곱하기

Question

Binary Search Tree을 고려하십시오. multiply all nodes by -1의 경우 아무도 제발 알려 줄 수 있습니다. 여전히 Binary Search Tree입니까?

Binary Search Tree으로 변환하는 함수를 작성할 수 있습니까?

Answer 1

흥미로운 문제.

Binary Search Tree에서 개체 그래프의 구조는 정렬 순서를 나타냅니다.

모든 개체에 -1을 곱하면 역방향으로 정렬됩니다.

EG :

3 4 8 9 12 

그래서

-3 -4 -8 -9 -12 

---

이되고, 어떻게이 여전히 이진 검색 트리 속성을 유지해야합니까?

이진 트리는 객체 노드의 그래프와 객체 비교 방법에 대한 지식이라는 두 가지로 구성됩니다. 비교 함수는 같은 것을 보일 것이다 : 당신이 당신의 이진 트리 내부의 값에 대한 변환을 수행하는 경우

Compare(left, right) { 
    return (left < right); 
} 

을, 당신은 그것의 비교 기능을 변경할 수 있습니다 다음 그것을 정상적으로 작동 할 것입니다.

myBinaryTree.comparisonFunction = function(left, right) { return (right < left) }; 

Answer 2

이진 검색 트리에서 노드의 왼쪽 하위 트리의 모든 요소는 노드보다 작거나 같아야하며 노드의 오른쪽 하위 트리의 모든 요소는 노드보다 크거나 같아야합니다 (일부 트리에서는 같음). 일부 나무) 노드. 모든 노드에 -1을 곱하면 결국 각 노드의 왼쪽 하위 트리에 더 큰 값이 저장되고 오른쪽 하위 트리에는 더 작은 값이 저장됩니다. 다시 BST로 변환하려면 미러링하여 BST를 "뒤집어"해야합니다. 나는 운동으로 그 일을하는 방법에 대한 세부 사항을 남겨 둘 것이다. 그것은 재귀적인 해결책이있는 고전적인 CS 문제입니다.

희망이 도움이됩니다.