Splay 트리 구현에 재귀 알고리즘을 사용할 수 있습니까?

Question

나는 이것을 구현하고 싶기 때문에 스플레이 트리를 연구 해왔다. 현재 Red-Black 트리, AVL 트리, 건너 뛰기 목록 및 기타 간단한 데이터 구조에 대해 "자가 진단 (autodidactic)"경험이 있습니다. 내 첫 번째 스플레이 트리를 구현하고 싶지만 가능한 경우 재귀 적 구현을 ​​원한다. (재귀를 좋아한다).

그러나 가능한 모든 경우 (지그재그, 지그재그, zar)를 관찰하기 위해 나무 아래 두 수준을 봐야하기 때문에 어렵다고 생각합니다. 다른 필드없이 대상을 표시 할 방법이 없습니다. . 붉은 검정 나무와 같은 다른 필드를 사용하여 방문한 노드를 표시하고 대상 노드를 표시해야합니까?

Answer 1

재귀 알고리즘을 사용하는 것은 쉽고 공정하게 깨끗하게 보일 수도 있습니다. 표시가 필요하지 않습니다. 검색, 삽입 및 삭제에 사용되는 표시 작업은 대상 노드를 트리의 맨 위로 가져옵니다. 즉, 대상 노드가 맨 위에있는 (스레딩 된) 트리를 반환합니다.

본질적으로 주어진 노드에서 다음 두 가지 동작 (왼쪽, 오른쪽 오른쪽 또는 다른 것)을 결정해야합니다. 동일한 방향을 두 번 이동하면 회전이 발생합니다.

크리스 오카사키 (Chris Okasaki)의 순수 기능 데이터 구조에는 기능 언어에 대한 유용한 구현이 있습니다.이 imho는 존재하는 가장 훌륭한 짧은 CS 텍스트 중 하나입니다.

Answer 2

위키피디아에서는 분출 나무에 관한 정말 멋진 기사를 찾을 수 있습니다. 재귀가 손에서 쉽게 벗어날 수 있기 때문에 재귀를 사용해서는 안됩니다. 반복성을 사용하는 것이 좋습니다.