DevAlgorithm

[Data Structure] Binary Search Tree

  1. 1. 이진 탐색 Tree (Binary Search Tree)
    1. 1.1. 데이터의 탐색
    2. 1.2. 데이터 삽입
    3. 1.3. 데이터 삭제
      1. 1.3.1. 삭제할 Node가 단말 Node일 경우
      2. 1.3.2. 삭제할 Node의 자식 Node가 하나일 경우
      3. 1.3.3. 삭제할 Node의 자식 Node가 두 개일 경우
    4. 1.4. 구현
  2. 2. 참조

이진 탐색 Tree (Binary Search Tree)

이진 탐색 Tree는 데이터의 삽입, 삭제, 탐색 등이 자주 발생하는 경우에 효율적인 구조이다.

같은 값을 갖는 Node가 없어야 한다. 왼쪽 Sub Tree에 있는 모든 데이터는 현재 Node의 값보다 작고,

오른쪽 Sub Tree에 있는 모든 Node의 데이터는 현재 Node의 값보다 크다.

데이터의 탐색

Root에서부터 탐색이 시작되며 Root node의 데이터가 찾으려는 데이터보다 작으면 오른쪽 Sub Tree를 탐색하고 찾으려는 데이터보다 크면 왼쪽 Subtree를 탐색한다.

데이터 삽입

Binary Search Tree에서의 데이터 삽입은 탐색을 통해 이루어지며, 탐색에 성공하면 데이터 삽입에 실패한다. (Binary tree는 같은 데이터를 갖는 Node가 없어야 하기 때문)

탐색에 실패할 경우 데이터를 삽입하며, 아래와 같은 과정을 거친다.

  1. 삽입하려는 데이터가 Root node의 데이터보다 작으면 왼쪽 Subtree로.
  2. 왼쪽 Subtree의 Root node보다 크면 오른쪽 Subtree로.
  3. 만약에 단말 Node를 만난다면 더 이상 탐색은 진행하지 않는다.
  4. 단말 Node보다 작으면 단말 Node의 왼쪽 자식 Node로, 단말 Node보다 크면 단말 Node의 오른쪽 자식 Node로 새 Node를 삽입한다.

데이터 삭제

데이터 삭제는 삭제할 Node의 위치에 따라 세 가지 케이스로 구분된다.

삭제할 Node가 단말 Node일 경우

부모 Node에서 삭제할 Node를 가리키는 링크를 제거하면 된다.

삭제할 Node의 자식 Node가 하나일 경우

부모 Node가 삭제할 Node의 자식 Node를 가리키게 한 후 제거하면 된다.

삭제할 Node의 자식 Node가 두 개일 경우

삭제할 Node를 왼쪽 Sub Tree에서 가장 큰 Node로 대체하거나 오른쪽 Sub Tree에서 가장 작은 Node로 대체한 후 원래 Node를 삭제한다.

이거 이해하는데 시간이 걸렸다. 멍청해 멍청해…

구현

Node는 아래와 같이 꾸미고,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Node {
	private int mData;
	
	private Node leftNode;
	private Node rightNode;
	
	Node(int data) {
		mData = data;
	}
	
	public Node getLeftNode() {
		return leftNode;
	}
	
	public Node getRightNode() {
		return rightNode;
	}
	
	public void setLeftNode(Node newNode) {
		leftNode = newNode;
	}
	
	public void setRightNode(Node newNode) {
		rightNode = newNode;
	}
	
	public int getData() {
		return mData;
	}
	
	public void setData(int data) {
		mData = data;
	}
}

BST (Binary Search Tree)는 아래와 같이 꾸민다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
public class BinarySearchTree {
	private Node mRootNode;
	
	BinarySearchTree(Node newNode) {
		mRootNode = newNode;
	}
	
	public Node getRoot() {
		return mRootNode;
	}
	
	public void insertNode(Node newNode) {
		
		Node offset = mRootNode; // 반복적 탐색 알고리즘을 이용
		
		while (offset != null) {
			if (offset.getData() == newNode.getData()) {
				System.out.println("insert fail because same data. BST regulation violation.");
				return;
			}
			if (newNode.getData() < offset.getData()) {
				if (offset.getLeftNode() == null) {
					offset.setLeftNode(newNode);
					return;
				} else {
					offset = offset.getLeftNode(); 
				}
			} else {
				if (offset.getRightNode() == null) {
					offset.setRightNode(newNode);
					return;
				} else {
					offset = offset.getRightNode();
				}
			}
			
		}
	}
	
