이진 검색 트리

이진 검색 트리의 정의

ㆍ 각 노드는 (키, 값)의 쌍을 저장하며, 서로 다른 노드의 키는 다르다.

ㆍ 왼쪽 서브 트리에 저장된 노드의 키보다는 크다.

ㆍ 오른쪽 서브 트리에 저장된 노드의 키보다는 작다.

---

이진 검색 트리의 장점

ㆍ 심볼 테이블을 정렬된 순서로 유지할 필요 없다.

ㆍ 새로 삽입되는 노드는 항상 리프 노드에 위치한다.

---

이진 검색 트리의 단점

ㆍ 균형 트리를 보장하지 않는다.

ㆍ 감색 시 많은 시간이 소요된다.

---

구현 방법

노드의 구성

class Node<K, V> {
	K key;
	V value;
	Node<K, V> left, right;

	int N;
	int aux;
	Node<K, V> parent;

	public Node(K key, V value) {
		this.key = key;
		this.value = value;
		this.N = 1;
	}

	public int getAux() {
		return this.aux;
	}

	public void setAux(int value) {
		this.aux = value;
	}
}

ㆍ 노드는 키, 값 그리고 자식에 대한 참조 변수인 left, right를 가지고 있다.
ㆍ 자신과 자식 노드의 개수에 대한 변수인 N이 있다.
ㆍ 노드의 높이를 알려주는 변수인 aux, 부모에 대한 참조 변수인 parent를 가지고 있다.

 

treeSearch() 메서드

protected Node<K, V> treeSearch(K key) {
	Node<K, V> x = root;

	while (true) {
		int cmp = key.compareTo(x.key);

		if (cmp == 0)
			return x;

		else if (cmp < 0) {
			if (x.left == null)
				return x;
			else
				x = x.left;
		}

		else {
			if (x.right == null)
				return x;
			else
				x = x.right;
		}
	}
}

ㆍ 특정 키를 입력받아, 그 키를 갖는 노드 또는 순회의 마지막 노드를 반환하는 메서드이다.

ㆍ 연산은 루트부터 시작되며, 입력받은 키보다 작을 경우 왼쪽으로 클 경우 오른쪽으로 이동하며 순회한다.

 

get() 메서드

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;
}

ㆍ 특정 키가 트리에 있을 경우 키에 대응하는 값을 반환한다.
ㆍ 키가 없을 경우 null을 반환한다.

 

put() 메서드

public void put(K key, V value) {
	if (root == null) {
		root = new Node<K, V>(key, value);
		return;
	}
	Node<K, V> x = treeSearch(key);

	int cmp = key.compareTo(x.key);

	if (cmp == 0)
		x.value = value;
	else {
		Node<K, V> newNode = new Node<K, V>(key, value);

		if (cmp < 0)
			x.left = newNode;
		else
			x.right = newNode;

		newNode.parent = x;

		rebalanceInsert(newNode);
	}
}

ㆍ 입력받은 키를 검색 후 있으면 값만 바꿔준다.
ㆍ 없을 경우 새로운 노드를 추가한다.

 

resetSize() 메서드

protected void rebalanceInsert(Node<K, V> x) {
	resetSize(x.parent, 1);
	}

protected void rebalanceDelete(Node<K, V> p, Node<K, V> delete) {
	resetSize(p, -1);
}

private void resetSize(Node<K, V> x, int value) {
	for (; x != null; x = x.parent)
		x.N += value;
}

ㆍ 입력받은 노드부터 루트 노드까지의 N변수를 1씩 증가시켜주는 메서드이다.

 

keys() 메서드

public Iterable<K> keys() {
	if (root == null)
		return null;

	ArrayList<K> keyList = new ArrayList<K>(size());
	inorder(root, keyList);
	return keyList;
}

ㆍ inorder 순회를 이용하여 트리의 모든 키를 ArrayList에 추가한다.
ㆍ ArrayList를 반환 함으로써 키의 정렬된 리스트를 반환한다.

 

inorder() 메서드

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);
	}
}

ㆍ 입력받은 노드부터 자식 노드까지의 모든 키값을 inorder 순회하여 ArrayList에 추가한다.
ㆍ ArrayList를 반환 함으로써 정렬된 키를 반환한다.

 

delete() 메서드

public void delete(K key) {
	if (root == null)
		return;

	Node<K, V> y, p;
	Node<K, V> x = treeSearch(key);

	if (!key.equals(x.key))
		return;

	if (x == root || isTwoNode(x)) {
		if (isLeaf(x)) { 
			root = null;
			return;
		} else if (!isTwoNode(x)) { 
			root = (x.right == null) ? x.left : x.right;
			root.parent = null;
			return;
		} else {
			y = min(x.right);
			x.key = y.key;
			x.value = y.value;

			p = y.parent;
			relink(p, y.right, y == p.left);
			rebalanceDelete(p, y);
		}
	} else {
		p = x.parent;
		if (x.right == null)
			relink(p, x.left, x == p.left);
		else if (x.left == null)
			relink(p, x.right, x == p.left);
		
		rebalanceDelete(p, x);
	}
}

ㆍ 삭제하고자 하는 키가 없는 경우 그냥 반환한다.
ㆍ 삭제하려는 노드가 루트 노드이며 리프 노드인 경우 노드를 null로 만든다.
ㆍ 그냥 루트 노드인 경우 자식 노드를 루트로 만든다.
ㆍ 자식이 둘인 노드일 경우에는 inorder successor로 대체하며, 기존의 inorder successor 위치의 노드는 삭제한다.
ㆍ 자식 노드의 수가 1 이하이고 루트도 아닐 경우에는 자식 노드를 삭제할 노드의 부모의 자식으로 만든다.

 

relink() 메서드

protected void relink(Node<K, V> parent, Node<K, V> child, boolean makeLeft) {
	if (child != null)
		child.parent = parent;
	if (makeLeft)
		parent.left = child;
	else
		parent.right = child;
}

ㆍ 특정 노드의 삭제 연산이 이루어질 경우에 호출되는 메서드이다.
ㆍ 삭제할 노드의 자식이 존재한다면 자식을 삭제할 노드의 부모의 자식으로 만든다.
ㆍ makeLeft가 참이라면 부모의 왼쪽 자식으로, 거짓이라면 오른쪽 자식으로 만든다.

---

참고 문헌 및 자료

ㆍ R.Sedgewick and K. Wayne, Algorithms (4th Ed.), Addison-Wesley.

ㆍ E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, Silicon Press, 2nd Edition.

---

GitHub - qlsdud0604/algorithm-study: 자료구조 및 알고리즘 공부 기록 공간