Data Structures & Algorithms with Javascript : Binary Trees and Binary Search Trees

2024.07.24 - [🤖 data structures & algorithms] - Data Structures & Algorithms with Javascript : Sets

Data Structures & Algorithms with Javascript : Sets

[이전 글]2024.07.23 - [🤖 data structures & algorithms] - Data Structures & Algorithms with Javascript : Hashing Data Structures & Algorithms with Javascript : Hashing[이전 글] 2024.07.22 - [🤖 data structures & algorithms] - Data Structures & A

pyotato-dev.tistory.com

🌲 트리는 데이터를 계층적으로 나타낼 때 유용한 비선형 자료 구조다.
트리 자료 구조를 파일 시스템이나 데이터 리스트를 정렬하는데 종종 쓰곤 한다.
오늘은 트리 구조 중 "이진 트리 (binary tree)"에 대해 살펴보자.
이진 트리는 linked list 보다 검색이 빠르고, array보다 데이터 삽입/삭제가 빠르기 때문에 더 선호되는데,

👩🏻‍💻 이진 트리가 무엇인지 알아보고, 자바스크립트 class로 자료 구조와 연산들을 구현해보자.

🌲 트리 자료 구조란?

트리 자료 구조는 node와 edge로 이루어져 있다. 예를 들어 다음 그림의 조직 관계도는 트리 구조로 되어 있다.

각 직함은 node를 나타내고, 각 직함의 관계가 edge에 해당된다.

CIO는 CEO에 직접 보고를 하기 때문에 edge로 연결되어 있고, VP와 CEO또한 같은 관계이므로 edge로 연결되어 있다.

하지만 VP sales와 development manager는 서로 보고를 직접 주고 받는 사이가 아니기 때무네 edge로 연결되어 있지 않고, 직접 관련이 있는 부서가 아니라고 볼 수 있다.

트리의 구성요소를 더 자세히 살펴보기 위해 다음의 트리를 살펴보자.

트리 구조에서 level, root, path, subtree, key,leaf가 각각 어떤 것들에 해당되나?

트리는 계층 구조를 지닌 데이터라고 앞서 이야기했다. 위의 그림처러 level로 각 계층 구조를 나타낼 수 있다.

레벨 0인 최상위 노드는 root라고도 불린다. 루트 노드 아래에 노드들이 있는데, 이 노드들을 child (자식) 노드라고 부른다.

그리고 child 노드 상위의 노드를 parent (부모) 노드라고 부른다. 자식 노드가 없는 노드는 leaf 노드라고 부른다.

오늘은 트리 중에서도 binary tree (이진 트리)에 대해서 살펴볼 건데, 이진 트리는 모든 노드의 자식 노드 개수가 2개 이하인 트리를 일컫는다. 각 노드는 key라고도 불리는 값을 지니고 있다. 하나의 노드 A를 기준으로 왼쪽에 있는 값을 left child of A라고 표현하고, 오른쪽에 있는 자식 노드를 right child of A라고 한다.

각 노드에 직접 연결된 관계를 edge라고 했었는데, 하나의 노드에서 다른 노드로 접근하기 위한 일련의 edge들을 path라고 부른다.

그리고 모든 노드를 특정 순서에 따라 방문하는 과정을 tree traversal(트리 순회)라고 부른다.

🌲 Binary Tree(이진트리)와 Binary Search Tree(이진 탐색 트리)

이진 트리는 자식 노드의 개수가 2개 이하로 제한된 트리 구조라는 것을 살펴봤다.

자식 노드의 개수를 최대 2개로 제한하면 데이터를 삽입, 삭제 그리고 검색하는 과정이 효율적이다.

왜냐하면 값을 왼쪽 또는 오른쪽 노드로만 저장할 수 있기 때문이다.

이진 탐색 트리는 자식 노드를 더 상세한 분류 기준으로 저장한 이진 트리다.

이진 탐색 트리는 2개 이하의 자식 노드를 갖는 것과 함께, 항상 작은 키 값이 왼쪽에 있고, 오른쪽으로 갈수록 큰 값으로 이루어진다.

🔍 이진 탐색 트리(BST) 구현

이진 탐색 트리는 노드로 구성된다. 먼저 노드 클래스를 만들어 보자. 노드 클래스는 linked list와 유사한 구조다.

