- 각 노드는 (키, 값)의 쌍을 저장하며, 서로 다른 노드의 키는 다르다.
- 부모의 키는 왼쪽 서브트리에 저장된 노드의 키보다 크다.
- 부모의 키는 오른쪽 서브트리에 저장된 노드의 키보다 작다.
동작 과정
- 검색: 루트부터 비교.
작으면 왼쪽, 크면 오른쪽. 같으면 발견.- 삽입: 검색 후, 있으면 수정. 없으면 추가.
장점
- 심볼 테이블을 정렬된 순서로 유지할 필요 없다.
- 새로 삽입되는 노드는 항상 리프 노드에 위치
문제점
- Balanced tree를 지원하지 못함
- Too many seeks
24개의 key 로 구성된 tree: 5번의 seek
예시
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)
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()
- Put: 검색 후, 키가 있으면 reset. 없으면 추가
- 비용: 비교 횟수 = 노드의 레벨
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);
}
}