알고리즘) 중간고사_대비_2장

 

 

 

연결리스트 

① delete(K key) 메서드 (수정 필요)

1. 리스트가 비어있을 때: first가 null이면 ptr.next에서 에러(NullPointerException)가 납니다.
2. 첫 번째 노드를 지워야 할 때: 작성하신 루프는 ptr.next부터 확인하기 때문에, 정작 첫 번째 노드(first)가 삭제 대상인 경우는 건너뛰게 됩니다.

    if (first == null) return; // 리스트가 비어있으면 아무것도 안 함

    // 1. 첫 번째 노드가 삭제 대상인 경우 (Special Case)
    if (first.key.equals(key)) {
        first = first.next;
        N--;
        return;
    }

 

 

 

 

 

심볼 테이블의 keys()는 보통 노드 전체가 아니라 키(K)들의 집합만 돌려줍니다.

arrList.add(ptr.key); // 키만 담기

 

 

contains(key)는 직접 루프를 돌려도 되지만, 이미 만들어둔 get(key)을 활용해서 return get(key) != null; 한 줄로 끝낼 수도 있습니다. 

 

 

배열

삽입할때도 뒤로 밀어줘야함 

 

 

 

keys = (K[]) new Comparable[capacity];
vals = (V[]) new Object[capacity];

key는 object가 아니라 Comparable이어야하네 

 

 

데이터를 밀 때는 "뒤에서부터" 옮겨야 앞에 데이터가 덮어씌워지지 않습니다.

• 잘못된 부분: keys[i] = keys[i+1] (앞에 있는 칸에 뒤에 있는 값을 넣음 -> 당기기 로직임)
• 수정 로직: keys[i] = keys[i-1] (현재 칸에 바로 앞 칸의 값을 넣음)

 

 

 

delete 메서드: 왼쪽으로 당기기 (Shift Left)

데이터를 삭제할 때는 빈틈을 메우기 위해 "앞에서부터" 뒤의 데이터를 가져와야 합니다.

• 잘못된 부분: i < keys.length까지 돌면 마지막에 keys[i+1]을 참조할 때 에러가 납니다.
• 수정 로직: i < N - 1까지만 돌면서 바로 뒤의 값을 현재 칸으로 가져옵니다.
• 누락된 부분: 삭제 후 N을 줄여야(N--) 합니다.

 

 

 

1. 이진 탐색 (Binary Search): while (lo <= hi)

이진 탐색은 **"목표값(Key)이 리스트 안에 있는지 확인"**하는 것이 목적입니다.

• 원소가 1개 남았을 때 (lo == hi): 이 마지막 남은 원소가 내가 찾는 그놈일 수도 있습니다!
• 따라서: lo == hi인 상황에서도 루프 안으로 들어가서 mid를 계산하고, compareTo로 확인을 해야 합니다.
• 종료 조건: 마지막 남은 1개마저 내가 찾는 게 아니라면, lo가 mid+1이 되거나 hi가 mid-1이 되면서 lo > hi가 됩니다. 이때서야 비로소 **"아, 이 배열엔 없구나!"**라고 확신하며 멈추는 것입니다.

2. 합병 정렬 (Merge Sort): if (lo >= hi) return;

합병 정렬은 **"배열을 쪼개고 쪼개서 정렬하는 것"**이 목적입니다.

• 원소가 1개 남았을 때 (lo == hi): 원소가 하나뿐인 배열은 이미 그 자체로 정렬된 상태입니다. 더 이상 쪼갤 수도 없고, 정렬할 필요도 없죠.
• 따라서: lo == hi가 되는 순간 **"더 할 일 없으니 돌아가(return)"**라고 하는 것입니다. (정렬을 수행하는 lo < hi 조건의 반대)

 

 

V get(K key) { if (isEmpty()) return null; int i = search(key); '
if (i < N && <<<<<<
keys[i].compareTo(key) == 0) return vals[i]; return null; }

이건 내코드랑 뭔차인거지

 

 

연결리스트일때는 그냥 Node<>였고

Bst는 Treenode네 

 

if (i < 0) { // 왼쪽으로 가야 하는데...

if (ptr.left == null) return ptr; // 왼쪽이 비었네? 그럼 여기가 끝! (현재 노드 리턴)

ptr==null일때 멈추는게 아니라 

 

 

get: treesearch이용하기 

 

 

 

 

 

일반적인 방식 (0, 1, 2개 자식)의 단점

자식 개수로만 나누면, 각 케이스 안에서 매번 "이게 루트인가?"를 또 체크해야 합니다.

• 자식이 0개일 때: 루트면 root=null, 아니면 부모.자식=null
• 자식이 1개일 때: 루트면 root=자식, 아니면 부모.자식=내자식
• 이렇게 모든 조건 안에 if (root) 체크가 중복해서 들어가는 게 싫어서 이 코드는 머리를 쓴 것입니다.

 

 

 

relink(p, child, x == p.left)에서 세 번째 매개변수인 **x == p.left**는 한마디로 **"내가 부모님의 어느 쪽 자식이었는지 알려주는 정보

 

 

 

루트에서 자식이 하나인가, 일반적인 겨웅에서 자식이 하나인가의 차이 

 

 

자식이 둘일 때는 나(x)를 지우는 게 아니라, 후계자(y)를 지우는 것입니다.

 

 

x == root

첫번째 분기점은 

isLeaf임 

 

for (ptr = root; ptr.left!=null ; ptr=ptr.left) { //ptr.left!=null인가 조건식이 ㅁ? }

 

 

그러면 totqaet에ㅓㅅ z는 왜필요하지, 연결을 위해서 필요햇던것이고, 사실 x,y자리를 바꾸는건가,ㄹㄹㅇㅇ

 

//아마 둘다 x보다 작은 위치에 있느느, 혹은 둘다 x보다 큰위치에 이쑈는
//즉 ll일떄는 y는 40 x=30이면 y처럼 x보다 큰 , 35, x의 오른쪽 자식이고
//그 반대 방향이면 또 y와 같은 방향에 있는게 ?

rotate에서 자식의 방향에 대해서 

 

1. 분기점의 의미: rotate(x)는 복잡한 LR/RL을 고민하지 않습니다. 오직 **"내가 부모의 어느 쪽에 있느냐"**만 보고 부모와 자리를 바꿉니다. 복잡한 케이스는 restructure가 이 함수를 여러 번 호출해서 해결합니다.