‼ 예제는 책의 구현을 참고하여 클래스로 재구성했습니다!!

Node 클래스는 왼쪽 오른쪽에 저장할 노드 참조와 현재 노드 데이터를 보여줄 show 메서드로 구성된다.

class Node{
	constructor(data, left, right){
		this.data = data;
        this.left = left;
        this.right = right;
	}
    
    // 현재 노드의 데이터 보여주기 
	show(){
    	return this.data;
    }
}

BST 클래스는 루트 노드 멤버와 노드를 추가하는 메서드인 insert로 구성된다.

class BST{
	constructor(){
    	this.root = null;
    }
    
    // 노드 추가
	insert(data){
    	let n = new Node(data,null,null); // 추가할 노드 생성
        if(this.root == null){ // 루트가 비어 있다면 추가할 노드를 루트 노드로 할당
        	this.root = n;
        } else {
        	let current = this.root; // 루트가 비어 있지 않다면 현재 루트를 기준으로
            let parent;
            while(true){
            	parent = current;	// 부모를 현재 루트 노드로 하고
                if(data < current.data){	// 현재 데이터가 부모를 기준으로 작다면
                	current = current.left; 
                    if(current == null){
                    	parent.left = n; // 부모 노드 기준 왼쪽에 할당한다
                        break;
                    }
                } else {
                	current = current.right; // 현재 데이터가 부모를 기준으로 크다면
                    if(current == null){	
                    	parent.right = n; // 부모 노드 기준으로 오른쪽으로 할당
                        break;
                    }
                }
            }
        
        }
    
    }
}

🎄 BST 순회

BST에 노드를 추가하는 연산까지 살펴봤다. 트리가 계층 구조라는 점을 살려서 데이터를 볼 수 있으면 좋을 거 같다.

BST를 순회하는 방식에는 3가지가 있다:

Inorder : 모든 노드의 키를 오름차순으로 방문

Preorder : 루트 먼저 방문 => 루트 노드 왼쪽 subtree 자식 노드들 => 루트 노드 오른쪽 subtree 자식 노드들 방문

Postorder : 왼쪽 리프 방문 =>해당 subtree 자식 노드 방문 => 오른쪽 subtree 자식 노드 방문 => 루트 맨 마지막에 방문

👩🏻‍💻 BST 순회 구현

순회 코드는 기본적으로 재귀함수를 바탕으로 한다.

// inorder traversal
function inOrder(node){
    if(!(node == null)){
        inOrder(node.left);	
        print(node.show());
        inOrder(node.right);
    }
}

// preOrder traversal
function preOrder(node){
    	if(!(node == null)){
        	print(node.show());
        	preOrder(node.left);
			preOrder(node.right);
        }
    }
    
	// postOrder traversal
function postOrder(node){
    	if(!(node == null)){
        	postOrder(node.left);
			postOrder(node.right);
            print(node.show());
        }
    }

전체 코드

class Node{
	constructor(data, left, right){
		this.data = data;
        this.left = left;
        this.right = right;
	}
    
    // 현재 노드의 데이터 보여주기 
	show(){
    	return this.data;
    }
}

class BST{
	constructor(){
    	this.root = null;
    }
    
    // 노드 추가
	insert(data){
    	let n = new Node(data,null,null); // 추가할 노드 생성
        if(this.root == null){ // 루트가 비어 있다면 추가할 노드를 루트 노드로 할당
        	this.root = n;
        } else {
        	let current = this.root; // 루트가 비어 있지 않다면 현재 루트를 기준으로
            let parent;
            while(true){
            	parent = current;	// 부모를 현재 루트 노드로 하고
                if(data < current.data){	// 현재 데이터가 부모를 기준으로 작다면
                	current = current.left; 
                    if(current == null){
                    	parent.left = n; // 부모 노드 기준 왼쪽에 할당한다
                        break;
                    }
                } else {
                	current = current.right; // 현재 데이터가 부모를 기준으로 크다면
                    if(current == null){	
                    	parent.right = n; // 부모 노드 기준으로 오른쪽으로 할당
                        break;
                    }
                }
            }
        
        }
    
    }
}

// 출력 유틸 함수
function print(item){
		console.log(item);
}

// inorder traversal
function inOrder(node){
    if(!(node == null)){
        inOrder(node.left);
        print(node.show());
        inOrder(node.right);
    }
}
	// preOrder traversal
