[자료구조&알고리즘] 이진 탐색 트리(2) ※ 이진 탐색 트리 (Binary Search Trees) - 원소 삭제하는 과정 1. 키(key)를 이용해 노드를 찾는다. - 해당 키 노드가 없을 경우 삭제할 것도 없음 - 찾은 노드의 부모 노드도 알고 있어야 함 2. 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리 구조 정리 이와 관련되어 있지만 보다 심화과정을 배우고 싶다면 AVL 트리, Red-black 트리 를 학습하면 좋음 기타/What I Learned 2021.10.15
[자료구조&알고리즘] 이진 탐색 트리(1) ※ 이진 탐색 트리(Binary Search Trees) - 이진 트리의 일종. 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진 트리임 정렬된 배열을 이용한 이진 탐색과 비교했을때, 장점으로는 데이터 원소의 추가와 삭제가 비교적 용이 단점으로는 공간 소요가 크다는 점이 있음 데이터 표현 - 각 노드는 (key, value) 한 쌍으로 구성되어 있음 이로 인한 특징은 키를 이용해서 검색이 가능하고 보다 복잡한 데이터 레코드로 확장이 가능함 연산의 정의 - insert(key, data) : 트리에 주어진 데이터 원소 추가 remove(key) : 특정 원소를 트리로부터 삭제 lookup(key) : 특정 원소를 .. 기타/What I Learned 2021.10.14