이진 검색 트리 삭제
None을 나올 때까지 찾음
이진 검색 트리 (Binary Search Tree) Loop. Ver
parent, child = snode, snode.right
while child.left is not None:
parent, child = child, child.left노드 검색에 사용한 변수 snode와 sparent가 이후에 사용되기 때문에 다른 변수 명 이용
elif data < sparent.data:
sparent.left = node
else:
sparent.right = node재귀적 알고리즘 구현의 값의 return과 재귀적 호출에 대응 되는 부분
if snode is self.root:
self.root = node루트 노드가 삭제 되는 경우 예외 처리 (재귀적 구현에서 유사하게 구현하려면, 추가 함수가 필요)
루트를 안써도 됨.
하지만 아래처럼 써도 됨.
수식 표기법(시험)
- 전위 표기법
×÷×+−315102+21 - 중위 (Infix) 표기법
(3−1+5)×10÷2×(1+2)=105 - 후위 (Postfix) 표기법
31 −5+10×2÷21+×
이진 검색 트리에서의 삽입
방법에 따라 같은 숫자여도 다른 순서로 삽입됨.
- Case #1: 30, 20, 25, 40, 10, 35 순으로 삽입됨
- Case#2:10,20,25,30,40,45순으로 삽입됨 (같은숫자,다른순서)
참고
정수: 2진수
- int : unsigned int (0 ~ 2의 32승-1)
signed int (-2의 31승-1 ~ 2의 31승)
왜 이렇게 기준을 정했을까?
2의 보수는 뒤집고 + 1
2의 보수를 쓰는 이유 (두개를 더하면 상수가 됨)
2의 보수란 0을 1로, 1을 0으로 모두 바꿔준후에 1을 더하는 방법이다.
0001은 1, 1111은 -1이된다.
다시 계산해 보면
1111 + 0001 = 10000
(-1) (1) (0이어야 함)
의 결과 가 나오는데 이 값은 맞게 된다. 최상위 비트가 1이지만 범위를 벗어났기 때문에
무시하기 때문이다. 따라서 0000 => 0이 된다.
<컴퓨터가 보수를 쓰는이유>
보수를 쓰는 이유는 컴퓨터가 (-)라는 개념이 없기 때문이다.
컴퓨터가 인식할 수 있는 것은 전기가 들어왔다(ON)전기가 나갔다(OFF)이것만 인식이 가능한데 음(-)이라는 개념은 컴퓨터에서 인식할수 없기 때문에 보수를 쓴다.
1의 보수는 0이라는 개념이 없을때는 그냥 사용해도 좋으나 0의 개념이 들어갈 경우 1의 보수로 한다면 (+)0과 (-)0이 나오게 됨
분명히 0은 하나밖에 없는데 음, 양의 개념으로 나뉜다면 컴퓨터가 오작동 함
이를 방지하기 위해 2의 보수를 사용한다.
2의 보수는 0의 개념이 단 하나로 지정되기 때문에 컴터가 오작동 할 이유가 없죠 그냥 쓰실때는 1의 보수도 괜찮으나 0의 개념을 쓰실경우는 2의 보수를 이용하여 사용하시는게 낫죠
결론은 음수 계산 및 기타 계산은 1의 보수 또는 2의 보수 둘 다 사용이 가능하지만 0의 개념을 하나로 통합하여 사용하기 위해서는
2의 보수를 사용하는게 좋다.
참고: https://kjhweb.tistory.com/40 [JH blog]