function preOrder(node){
    	if(!(node == null)){
        	print(node.show());
        	preOrder(node.left);
			preOrder(node.right);
        }
    }
    
	// postOrder traversal
function postOrder(node){
    	if(!(node == null)){
        	postOrder(node.left);
			postOrder(node.right);
            print(node.show());
        }
    }
  
let nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
print("Inorder traversal:");
inOrder(nums.root);
print("Preorder traversal:");
preOrder(nums.root);
print("Postorder traversal:");
postOrder(nums.root);

순회 결과 살펴보기

/**
Inorder traversal:
3
16
22
23
37
45
99
Preorder traversal:
23
16
3
22
45
37
99
Postorder traversal:
3
22
16
37
99
45
23 
*/

트리 노드 추가 과정

let nums = new BST();

nums.insert(23); -----> root [23]
\
nums.insert(45);          [45]

nums.insert(16); root [23]
/ \
[16] [45]
                                 /
nums.insert(37);                    [37]

nums.insert(3); root [23]
/ \
[16] [45]
/ /
[3] [37]

nums.insert(99); root [23]
/ \
[16] [45]
/ / \
[3] [37] [99]

nums.insert(22); root [23]
/ \
         [16] [45]
   / \ / \
         [3] [22] [37] [99]

트리 순회 과정

          root [23]
a    / \ b
[16]    [45]
c   / \ d   e / \ f
[3] [22] [37] [99]

Inorder traversal:
path : c => d => a =>    e   => f
노드 방문 : [3] [16] [22] [23] [37] [45] [99]

Preorder traversal:
path : a =>    c   =>    d    =>    e   =>    f
노드 방문 : [23] [16] [3] [22] [45] [37] [99]
Postorder traversal:
path : c =>    d    =>    e    =>    f    =>    a
노드 방문 : [3] [22] [16] [37] [99] [45] [23]

inorder, preorder, postorder 순회 비교

inorder, preorder,postorder bst traversal

🔍 BST 탐색

bst 탐색에 주로 활용되는 예는 크게 다음 3가지 경우가 있다

특정 값 찾기
최소 값 찾기
최대 값 찾기

최대/최소 값 찾기

BST에서 최대/최소값은 비교적 간단한 방식으로 저장된다.

값이 작을 수록 왼쪽 자식 노드에 저장되기 때문에 BSt의 최소값을 찾기 위해서는

BST의 왼쪽 edge를 순회하면서 맨 마지막 노드를 찾으면 된다.

최소 값을 구하기 위한 메서드 getMin()를 다음과 같이 구현해볼 수 있다.

getMin(){
	let current = this.root;			// 루트 노드로부터 시작해서 
    while(!(current.left == null)){		// 더 이상 왼쪽 자식 노드가 없을 때까지 검색
    	current = current.left;
    }
    return current.data;		// 맨 왼쪽의 leaf 노드가 가장 작은 값이므로 리턴
}

최대 값은 반대로 가장 오른쪽의 leaf 노드를 찾으면 된다.

getMax(){
	let current = this.root;
    while(!(current.right == null)){
    	current = current.right;
    }
	return current.data;
}

👇 전체 코드!

class Node{
	constructor(data, left, right){
		this.data = data;
        this.left = left;
        this.right = right;
	}
    
    // 현재 노드의 데이터 보여주기 
	show(){
    	return this.data;
    }
}

class BST{
	constructor(){
    	this.root = null;
    }
    
    // 노드 추가
	insert(data){
    	let n = new Node(data,null,null); // 추가할 노드 생성
        if(this.root == null){ // 루트가 비어 있다면 추가할 노드를 루트 노드로 할당
        	this.root = n;
        } else {
        	let current = this.root; // 루트가 비어 있지 않다면 현재 루트를 기준으로
            let parent;
            while(true){
            	parent = current;	// 부모를 현재 루트 노드로 하고
                if(data < current.data){	// 현재 데이터가 부모를 기준으로 작다면
                	current = current.left; 
                    if(current == null){
                    	parent.left = n; // 부모 노드 기준 왼쪽에 할당한다
                        break;
                    }
                } else {
                	current = current.right; // 현재 데이터가 부모를 기준으로 크다면
                    if(current == null){	
                    	parent.right = n; // 부모 노드 기준으로 오른쪽으로 할당
                        break;
                    }
                }
            }
        
        }
    
    }
	////////////////////////////////////////////////// 💖 추가 ////////////////////////////////////////////////// 
    
