Binary Search Tree
모든 노드가 아래의 조건을 만족하는 이진 트리
- 모든 data는 서로 다른 값을 갖는다.
- 왼쪽 자식 노드 <= 부모 <= 오른쪽 자식 노드
탐색
탐색순서
- root의 data와 탐색 대상 data를 비교한다
- 1의 결과에 따라 아래 작업 중 하나를 수행한다.
- root.data = data : 원소를 찾았으므로 탐색연산 성공
- root.data < data : root노드의 오른쪽 서브트리에서 탐색연산수행
- root.data > data : root노드의 왼쪽 서브트리에서 탐색연산수행
탐색코드
주목 포인트!
1. node를 parent와 child로 구분해서 사용한다.
parent : 아래 조건 2,3을 만족한 노드
child : parent의 자식 노드이고 2,3의 조건 만족여부를 수행해야하는 노드
2. while문 수행전후로 child의 역할이 달라진다.
while문 : 자식노드(child)의 존재여부 (null이 아닌지)
if문 : 탐색대상 data와 현재노드(child)를 비교
// 트리의 root와 탐색대상 data를 인자로 받는다.
BST.prototype.search = function(node, data){
let parent = node; // 비교가 끝난 부모노드
let child = node; // 현재 비교할 대상노드
// 1. 자식노드가 없을 때까지 while문을 수행
while(child !== null){
// 2. 탐색대상data와 현재노드 data비교
// 2-1. 찾으려는 data가 현재노드보다 작을 때
if(data < child.data){
parent = child;
child = child.left
// 2-2. 찾으려는 data가 현재노드보다 클 때
}else if(data > child.data){
parent = child;
child = child.right;
// 2-3. 찾으려는 data가 현재노드일 때
}else return parent === child? [parent,null]:[parent, child];
}
}탐색 조건
1. 자식노드가 없을 때까지 while문 수행
- while문의 비교식에서 child는 아직 자식노드이다.
- while문의 비교식을 통해 parent의 자식노드가 존재한다는 것을 확인한다.
- parent의 자식노드가 존재한다는걸 확인 했으니 while문 내부에서 자식노드인 child를 현재노드(비교대상)로 본다.
- while문의 내부에서의 child는 현재노드이다.
2. 탐색대상 data와 현재노드를 비교한다.
- 여기서 child는 현재노드이다.
2-1. 찾으려는 data가 현재 노드보다 작을 때
- 현재노드의 left를 현재 노드에 담는다.
- 조건을 만족하면 현재노드인 child가 parent가 되고, 조건을 자식노드 child.left는 child다 된다.
2-2. 찾으려는 data가 현재 노드보다 클 때
- 현재노드의 right를 현재 노드에 담는다.
- 조건을 만족하면 현재노드인 child가 parent가 되고, 조건을 자식노드 child.right는 child다 된다.
2-3. 찾으려는 data가 현재노드일 때
- 부모와 자식이 같으면 parent만 return (root === data)
- 다르면 parent와 child를 return (child가 탐색대상 data)
삽입
삽입순서
- 탐색 : data 삽입 전 BST에 중복 data 있는지 확인하기 위해 먼저 탐색한다.
- 탐색 결과
- 탐색 성공 : 중복data가 있으므로 삽입연산을 수행하지 않는다.
- 탐색 실패 : 중복data가 없으므로 삽입연산을 수행한다.
삽입코드
주목 포인트!
1. insertKey에서의 root
첫 호출에서 root는 트리의 root를 의미하지만, 재귀호출에서 root는 비교할 현재노드를 가리킨다
// 트리 생성
const BST = function(){
this.root = null;
}
// 노드 생성
const Node = function(data) {
this.data = data;
this.left = null;
this.right = null;
}
BST.prototype.insertBST = function(data){
1-1**
let insert = this.insertKey(this.root, data);
this.root = insert;
}
BST.prototype.insertKey = function(node, data){
const root = node;
const newNode = new Node(data);
// 1. 현재노드(root)가 빈노드면 삽입대상 노드생성 후 return
// 빈트리일경우 or 다음 자식노드가 없을 경우
if(root === null)
return newNode;
// 2. 삽입대상 data와 현재노드의 data 비교
// 2-1. 삽입대상 data가 현재 노드보다 작을 때
if(data < root.data){
1-2**
root.left = this.insertKey(root.left,data);
return root;
// 2-2. 삽입대상 data가 현재 노드보다 클 때
}else if(data > root.data){
1-2**
root.right = this.insertKey(root.right,data);
return root;
// 2-3. 삽입대상 data가 현재 노드가 같을 때
}else return node;
}
// 실행코드
const bts = new BST();
bts.insertBST(5);삽입 조건
1. 현재노드(root)가 빈노드일 때
- 삽입한 data로 노드 생성 후 return
- 조건에 만족하는 경우는 빈 트리일 때 or 다음 자식노드가 없을 때
1-1.빈 트리일 때 : data가 root가 된다.
let insert = newNode;
this.root = insert;1-2. 다음 자식노드가 없을 때 : data가 현재노드의 right나 left로 삽입된다.
- 이전 재귀호출의 return 값으로 삽입된다.
- return root를 통해 재귀호출을 한 부모 root > 부모 root > ...
root.left = newNode;
return root;2. 삽입대상 data와 현재노드의 data 비교
2-1. 삽입대상 data가 현재 노드보다 작을 때
- 현재노드의 left와 data를 인자로 넘겨 insertKey를 재귀호출
- 재귀호출한 값을 부모의 left에 담아 부모를 return한다.
2-2. 삽입대상 data가 현재 노드보다 클 때
- 현재노드의 right와 data를 인자로 넘겨 insertKey를 재귀호출
- 재귀호출한 값을 부모의 right에 담아 부모를 return한다.
2-3. 삽입대상 data가 현재노드일 때
- 트리에 삽입 data와 중복되는 data가 있다는 것.
- node(root)를 반환한다.
삭제
삭제순서
- 탐색 : data 삭제 전 data의 위치를 확인하기 위해 먼저 탐색한다.
- 삭제할 노드의 차수에 따라 아래 작업 중 하나를 수행한다.
- 삭제할 노드가 단말 노드일 경우 (차수 0)
- 삭제할 노드가 1개의 자식노드를 가질 경우 (차수 1)
- 삭제할 노드가 2개의 자식노드를 가질 경우 (차수 2)
삭제코드
주목 포인트!
1. search를 먼저 수행하고 탐색결과(삭제할 노드)를 받는다.
parent : 삭제할 노드의 부모노드
child : 삭제할 노드
2. temp역할(임시저장)을 하는 변수
parent : 2,3에서 parent는 child에 대한 temp역할을 한다.
root : 2,3에서 root는 삭제할 노드가 있는 위치를 가르키고 있는 temp역할을 한다.
// 트리 생성
const BST = function(){
this.root = null;
}
// 노드 생성
const Node = function(data) {
this.data = data;
this.left = null;
this.right = null;
}
BST.prototype.deleteBST = function(data){
let findNode = this.search(this.root, data);
// 탐색의 3-3 return 값 참조
let parent = findNode[0];
let child = findNode[1]===null? parent : findNode[1];
const root = child;
// child는 현재노드(삭제할 노드)
// 1. 삭제할 노드의 차수가 0일 때
if(child.left === null && child.right === null){
parent.data > child.data? parent.left = null: parent.right = null;
// 2. 삭제할 노드의 차수가 1일 때
}else if(child.left === null || child.right === null){
parent = child;
if(parent.left !== null){
child = child.left;
root.data = child.data; //**2
parent.left = null;
}else{
child = child.right;
root.data = child.data; //**2
parent.right = null;
}
// 3. 삭제할 노드의 차수가 2일 때
}else if(child.left !== null && child.right !== null){
parent = child;
child = child.right;
let flag = true;
while(child.left !== null && child.right !== null){
parent = child;
child = child.left;
flag = false;
}
root.data = child.data;
flag === true ? parent.right === null: parent.left === null;
}
}
// 실행코드
const bts = new BST();
bts.insertBST(5);
bts.insertBST(4);
bts.insertBST(3);
bts.deleteBST(5);삭제 조건
1. 삭제할 노드의 차수가 0일 때
- parent와 child의 data를 비교해 삭제할 child의 방향에 null을 넣어 연결을 끊는다.
2. 삭제할 노드의 차수가 1일 때
/* 5
* / \
* 4 6
* /
* 3
*/ delete 4-
- 삭제할 노드의 위치에 삭제할 노드의 자식노드를 담는다.
/* child = child.left; * 5 * / \ * 4 6 * / * 3 */ root.data = 4 / child.data = 3 -
-
삭제할 노드의 위치에 자식노드의 data를 담는다.
/* root.data = child.data; * 5 * / \ * 3 6 * / * 3 */ root.data = 3 / child.data = 3root.data가 아닌 parent.data를 써도 동일한 작업을 수행한다. 굳이 조건문에서 참조되지 않는 root를 불러와서 사용하는 것보다 조건문에 있는 parent.data를 쓰는게 더 깔끔하다고 생각했다.
하지만 parent와 child는 조건문 수행하는데 필요한 계속 변경되는 부모노드와 자식 노드이고, root는 삭제되는 노드의 위치를 명시한 변경되지 않는 값으로 생각하니 root.data를 사용하는게 코드의 유지보수에 있어 더 좋은 것 같다.
-
- 삭제할 노드가 있는 위치에서 자식노드의 방향을 끊는다.(null)
/* parent.left = null * 5 * / \ * 3 6 */
3. 삭제할 노드의 차수가 2일 때
- 노드의 차수가 2일 때, 왼쪽과 오른쪽 노드 중 어떤 방향의 노드를 부모(삭제된 노드)의 위치에 올릴지 선택해야한다.
- 노드의 right 자식노드를 선택한다.
child = child.right;
let flag = true;- 1에서 선택된 right의 노드도 차수가 있을 수 있다. right노드의 차수가 2이면, right 노드의 자식중 left 노드를 선택한다.
child = child.left;
flag = false;- 2에서 선택된 left노드도 차수가 있을 수 있다. left노드의 차수가 2가 아닐 때까지 2의 작업을 반복한다.
while(child.left !== null && child.right !== null)- flag로 삭제된 노드의 위치에 올라간 자식 노드를 끊어준다.
flag === true ? parent.right === null: parent.left === null;전체코드
const BST = function(){
this.root = null;
}
// 노드 생성
const Node = function(data) {
this.data = data;
this.left = null;
this.right = null;
}
BST.prototype.search = function(node, data){
let parent = node; // 비교가 끝난 부모노드
let child = node; // 현재 비교할 대상노드
// 1. 자식노드가 없을 때까지 while문을 수행
while(child !== null){
// 2. 탐색대상data와 현재노드 data비교
// 2-1. 찾으려는 data가 현재노드보다 작을 때
if(data < child.data){
parent = child;
child = child.left
// 2-2. 찾으려는 data가 현재노드보다 클 때
}else if(data > child.data){
parent = child;
child = child.right;
// 2-3. 찾으려는 data가 현재노드일 때
}else return parent === child? [parent,null]:[parent, child];
}
}
BST.prototype.insertBST = function(data){
let insert = this.insertKey(this.root, data);
this.root = insert;
}
BST.prototype.insertKey = function(node, data){
const root = node;
const newNode = new Node(data);
// 1. 현재노드(root)가 빈노드면 삽입대상 노드생성 후 return
// 빈트리일경우 or 다음 자식노드가 없을 경우
if(root === null)
return newNode;
// 2. 삽입대상 data와 현재노드의 data 비교
// 2-1. 삽입대상 data가 현재 노드보다 작을 때
if(data < root.data){
root.left = this.insertKey(root.left,data);
return root;
// 2-2. 삽입대상 data가 현재 노드보다 클 때
}else if(data > root.data){
root.right = this.insertKey(root.right,data);
return root;
// 2-3. 삽입대상 data가 현재 노드가 같을 때
}else return node;
}
BST.prototype.deleteBST = function(data){
let findNode = this.search(this.root, data);
// 탐색의 3-3 return 값 참조
let parent = findNode[0];
let child = findNode[1]===null? parent : findNode[1];
const root = child;
// child는 현재노드(삭제할 노드)
// 1. 삭제할 노드의 차수가 0일 때
if(child.left === null && child.right === null){
parent.data > child.data? parent.left = null: parent.right = null;
// 2. 삭제할 노드의 차수가 1일 때
}else if(child.left === null || child.right === null){
parent = child;
if(parent.left !== null){
child = child.left;
root.data = child.data;
parent.left = null;
}else{
child = child.right;
root.data = child.data;
parent.right = null;
}
// 3. 삭제할 노드의 차수가 2일 때
}else if(child.left !== null && child.right !== null){
parent = child;
child = child.right;
let flag = true;
while(child.left !== null && child.right !== null){
parent = child;
child = child.left;
flag = false;
}
root.data = child.data;
flag === true ? parent.right === null: parent.left === null;
}
}
// 실행코드
const bts = new BST();
bts.insertBST(5);
bts.insertBST(4);
bts.insertBST(3);
연봉킹이 되고 싶은 개발자