[C++ STL] rbtree_iterator

• https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_tree.h
• https://cplusplus.com/reference/iterator/
• rbtree_iterator는 bidirectional iterator이다. vector의 random access iterator와 다르게 arithmetic operators + and -, 비교연산, += 연산, [] 접근 등을 지원하지 않아도 됨.
• 멤버변수의 경우 public으로 iterator가 가리키는 rbtree node를 저장할 수 있게 해 줌.
• 대신 iterator의 ->이나 * 접근은 node의 data의 주소, 값으로 할 수 있게 함

increment

• https://stackoverflow.com/questions/20990808/bst-finding-next-highest-node
• operator++을 위한 알고리즘
• Case 1: right child가 있으면 right child의 leftmost 노드 리턴(내 right subtree가 존재한다면 right subtree의 leftmost 노드가 나보다 큰 값 중 가장 작은 값)
• Case 2: right child가 없는 경우, 내가 left child였을 때까지 위로 올라가서 내 부모 노드 리턴(내가 left sub tree였을 동안 위로 올라가서 그 부모를 리턴해야 나보다 큰 값 중 가장 작았던 값을 리턴할 수 있다.)
• Case 3: 위에서 리턴 안 됐음 TNULL노드(leaf node) 리턴.

decrement

• operator--를 위한 알고리즘 (operator++ 와 반대라고 생각하면 됨)
• Case 1: left child가 있으면 left child의 rightmost 노드 리턴(내 left subtree가 존재한다면 left subtree의 rightmost 노드가 나보다 작은 값 중 가장 큰 값)
• Case 2: left child가 없는 경우, 내가 right child였을 때까지 위로 올라가서 내 부모 노드 리턴(내가 right sub tree였을 동안 위로 올라가서 그 부모를 리턴해야 나보다 작은 값 중 가장 컸던 값을 리턴할 수 있다.)
• Case 3: 위에서 리턴 안 됐음 TNULL노드(leaf node) 리턴.

end(== leaf node == _TNULL)의 --를 위해 필요한 추가 작업

• 이론상 leaf node는 parent를 가리킬 필요가 없음.
• 하지만 end에서 --를 하면 tree의 rightmost 노드를 가리킬 수 있어야 함.
• 이를 위해 end의 parent를 root를 가리키게 해줘서
• end에서 --를 하려고 할 땐 end->parent(== root)의 maximum 노드를 가리키도록 해줬음.