    getMin(){
    	let current = this.root;			// 루트 노드로부터 시작해서 
            while(!(current.left == null)){		// 더 이상 왼쪽 자식 노드가 없을 때까지 검색
            	current = current.left;
            }
        return current.data;		// 맨 왼쪽의 leaf 노드가 가장 작은 값이므로 리턴
    }


  getMax(){
	let current = this.root;
        while(!(current.right == null)){
        	current = current.right;
        }
	return current.data;
  }
  
  ////////////////////////////////////////////////// 💖 추가 ////////////////////////////////////////////////// 
    
}

// 출력 유틸 함수
function print(item){
		console.log(item);
}

// inorder traversal
function inOrder(node){
    if(!(node == null)){
        inOrder(node.left);
        print(node.show());
        inOrder(node.right);
    }
}
	// preOrder traversal
function preOrder(node){
    	if(!(node == null)){
        	print(node.show());
        	preOrder(node.left);
			preOrder(node.right);
        }
    }
    
	// postOrder traversal
function postOrder(node){
    	if(!(node == null)){
        	postOrder(node.left);
			postOrder(node.right);
            print(node.show());
        }
    }
  
let nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);

let min = nums.getMin();
let max = nums.getMax();

print(`bst nums의 최소값: ${min}, 최대값: ${max}`);
// bst nums의 최소값: 3, 최대값: 99

특정 값 찾기

bst에서 특정 값을 찾기 위해서는 현재 노드와 찾으려는 값 간의 대소 비교가 필요하다.

대소 비교를 통해 찾으려는 값이 현재 노드보다 크다면 오른쪽 노드로 이동하고,

찾으려는 값이 작다면 현재 노드 기준 왼쪽 노드로 이동해서 찾으면 된다.

find() 메서드를 구현했던 클래스에 추가해보자.

find(data){
	let current = this.root;
    while(current.data != data){
    	if(data < current.data){	// 찾으려는 값이 현재 노드보다 작다면 
        	current = current.left;	// 왼쪽 서브 트리로 이동해서 검색
        } else {
        	current = current.right;	// 오른쪽으로 이동해서 검색
        }
        
        if(current == null){
        	return null;
        }
    }
    return current;
}

👇 전체 코드!

class Node{
	constructor(data, left, right){
		this.data = data;
        this.left = left;
        this.right = right;
	}
    
    // 현재 노드의 데이터 보여주기 
	show(){
    	return this.data;
    }
}

class BST{
	constructor(){
    	this.root = null;
    }
    
    // 노드 추가
	insert(data){
    	let n = new Node(data,null,null); // 추가할 노드 생성
        if(this.root == null){ // 루트가 비어 있다면 추가할 노드를 루트 노드로 할당
        	this.root = n;
        } else {
        	let current = this.root; // 루트가 비어 있지 않다면 현재 루트를 기준으로
            let parent;
            while(true){
            	parent = current;	// 부모를 현재 루트 노드로 하고
                if(data < current.data){	// 현재 데이터가 부모를 기준으로 작다면
                	current = current.left; 
                    if(current == null){
                    	parent.left = n; // 부모 노드 기준 왼쪽에 할당한다
                        break;
                    }
                } else {
                	current = current.right; // 현재 데이터가 부모를 기준으로 크다면
                    if(current == null){	
                    	parent.right = n; // 부모 노드 기준으로 오른쪽으로 할당
                        break;
                    }
                }
            }
        
        }
    
    }
	
    
    getMin(){
    	let current = this.root;			// 루트 노드로부터 시작해서 
            while(!(current.left == null)){		// 더 이상 왼쪽 자식 노드가 없을 때까지 검색
            	current = current.left;
            }
        return current.data;		// 맨 왼쪽의 leaf 노드가 가장 작은 값이므로 리턴
    }


  getMax(){
	let current = this.root;
        while(!(current.right == null)){
        	current = current.right;
        }
	return current.data;
  }
  
  ////////////////////////////////////////////////// 💖 추가 ////////////////////////////////////////////////// 
  
