Chapter 2. Binary Search Trees Search (2)

쓰리원·2022년 4월 19일
0

Search Structures

목록 보기
2/5
post-thumbnail

1. BST의 정의

  1. 각 노드는 (키, 값)의 쌍을 저장하며, 서로 다른 노드의 키는 다르다.
  2. 부모의 키는 왼쪽 서브트리에 저장된 노드의 키보다 크다.
  3. 부모의 키는 오른쪽 서브트리에 저장된 노드의 키보다 작다.

동작 과정

  • 검색: 루트부터 비교.
     작으면 왼쪽, 크면 오른쪽. 같으면 발견.
  • 삽입: 검색 후, 있으면 수정. 없으면 추가.

장점

  • 심볼 테이블을 정렬된 순서로 유지할 필요 없다.
  • 새로 삽입되는 노드는 항상 리프 노드에 위치

문제점

  • Balanced tree를 지원하지 못함
  • Too many seeks
     24개의 key 로 구성된 tree: 5번의 seek

예시

2. Java를 이용한 BST의 구현

Node와 트리(BST)를 구분하여 구현
Node: key와 value, 자식 노드에 대한 reference
BST: root 노드(Node)에 대한 reference를 포함

  • 트리에 대한 연산들은 BST에서 구현

1. 기본구조

class Node<K,V> {
	K key;
	V value;
	Node<K,V> left, right;
	public Node(K key, V val) {
	this.key = key;
	this.value = val;
	}
}

2. Ordered operation과 Balanced Tree를 위한 추가적인 구조

class Node<K,V> {
	int N; // 자손 노드 + 1 (ordered 연산)
	int aux: // AVL 트리나 RB 트리에 사용
	Node<K,V> parent; // AVL or RB
	public Node(K key, V val) {
		this.key = key; this.value = val;
		this.N = 1;
	}
	public int getAux(){ return aux; }
	public void setAux(int value) { aux = value; }
}

3. BST 클래스

4. BST 구현 – treeSearch()

  1. 키를 입력받아, 그 키를 갖는 노드 또는 순회의 마지막 노드를 반환합니다.

  2. 비교 횟수 = 노드의 레벨 (단, 루트의 레벨 = 1)

protected Node<K,V> treeSearch(K key) {
	Node<K,V> x = root; // BST에 대한 모든 연산은 루트부터 시작
	while (true) {
		int cmp = key.compareTo(x.key);
		if (cmp == 0) return x; // 찾았으면, 순회 종료
		else if (cmp < 0) { // x.key보다 작을 경우, 왼쪽으로
		if (x.left == null) return x; // 없으면, 순회 종료
		else x = x.left;
	}
	else { // x.key보다 클 경우, 오른쪽으로
		if (x.right == null) return x; // 없으면, 순회 종료
		else x = x.right;
		}
	}
}

5. BST 구현 – get()

Get: 주어진 키에 해당하는 값을 반환. 키가 없으면 null

public V get(K key) {
	if (root == null) return null;
	Node<K,V> x = treeSearch(key);
	if (key.equals(x.key)) // 검색 키를 가진 노드가 반환된 경우
	return x.value;
	else // 검색 키를 가진 노드가 없는 경우
	return null;
}

6. BST 구현 – put()

  1. Put: 검색 후, 키가 있으면 reset. 없으면 추가
  2. 비용: 비교 횟수 = 노드의 레벨
public void put(K key, V val) {
	if (root == null) { root = new Node<K,V>(key, val); return; }
	Node<K,V> x = treeSearch(key);
	int cmp = key.compareTo(x.key);
	if (cmp == 0) x.value = val; // 키가 존재하므로, 값을 reset
	else { // 없는 키: 새로운 노드를 생성하여 x의 자식으로 추가
	Node<K,V> newNode = new Node<K,V>(key, val);
	if (cmp < 0) x.left = newNode;
	else x.right = newNode;
	newNode.parent = x;
	rebalanceInsert(newNode); // Insert의 후속 조치: 다음 slide
	}
}

7. BST 구현 – rebalanceInsert()

BST의 subclass인 AVLTree나 RBTree에서 overriding

  • BST에서는 신규 노드의 모든 조상 노드들의 size 증가
protected void rebalanceInsert(Node<K,V> x) {
	resetSize(x.parent, 1); // root까지 조상 노드들의 size를 1 증가
}
protected void rebalanceDelete(Node<K,V> p, Node<K,V> deleted) {
	resetSize(p, -1); // root까지 조상 노드들의 size를 1 감소
}
private void resetSize(Node<K,V> x, int value) {
	for ( ; x != null; x = x.parent)
		x.N += value;
}

8. BST 구현 – keys()

키의 정렬된 리스트를 반환 -> Inorder 순회 이용

public Iterable<K> keys() {
	if (root == null) return null;
	ArrayList<K> keyList = new ArrayList<K>(size());
	inorder(root, keyList);
	return keyList;
}
private void inorder(Node<K,V> x, ArrayList<K> keyList) {
	if (x != null) {
	inorder(x.left, keyList);
	keyList.add(x.key);
	inorder(x.right, keyList);
	}
}

profile
가장 아름다운 정답은 서로의 협업안에 있다.

0개의 댓글