	// 순환적 탐색 알고리즘을 이용
	public Node searchNode(Node curNode, int data) {
		if (curNode == null) {
			return null;
		}
		
		if (curNode.getData() == data) {
			return curNode;
		}
		
		if (curNode.getLeftNode() == null && curNode.getRightNode() == null) {
			System.out.println("search fail. BST is not contained this element."); 
			return null;
		}
		if (data < curNode.getData()) {
			return searchNode(curNode.getLeftNode(), data);
		}
		
		// data > curNode.getData()
		return searchNode(curNode.getRightNode(), data);
	}
	
	public void deleteNode(int data) {
		deleteTarget(mRootNode, data);
	}
	public Node deleteTarget(Node curNode, int data) {
		if (curNode == null) {
			return null;
		}
		
		if (data < curNode.getData()) {
			curNode.setLeftNode(deleteTarget(curNode.getLeftNode(), data));
		} else if (data > curNode.getData()) {
			curNode.setRightNode(deleteTarget(curNode.getRightNode(), data));
		} else {
			// found!!
			// parent has no or one node.
			if (curNode.getLeftNode() == null) {
				return curNode.getRightNode();
			} else if (curNode.getRightNode() == null) {
				return curNode.getLeftNode();
			}
			
			// parent has two nodes. find smallest nodes in right tree.
			Node temp = curNode.getRightNode();
			while (temp != null) {
				if (temp.getLeftNode() != null) {
					temp = temp.getLeftNode();
					continue;
				}
				curNode.setData(temp.getData());
				temp = null;
			}
			curNode.setRightNode(deleteTarget(curNode.getRightNode(), data));
		}
		return curNode;
	}
}

Main에서 Tree 생성 후 실행해보면

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class Main {
	public static void main(String[] args) {
		
		BinarySearchTree bst = new BinarySearchTree(new Node(20));
		
		System.out.println("making tree...");
		bst.insertNode(new Node(10));
		bst.insertNode(new Node(4));
		bst.insertNode(new Node(15));
		bst.insertNode(new Node(2));
		bst.insertNode(new Node(7));
		bst.insertNode(new Node(5));
		bst.insertNode(new Node(15));
		bst.insertNode(new Node(12));
		bst.insertNode(new Node(18));
		bst.insertNode(new Node(30));
		bst.insertNode(new Node(25));
		bst.insertNode(new Node(22));
		bst.insertNode(new Node(23));
		bst.insertNode(new Node(27));
		bst.insertNode(new Node(26));
		bst.insertNode(new Node(36));
		bst.insertNode(new Node(33));
		bst.insertNode(new Node(34));
		bst.insertNode(new Node(50));
		bst.insertNode(new Node(60));
		
		System.out.println("print some nodes...");
		System.out.println(bst.getRoot().getData());
		System.out.println(bst.getRoot().getLeftNode().getData());
		System.out.println(bst.getRoot().getLeftNode().getLeftNode().getData());
		System.out.println(bst.getRoot().getLeftNode().getLeftNode().getLeftNode().getData());
		System.out.println(bst.getRoot().getLeftNode().getLeftNode().getRightNode().getData());
		
		System.out.println("delete node data \'4\'");
		bst.deleteNode(4);
		try {
			System.out.println("print some nodes...");
			System.out.println(bst.getRoot().getData());
			System.out.println(bst.getRoot().getLeftNode().getData());
			System.out.println(bst.getRoot().getLeftNode().getLeftNode().getData());
			System.out.println(bst.getRoot().getLeftNode().getLeftNode().getLeftNode().getData());
			System.out.println(bst.getRoot().getLeftNode().getLeftNode().getRightNode().getData());
			System.out.println("search some datas...");
			System.out.println(bst.searchNode(bst.getRoot(), 2).getData());
			System.out.println(bst.searchNode(bst.getRoot(), 30).getData());
			System.out.println(bst.searchNode(bst.getRoot(), 25).getData());
			System.out.println(bst.searchNode(bst.getRoot(), 11).getData());
			System.out.println(bst.searchNode(bst.getRoot(), 9).getData());
		} catch (NullPointerException e) {
			System.out.println("null");
		}
	}
}

각각 아래와 같은 결과를 얻을 수 있다.

making tree...
insert fail because same data. BST regulation violation.
print some nodes...
20
10
4
2
7
delete node data '4'
print some nodes...
20
10
5
2
7
search some datas...
2
30
25
search fail. BST is not contained this element.
null

참조

Share