  find(data){
	let current = this.root;
    while(current.data != data){
    	if(data < current.data){	// 찾으려는 값이 현재 노드보다 작다면 
        	current = current.left;	// 왼쪽 서브 트리로 이동해서 검색
        } else {
        	current = current.right;	// 오른쪽으로 이동해서 검색
        }
        
        if(current == null){
        	return null;
        }
    }
    return current;
}
  
  
  ////////////////////////////////////////////////// 💖 추가 ////////////////////////////////////////////////// 
}

// 출력 유틸 함수
function print(item){
		console.log(item);
}

// inorder traversal
function inOrder(node){
    if(!(node == null)){
        inOrder(node.left);
        print(node.show());
        inOrder(node.right);
    }
}
	// preOrder traversal
function preOrder(node){
    	if(!(node == null)){
        	print(node.show());
        	preOrder(node.left);
			preOrder(node.right);
        }
    }
    
	// postOrder traversal
function postOrder(node){
    	if(!(node == null)){
        	postOrder(node.left);
			postOrder(node.right);
            print(node.show());
        }
    }
  
let nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);

let findValues = [3,12,25,23,33,45,99];

findValues.forEach((value)=>{
    let hit = nums.find(value);
    print(`value ${value} ${hit==null?"is not":""} in bst`);
})
/**
value 3  in bst
value 12 is not in bst
value 25 is not in bst
value 23  in bst
value 33 is not in bst
value 45  in bst
value 99  in bst
*/

BST에서 노드 제거

BST 연산 중에서 가장 복잡한 연산은 노드를 제거하는 과정이다. 노드 제거의 복잡도는 어떤 노드를 제거하고 싶냐에 따라 달라진다. leaf 노드를 제거하고 싶은 경우 제거 코드를 비교적 간단하게 구현할 수 있다.

하지만 자식 노드가 하나 있다면 좀 더 복잡해지고, 자식 노드가 둘이라면 더욱 더 복잡해진다.

노드 삭제의 복잡도를 낮추기 위해 노드를 재귀적으로 제거하는 과정으로 간소화해보고자 한다.

노드를 제거하기 위한 메서드는 두가지다 : remove()와 removeNode()

구현 논리

1. 현재 노드가 우리가 삭제하려는 노드를 포함하고 있는가? => 해당 노드 삭제

2. 아니라면 현재노드와 우리가 삭제하려는 노드 비교

2 - 1. 삭제하고자하는 노드가 현재 노드보다 작다면 왼쪽 자식 노드로 이동해서 비교

2 - 2. 삭제하고자하는 데이터가 현재 노드보다 크다면 오른쪽 자식 노드로 이동해서 비교

고려사항

1. 제거하려는 노드가 leaf인 경우 => 해당 노드의 parent node가 null을 가리키도록

2. 제거하려는 노드가 하나의 자식 노드가 있는 경우 => 자식 노드가 제거하려는 노드의 부모 노드를 가르키도록

3. 제거하려는 노드가 두 개의 자식 노드가 있는 경우

3 - 1. 제거한 노드의 왼쪽에서 subtree 중 가장 큰 값을 찾거나

3 - 2. 제거한 노드의 오른쪽에서 subtree 중 가장 작은 값을 찾기 ( ☑️ 선택 )

4. subtree의 최소값을 구하는 함수 => 임시 최소 값을 지닌 노드 구해서 현재

class Node{
	constructor(data, left, right){
		this.data = data;
        this.left = left;
        this.right = right;
	}
    
    // 현재 노드의 데이터 보여주기 
	show(){
    	return this.data;
    }
}

class BST{
	constructor(){
    	this.root = null;
    }
    
    // 노드 추가
	insert(data){
    	let n = new Node(data,null,null); // 추가할 노드 생성
        if(this.root == null){ // 루트가 비어 있다면 추가할 노드를 루트 노드로 할당
        	this.root = n;
        } else {
        	let current = this.root; // 루트가 비어 있지 않다면 현재 루트를 기준으로
            let parent;
            while(true){
            	parent = current;	// 부모를 현재 루트 노드로 하고
                if(data < current.data){	// 현재 데이터가 부모를 기준으로 작다면
                	current = current.left; 
                    if(current == null){
                    	parent.left = n; // 부모 노드 기준 왼쪽에 할당한다
                        break;
                    }
                } else {
                	current = current.right; // 현재 데이터가 부모를 기준으로 크다면
                    if(current == null){	
                    	parent.right = n; // 부모 노드 기준으로 오른쪽으로 할당
                        break;
                    }
                }
            }
        
        }
    
    }
	
    
    getMin(){
    	let current = this.root;			// 루트 노드로부터 시작해서 
            while(!(current.left == null)){		// 더 이상 왼쪽 자식 노드가 없을 때까지 검색
            	current = current.left;
            }
        return current.data;		// 맨 왼쪽의 leaf 노드가 가장 작은 값이므로 리턴
    }


