(이진) 검색 트리의 시각적 너비를 최소화하는 방법은 무엇입니까?

debugcn 에 게시 Dev

칼렙 531

소개

주어진 숫자 목록에서 이진 검색 트리의 시각적 표현을 만드는 HTML5 웹 응용 프로그램을 만들고 있습니다.

현재 트리의 최대 깊이 (base-0 값)를 기준으로 각 행의 노드 간 시각적 간격을 계산하는 알고리즘이 있습니다.

offset = 50
offset *= pow(2, maxDepth - currentDepth)

여기에서 노드의 위치는이 오프셋과 부모의 x 위치를 사용하여 결정됩니다.

알고리즘은 모든 깊이의 가능한 가장 넓은 트리를 항상 수용 할 수 있기 때문에 잘 작동합니다. 그러나 이것은 또한 때때로 나무를 불필요하게 넓게 만듭니다.

예

왼쪽으로 분기하는 트리 (너무 넓음) :

왼쪽으로 나뭇 가지 http://f.cl.ly/items/0c0t0L0L0o411h092G2w/left.png

양쪽으로 분기되는 트리 (왼쪽과 오른쪽이 서로 더 가까울 수 있음).

양쪽으로 분기하는 트리 http://f.cl.ly/items/0r3X1j0w3r1D3v1V1V3b/left-right.png

이상적으로, 위의 나무는 아래 그림과 같이 너비가 더 작고 측면이 직선 인 피라미드 모양이어야합니다.

양쪽으로 분기 할 때 이상적인 나무

균형 잡힌 트리 (알고리즘이 가장 잘 작동하는 경우) :

균형 잡힌 나무 http://f.cl.ly/items/203m2j2i3P1F2r2T3X02/balanced.png

이행

속성

Backbone.js를 사용하여 Node 모델에서 노드를 만듭니다. 각 노드에는 다음과 같은 속성이 있습니다.

부모 (부모 노드)
left (왼쪽 자식 노드)
오른쪽 (오른쪽 자식 노드)
x (픽셀 단위의 노드 x 위치)
y (노드의 y 위치 (픽셀 단위))

위의 x 및 y 속성은 노드가 분기하는 방향에 따라 계산됩니다.

if (parent.get('left') === node) {
    x = parentX - offsetX;
    y = parentY + offsetY;
} else if (parent.get('right') === node) {
    x = parentX + offsetX;
    y = parentY + offsetY;
}

이 시점에서 x 및 y 속성은 노드를 배치하는 데 사용되는 정확한 값입니다 (각각은 컨테이너 요소 내에서 절대 위치에 있음).

행동 양식

getDepth () (노드의 밑 수가 0 인 깊이를 반환)
getMaxDepth () (트리에서 마지막 행의 깊이를 반환)
getRow (n) (깊이 -n에있는 모든 노드의 배열을 반환)

질문

따라서 내 질문은 간단합니다.

바이너리 트리의 미적 너비를 최소화하는 가장 좋은 알고리즘은 무엇입니까?

니키

비슷한 질문에 대한 답변을 살펴보면 도움이 될 수 있습니다 . 여기에는 원하는 종류의 트리 시각화를 정확히 수행하는 소프트웨어에 대한 링크가 포함되어 있습니다.

미학은 매우 주관적이므로 이것은 제 의견입니다. 내 지침 ( 알고리즘이 아님)은 다음과 같습니다. 나는 아이들의 순서가 중요하다고 가정하고 있습니다 (이진 검색 트리이기 때문에).

만 x좌표는 흥미 롭다; y좌표는 노드의 수준에 의해서만 결정되어야합니다. (이것이 위반되면 다소 못 생겼지 만 내가 말했듯이 맛은 다르지만 나머지는이 가정에 근거한다.)
동일한 수준의 노드는 고정 된 최소 거리보다 가까워서는 안됩니다 (예 :) D.
노드에 x1및에 두 개의 자식 x2이 있으면에 배치하는 것이 (x1+x2)/2좋습니다. 어떤 경우에는 다른 좌표를 선택하는 것이 좋습니다 [x1..x2](아마도 그 끝 중 하나). 외부 좌표가 더 좋은 특이한 경우가있을 수 있다고 생각 [x1..x2]합니다.
노드에 자식이 하나 x1있고 부모가에있는 xp경우에는에 배치 (x1+xp)/2하는 것이 좋습니다 (부모와 자식을 연결하는 선에 놓 이도록). 어떤 경우에는 이것에서 벗어나 내부 [xp..x1](또는 외부)의 다른 좌표를 선택하는 것이 좋습니다 .
레벨의 너비 를 맨 왼쪽 노드와 맨 오른쪽 노드 사이의 거리 라고합시다 . 가장 넓은 레벨의 너비는 최소 여야합니다.

이러한 지침은 동시에 모두 만족할 수없는 제약을 부과합니다. 따라서 우선 순위를 지정해야하며 이는 다시 주관적입니다. 예를 들어, # 4 또는 # 5가 더 중요한 것은 무엇입니까? 5- 노드 트리에 대한 스케치는 # 4가 더 중요하다는 것을 의미합니다. # 5가 더 중요하다면 집과 같은 그림 (수직선)을 얻을 수 있습니다. 둘 다 중요하다면 현재 결과는 괜찮을 것입니다.

이를 해결하는 한 가지 방법은 가이드 라인에 가중치를 할당하고이를 따르지 않을 경우 벌칙을 정의하는 것입니다. 예를 들어, 지침 # 3에서 abs(x-(x1+x2)/2)부모가 x자식 사이의 중간에 위치하지 않으면 처벌을받을 수 있습니다. 다른 지침과 비교하여 이것이 얼마나 중요한지 알려주는 가중치를 할당 할 수도 있습니다. 그런 다음 솔루션의 총 가중 패널티를 최소화해야합니다. 일반적으로 이것은 제약 최적화 문제를 제공 하며 이러한 문제를 해결하는 방법에는 여러 가지가 있습니다.

이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.

침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제

에서 수정2021-05-29

몇 마디 만하겠습니다

0리뷰

로그인참여 후 검토

Related 관련 기사

기사