이진 검색 트리 2

x를 루트로 하는 이진트리에서 최소값을 찾으려면 맨 왼쪽에 있는 리프 노드까지 도달하면 된다.

왼쪽으로 계속 내려가다가 더 이상 자식이 없다면 그 값이 최소값이다.

tree-minimum(x):

  while left[x] != None:

    x=left[x]

  return x

반대로 최대값은 오른쪽 아래로 내려가야 한다.

tree-maximum(x):

  while right[x] != None:

    x=right[x]

  return x

Successor

노드 x의 successor란 key[x]보다 크면서 가장 작은 키를 가진 노드.

1. 노드 x의 오른쪽 부트리가 존재할 경우, 오른쪽 부트리의 최소값.

2. 오른쪽 부트리가 없는 경우, 노드 x의 부모를 따라 올라가다가 처음으로 오른쪽 방향으로 올라간다면 그 노드가 x의 successor이다.

3. 위 경우가 없다면 successor는 없다.

tree_successor(x):

  if right[x] != None:

    return tree_minimum(right[x])

  y = p[x]

  while y != None and x == right[y]

    x=y

    y=p[y]

  return y

Predecessor

x보다 작으면서 가장 큰 값

Insert

트리의 전체 구조는 바뀌지 않고 비교하려는 값보다 작다면 왼쪽 크다면 오른쪽으로 내려가면서 이동하다가 자식이 없다면 자리를 잡은 것이다. x가 값을 비교하면서 내려가는데 y는 뒤따라가는 역할이다.

tree_insert(T,z): #트리와 insert할 노드

  y=None

  x=root[T]

  while x!=None:

    y=x

    if z < key[x]: #현재 노드보다 작다면 왼쪽으로 내려감

      x=left[x]

    else:

      x=right[x]

  p[z]=y #y의 위치가 z의 부모, y는 x보다 한칸 위

  if y == None: #루트가 비어 있다면 삽입하려는 값 z가 root가 된다.

    root[T]=z

  elif z < key[y]: #삽입하려는 값(z)이 y 값보다 작다면 y의 왼쪽 자식에 삽입 

    left[y] = z

  else:

    right[y] = z