  getMax(){
	let current = this.root;
        while(!(current.right == null)){
        	current = current.right;
        }
	return current.data;
  }

      
  find(data){
	let current = this.root;
    while(current.data != data){
    	if(data < current.data){	// 찾으려는 값이 현재 노드보다 작다면 
        	current = current.left;	// 왼쪽 서브 트리로 이동해서 검색
        } else {
        	current = current.right;	// 오른쪽으로 이동해서 검색
        }
        
        if(current == null){
        	return null;
        }
    }
    return current;
}
  
  
  ////////////////////////////////////////////////// 💖 추가 ////////////////////////////////////////////////// 
    remove(data){
        this.root = this.removeNode(this.root, data);
    }

    removeNode(node, data){
        if(node == null){
            return null;
        }
        if(data == node.data){
            // 노드가 자식이 없을 경우
            if(node.left == null && node.right == null){
                return null;
            }
            // 노드가 왼쪽 자식이 없을 경우
            if(node.left == null){
                return node.right;
            }
           // 노드가 오른쪽 자식이 없을 경우
            if(node.right == null){
                return node.left;
            }
            // 노드가 자식이 두개안 경우
            let tempNode = this.getMin();
            node.data = tempNode.data;
            node.right = this.removeNode(node.right, tempNode.data);
            return node;
        }
        else if(data< node.data){
            node.left = this.removeNode(node.left, data);
            return node;
        } else {
            node.right = this.removeNode(node.right,data);
            return node;
        }
        
    }
  
  ////////////////////////////////////////////////// 💖 추가 ////////////////////////////////////////////////// 
}

// 출력 유틸 함수
function print(item){
		console.log(item);
}

// inorder traversal
function inOrder(node){
    if(!(node == null)){
        inOrder(node.left);
        print(node.show());
        inOrder(node.right);
    }
}
	// preOrder traversal
function preOrder(node){
    	if(!(node == null)){
        	print(node.show());
        	preOrder(node.left);
			preOrder(node.right);
        }
    }
    
	// postOrder traversal
function postOrder(node){
    	if(!(node == null)){
        	postOrder(node.left);
			postOrder(node.right);
            print(node.show());
        }
    }
  
let nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);

// let findValues = [3,12,25,23,33,45,99];
// findValues.forEach((value)=>{
//     let hit = nums.find(value);
//     print(`value ${value} ${hit==null?"is not":""} in bst`);
// })
nums.remove(23);
inOrder(nums.root);

/**
3
16
22
undefined
37
45
99

*/

// 맨 왼쪽의 리프 제거
nums.remove(3);
inOrder(nums.root);
/**
16
22
23
37
45
99
*/

// 맨 오른쪽의 리프 제거
nums.remove(99);
inOrder(nums.root);
/**
3
16
22
23
37
45
*/

nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);

nums.remove(37);

// 오른쪽 자식이 하나인 노드 제거
nums.remove(45);
inOrder(nums.root);

/**
3
16
22
23
99
*/

let nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);

nums.remove(3);
inOrder(nums.root);
print('왼쪽 자식이 하나인 노드 제거')
// 왼쪽 자식이 하나인 노드 제거
nums.remove(16);
inOrder(nums.root);
/**
16
22
23
37
45
99
VM540:127 왼쪽 자식이 하나인 노드 제거
22
23
37
45
99
*/

nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);

// 자식 노드가 두 개인 노드 제거 
nums.remove(16);
inOrder(nums.root);

/**
3
undefined
22
23
37
45
99
*/

빈도수 카운트

어떤 숫자가 발생하는 빈도수를 체크할 때 bst를 활용할 수 있다.예를 들면 학생들 성적 분포를 bst로 나타낼 수 있는데, 점수가 bst에 없다면 추가해주고, 있다면 해당 노드의 빈도수++을 해주면 된다.

그러기 위해서는 Node 클래스가 빈도수 데이터를 갖도록 살짝 변경을 해줘야 한다.

