트리 삽입을 재생합니다

https://stackoverflow.com/questions/2008630

18-09-2019
|

문제

바이너리 트리 기술을 연마하기위한 몇 가지 운동을 통해 다음과 같이 설명한대로 스플레이 트리를 구현하기로 결정했습니다. 위키 백과 : 스플레이 트리.

내가 얻지 못하는 한 가지는 삽입에 관한 부분입니다.

그것은 말한다 :

먼저, 우리는 스플레이 트리에서 x를 검색합니다. x가 아직 존재하지 않으면 우리는 그것을 찾지 못하고 부모 노드 y를 찾을 수 있습니다. 둘째, 우리는 Y에서 스플레이 작업을 수행하여 y를 스플레이 트리의 뿌리로 이동합니다. 셋째, 새 노드 X를 적절한 방식으로 루트로 삽입합니다. 이런 식으로 Y는 새 루트 x의 왼쪽 또는 오른쪽 자식입니다.

내 질문은 이것입니다 : 위의 텍스트는 기사의 다른 예제와 비교하여 지나치게 간결 해 보입니다. 왜 그런가요? 여기에 약간의 gotchas가 남아있는 것 같습니다. 예를 들어, y 노드를 루트까지 뿌린 후에는 루트를 x로 맹목적으로 바꾸고 x에 y를 왼쪽 또는 오른쪽 자식으로 대체 할 수는 없습니다.

나무에 값이 아직 존재하지 않는다고 가정 해 봅시다.

나는이 나무가있다 :

           10
          /  \
         5    15
        / \    \
       1   6    20

그리고 삽입하고 싶습니다. 루트까지 6 노드 :

그런 다음이 두 가지 중 하나는 특허 적으로 잘못되었습니다.

          8                                  8
           \                                /
            6                              6
           / \                            / \
          5   10                         5   10
         /     \                        /     \
        1       15                     1       15
                 \                              \
                  20                             20

    6 is not greater than 8          10 is not less than 8

먼저 스플레이를 수행하는 유일한 방법 인 것 같습니다. 그런 다음 루트로 새 값을 올바르게 추가하면 다음 기준을 확인해야한다는 것을 의미합니다 (새 루트의 왼쪽 자식으로 스플레이 된 노드를 추가하기 위해).

내가 루트로 펼친 노드는 새 루트보다 작습니다 (6 <8)
노드의 가장 오른쪽 아이는 뿌리에 뿌려진 것도 새 루트보다 작습니다 (20 8)

그러나, 내가 올바른 아이를 데려 가서 새 노드의 올바른 자식으로 추가함으로써 내가 펼친 노드를 분할한다면, 나는 이것을 얻을 것이다.

                        8
                       / \
                      6   10
                     /     \
                    5       15
                   /         \
                  1           20

그러나이 간단한 변경이 항상 나에게 올바른 나무를 줄까요? 나는 예를 들어 오는 데 어려움을 겪고 있지만 이것이 다음으로 이어질 수 있습니다.

내가 추가하고 싶은 새로운 값은 임시 루트 (루트에 뿌린 노드)보다 높지만 임시 루트의 오른쪽 자식의 가장 왼쪽 자식보다 높습니까?

즉. 기본적으로 튀어 나온 후 이렇게 보이지만 뿌리를 교체하기 전에?

그리고 나는 13을 추가하고 싶습니다. 이것은 다음과 같이 새 나무를 만들 것입니다.

                        13
                       /  \
                     10    15
                     /    /  \
                    5   11    20  <-- 11, on the wrong side of 13

아니면 이런 일이 일어나지 않을 수 있습니까?

두 번째 질문은 다음과 같이 작업을 다시 작성하는 것이 훨씬 쉽지 않습니까?

먼저, 우리는 스플레이 트리에서 x를 검색합니다. x가 아직 존재하지 않으면 우리는 그것을 찾지 못하고 부모 노드 y를 찾을 수 있습니다. 그런 다음 새 노드를 부모 노드의 왼쪽 또는 오른쪽 자식으로 추가합니다. 셋째, 우리는에서 스플레이 작업을 수행합니다 우리가 추가 한 노드 새 값을 스플레이 트리의 루트로 이동합니다.

내가 무엇을 바꾸 었는지 보여주기 위해 강조합니다.

해결책

설명하는 문제가 어떻게 발생할 수 있는지 모르겠습니다. 이 나무에 13을 삽입하려면 먼저 다음을 찾아야합니다.

10에서 당신은 오른쪽으로 가고, 15에서 당신은 왼쪽으로 가고, 11에서 당신은 오른쪽으로 가고 있습니다. 그리고 당신은 더 이상 요소가 없습니다. 133이 나무에 있었다면, 우리는 그것을 11의 올바른 아이로 알게되었을 것입니다. 따라서 규칙에 따라 11에 스플레이 작업을 수행하여 11은 스플레이 트리의 뿌리로 이동합니다.

                    11
                   /  \
                  10   15
                 /       \
                5         20

그런 다음 13을 새 뿌리로 추가하고 11 명으로 좌파 자식으로 추가합니다.

                    13
                   /  \
                  11   15
                 /       \
                10        20
               /
              5

이제 문제가 없습니다.

먼저, 우리는 스플레이 트리에서 x를 검색합니다. x가 아직 존재하지 않으면 우리는 그것을 찾지 못하고 부모 노드 y를 찾을 수 있습니다. 그런 다음 새 노드를 부모 노드의 왼쪽 또는 오른쪽 자식으로 추가합니다. 셋째, 우리는 추가 된 노드에서 스플레이 작업을 수행하여 새 값을 스플레이 트리의 루트로 이동합니다.

이것은 나에게도 효과가있는 것처럼 들리지만, 내가 당신이라면, 나는 많은 사람들이 그것을 테스트했으며 이미 잘 문서화되어 있기 때문에 Wikipedia에 설명 된대로 버전을 구현하려고 노력할 것입니다.

다른 팁

"Splay Tree"는 즉시 CUJ의 기사를 기억하게 만들었습니다. C ++에서 스플레이 트리 구현.

셋째, 새 노드 X를 적절한 방식으로 루트로 삽입합니다. 이런 식으로 Y는 새 루트 x의 왼쪽 또는 오른쪽 자식입니다.

그렇습니다. 그러나이 새로운 뿌리 X에는 2 명의 자녀가 있어야 하므로이 문장이 혼란 스러울 수 있습니다.

새 노드는 일반적인 이진 검색 트리처럼 트리에 추가됩니다. 그러면 새 노드가 루트에서 루트 또는 첫 번째 레벨로 튀어 나옵니다. 또한 새 노드를 삽입 할 때는 위치를 찾아야하므로 찾을 수 있습니다. 그리고 스플레이 트리에서 찾기를 포함한 모든 작업은 스플레이 작업을 트리거합니다. Wikipedia 기사가 그렇게 설명하는 이유 일 수 있습니다. 나는 단지 새 노드를 삽입하고 그것을 펼친다. 어느 쪽이든 나무는 그보다 균형이 잘해집니다. 잘 작동합니다 여기

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow