마지막으로 어떤 노드가 주어졌을 때 그 노드의 바로 이전 노드와 바로 다음 노드를 구하는 메서드인 prev()와 next()를 구현해 보겠습니다. 코드를 먼저 보겠습니다.
코드 8-8
def prev(self, cur):
if cur.left: ➊
return self.max(cur.left)
parent = cur.parent ➋
while parent and cur == parent.left: ➌
cur = parent
parent = parent.parent
return parent
def next(self, cur):
if cur.right: ➍
return self.min(cur.right)
parent = cur.parent ➎
while parent and cur == parent.right: ➏
cur = parent
parent = parent.parent
return parent
➊ 왼쪽 자식이 있다면 왼쪽 자식에서 가장 큰 노드
➋ 부모 노드를 받아 옵니다.
➌ 현재 노드가 부모 노드의 왼쪽 자식이면
➍ 오른쪽 자식이 있다면 오른쪽 자식에서 가장 작은 노드
➎ 부모 노드를 받아 옵니다.
➏ 현재 노드가 부모 노드의 오른쪽 자식이면 루트에 도달하거나 현재 노드가 부모 노드의 왼쪽 자식이 될 때까지 계속 부모 노드로 이동