class Node{
	constructor(data,left,right){
    	this.data = data;
        this count = 1;	/** 💖 추가 */
        this.left = left;
        this.right = right;
    }
	show(){
    	return this.data;
    }
}

성적 노드가 BST에 추가되면 빈도수 카운트는 1로 초기화된다.

BST 노드 insert시 빈도수도 증가하도록 update 메서드를 추가해주자.

// 노드 추가 시 빈도수 ++
update(data){
	let grade = this.find(data);
    grade.count ++;
    return grade;
}

👇 전체 코드!

class Node{
	constructor(data, left, right){
		this.data = data;
        this.left = left;
        this.right = right;
        this.count = 1;
	}
    ////////////////////////////////////////////////// 💖 추가 ////////////////////////////////////////////////// 
    // 현재 노드의 데이터 보여주기 
	show(){
    	return [`${this.data}점`, this.count];
    }
    ////////////////////////////////////////////////// 💖 추가 ////////////////////////////////////////////////// 
}

class BST{
	constructor(){
    	this.root = null;
    }
    
    // 노드 추가
	insert(data){
    	let n = new Node(data,null,null); // 추가할 노드 생성
        if(this.root == null){ // 루트가 비어 있다면 추가할 노드를 루트 노드로 할당
        	this.root = n;
        } else {
        	let current = this.root; // 루트가 비어 있지 않다면 현재 루트를 기준으로
            let parent;
            while(true){
            	parent = current;	// 부모를 현재 루트 노드로 하고
                if(data < current.data){	// 현재 데이터가 부모를 기준으로 작다면
                	current = current.left; 
                    if(current == null){
                    	parent.left = n; // 부모 노드 기준 왼쪽에 할당한다
                        break;
                    }
                } else {
                	current = current.right; // 현재 데이터가 부모를 기준으로 크다면
                    if(current == null){	
                    	parent.right = n; // 부모 노드 기준으로 오른쪽으로 할당
                        break;
                    }
                }
            }
        
        }
    
    }
	
    
    getMin(){
    	let current = this.root;			// 루트 노드로부터 시작해서 
            while(!(current.left == null)){		// 더 이상 왼쪽 자식 노드가 없을 때까지 검색
            	current = current.left;
            }
        return current.data;		// 맨 왼쪽의 leaf 노드가 가장 작은 값이므로 리턴
    }


  getMax(){
	let current = this.root;
        while(!(current.right == null)){
        	current = current.right;
        }
	return current.data;
  }

      
  find(data){
	let current = this?.root;
    if(current?.data == null) return null;
    while(current.data != data){
    	if(data < current.data){	// 찾으려는 값이 현재 노드보다 작다면 
        	current = current.left;	// 왼쪽 서브 트리로 이동해서 검색
        } else {
        	current = current.right;	// 오른쪽으로 이동해서 검색
        }
        
        if(current == null){
        	return null;
        }
    }
    return current;
}
  
    remove(data){
        this.root = this.removeNode(this.root, data);
    }

    removeNode(node, data){
        if(node == null){
            return null;
        }
        if(data == node.data){
            // 노드가 자식이 없을 경우
            if(node.left == null && node.right == null){
                return null;
            }
            // 노드가 왼쪽 자식이 없을 경우
            if(node.left == null){
                return node.right;
            }
           // 노드가 오른쪽 자식이 없을 경우
            if(node.right == null){
                return node.left;
            }
            // 노드가 자식이 두개안 경우
            let tempNode = this.getMin();
            node.data = tempNode.data;
            node.right = this.removeNode(node.right, tempNode.data);
            return node;
        }
        else if(data< node.data){
            node.left = this.removeNode(node.left, data);
            return node;
        } else {
            node.right = this.removeNode(node.right,data);
            return node;
        }
        
    }
  
  ////////////////////////////////////////////////// 💖 추가 ////////////////////////////////////////////////// 

// 노드 추가 시 빈도수 ++
update(data){
	let grade = this.find(data);
    grade.count ++;
    return grade;
}
  ////////////////////////////////////////////////// 💖 추가 ////////////////////////////////////////////////// 
    
}

const arr =[];

////////////////////////////////////////////////// 💖 추가 ////////////////////////////////////////////////// 

// 출력 유틸 함수, 두번째 인자를 true로 넘기면 table 형식으로 출력
function print(item,table=false){
		!table?console.log(item):console.table(item);
}
////////////////////////////////////////////////// 💖 추가 ////////////////////////////////////////////////// 

// inorder traversal
function inOrder(node){
    if(!(node == null)){
        inOrder(node.left);
        arr.push(node.show());
        // print(node.show());
        inOrder(node.right);
    }
}
// preOrder traversal
function preOrder(node){
    	if(!(node == null)){
        	print(node.show());
        	preOrder(node.left);
			preOrder(node.right);
        }
    }
    
	// postOrder traversal
function postOrder(node){
    	if(!(node == null)){
        	postOrder(node.left);
			postOrder(node.right);
            print(node.show());
        }
    }
  

////////////////////////////////////////////////// 💖 추가 ////////////////////////////////////////////////// 

let grades = new BST();
const scores = Array.from({length: 100},()=>Math.floor(Math.random()*101));
scores.forEach((score)=>{
    let scoreExists = grades.find(score);
    if(scoreExists == null){
        grades.insert(score);
    } else {
        grades.update(score);
    }
});
inOrder(grades.root);

print(arr,true);

////////////////////////////////////////////////// 💖 추가 //////////////////////////////////////////////////

출력 결과

🍀 마치면서

TMI...traversal gif 삽입 중 에러 발생 ㅜㅜ 이미 글을 등록한 상태라서 자동 저장이 안돼서 bst 탐색 이전부터 글을 두번 쓰는 중 ㅜㅜㅜㅜ
bst에 대해서는 확실히 알고 가는 시간이 된 거 같다 😂😂😂😂😂😂

📚 Reference

'🤖 data structures & algorithms' 카테고리의 다른 글

Data Structures & Algorithms with Javascript : Sorting Algorithms (Basic) (0)	2024.07.27
Data Structures & Algorithms with Javascript : 중간(?) 점검 🍪 (0)	2024.07.25
Data Structures & Algorithms with Javascript : Sets (2)	2024.07.24
Data Structures & Algorithms with Javascript : Hashing (0)	2024.07.23
Data Structures & Algorithms with Javascript : Dictionaries (0)	2024.07.22

🥕 pyotato's dev farm

Data Structures & Algorithms with Javascript : Binary Trees and Binary Search Trees

🌲 트리 자료 구조란?

🌲 Binary Tree(이진트리)와 Binary Search Tree(이진 탐색 트리)

🔍 이진 탐색 트리(BST) 구현

🎄 BST 순회

Inorder : 모든 노드의 키를 오름차순으로 방문

Preorder : 루트 먼저 방문 => 루트 노드 왼쪽 subtree 자식 노드들 => 루트 노드 오른쪽 subtree 자식 노드들 방문

Postorder : 왼쪽 리프 방문 =>해당 subtree 자식 노드 방문 => 오른쪽 subtree 자식 노드 방문 => 루트 맨 마지막에 방문

👩🏻‍💻 BST 순회 구현

🔍 BST 탐색

최대/최소 값 찾기

특정 값 찾기

BST에서 노드 제거

구현 논리

빈도수 카운트

🍀 마치면서

📚 Reference

'🤖 data structures & algorithms' 카테고리의 다른 글

티스토리툴바

Data Structures & Algorithms with Javascript : Binary Trees and Binary Search Trees

🌲 트리 자료 구조란?

🌲 Binary Tree(이진트리)와 Binary Search Tree(이진 탐색 트리)

🔍 이진 탐색 트리(BST) 구현

🎄 BST 순회

Inorder : 모든 노드의 키를 오름차순으로 방문

Preorder : 루트 먼저 방문 => 루트 노드 왼쪽 subtree 자식 노드들 => 루트 노드 오른쪽 subtree 자식 노드들 방문

Postorder : 왼쪽 리프 방문 =>해당 subtree 자식 노드 방문 => 오른쪽 subtree 자식 노드 방문 => 루트 맨 마지막에 방문

👩🏻‍💻 BST 순회 구현

🔍 BST 탐색

최대/최소 값 찾기

특정 값 찾기

BST에서 노드 제거

구현 논리

빈도수 카운트

🍀 마치면서

📚 Reference

'🤖 data structures & algorithms' 카테고리의 다른 글

'🤖 data structures & algorithms' Related Articles

티스토리툴바