이진 트리7 [Javascript] 이진 탐색 트리 가장 활용도가 높은 이진 탐색트리를 자바스크립트로 구현해보겠습니다. 2021.09.30 - [Programming/자료구조] - 이진 탐색 트리 이진 탐색 트리 처음에 트리를 소개하며 조직도이야기를 했듯이, 트리라는 자료구조는 어떤 자료를 찾는데 이점을 갖는 구조입니다. 하지만 트리의 높이가 높아지면 탐색하는데 오래걸리거나, 위치를 안다고 bamtory29.tistory.com 중복 코드와 로직부분은 private 멤버 함수로 선언했습니다. 코드가 좀 많이 길지만 내용은 간단합니다. 재귀를 통해 삽입, 삭제, 검색에서 연산을 진행하도록 설계했습니다. class Tree { constructor() { this.root;//루트 노드 this.size = 0;//트리 크기 } _insertNode(root.. 2021. 11. 18. 힙 Heap 힙(Heap) 혹은 히프는 완전 이진 트리 종류 중 하나 입니다. 히프는 여태까지 트리를 계속 해서 연결 자료구조로 구현한 것과는 다르게 1차원 배열을 이용해서 구현할 수 있는 자료구조 이기도 합니다. 1. 힙 Heap 힙은 이진 트리의 노드들 중에서 키값이 가장 큰 값또는 가장 작은 값을 찾기 위한 자료구조입니다. 이때 가장 큰 값을 찾으면 최대 힙, 가장 작은 값을 찾으면 최소 힙이라고 합니다. 또 다른 특징은 힙은 같은 키값을 가진 노드를 가질 수 없다는 점 입니다. 그래서 최대 힙에서는 가장 큰 키값을 가진 노드가 루트 노드가 되고, 최소 힙에서는 가장 작은 키값을 가진 노드가 루트 노드가 됩니다. 힙을 1차원 배열로 구현하기 때문에 배열의 인덱스를 통해 트리간의 부모 자식관계를 쉽게 알 수 있다.. 2021. 10. 2. AVL 트리 이진 탐색 트리는 트리 구조마다 연산시간이 천차만별입니다. 다음 그림처럼 같은 노드를 가져도 구조에 따라서 연산시간이 다르게 됩니다. 같은 3개의 노드, 같은 요소인데도 8이라는 요소를 탐색 할 때 왼쪽 편향 트리는 노드를 2번 거치는 연산을 하고, 오른쪽 그림의 이진 트리는 오른쪽으로 한 번 이동하는 연산만을 수행하면 됩니다. 이처럼 노드가 늘어날수록 그 차이가 커집니다. 이처럼 노드가 늘어나서 불균형해질수록 이진 트리의 연산횟수가 증가하는 단점이 있는데, 이 단점을 보완한 트리를 균형 이진 탐색 트리 혹은 균형 트리라고 합니다. 이 균형 트리에는 B 트리, AVL 트리 2-3-4 트리 등이 있는데 오늘은 이 중에서 AVL 트리에 대해서 알아보려고 합니다. 1. AVL 트리 Adelson-Velskii.. 2021. 10. 1. 이진 탐색 트리 처음에 트리를 소개하며 조직도이야기를 했듯이, 트리라는 자료구조는 어떤 자료를 찾는데 이점을 갖는 구조입니다. 하지만 트리의 높이가 높아지면 탐색하는데 오래걸리거나, 위치를 안다고 해도 도달하는데 연산이 필요합니다. 그래서 우리는 트리를 특정 기준으로 나누어서 만들려고 합니다. 이것이 이진 탐색 트리입니다. 1. 이진 탐색 트리 이진 탐색 트리는 트리를 실제로 사용하기 위해 정의한 구조입니다. 이때 특정 기준에 따라서 트리 노드를 정렬하는데 보통 노드의 원소 크기를 기준으로 정렬합니다. 이때 노드의 원소를 우리는 키(key)라고 부르고, 이 값에 따라 탐색 등의 연산을 실행하게 됩니다. 우리는 종종 업앤 다운 게임을 합니다. 특정 숫자를 부르고 이 숫자보다 특정 숫자가 크면 업, 작으면 다운이라고 말하죠.. 2021. 9. 30. 이진 트리의 순회 지난 포스트에서 이진 트리를 구현해 보면서, 트리 삽입 과정에서 문제가 발생했었습니다. 트리의 하위 트리가 존재하는 경우 그 아래 트리의 메모리가 반환되지 않아 메모리 낭비가 일어나는 과정이었는데요. 이 과정을 순회 라는 개념으로 해결할 수 있다고 했었습니다. 1. 순회 순회는 트리의 모든 노드를 중복이나 빠지는 것 없이 처리하는 연산입니다. 그동안 우리가 다뤘던 스택, 큐같은 자료구조들을 자료가 1:1 구성을 가졌기에 따로 순회할 필요가 없었습니다. 그러나 트리는 1:다수의 관계이기 때문에 현재 노드에서 어떤 다음 노드를 처리할지에 대한 연산이 필요하며, 이 연산을 순회라고 합니다. 순회는 루트 노드의 방문 순서를 기준으로 세 가지 종류로 나뉩니다. 전위 순회 중위 순회 후위 순회 전위 순회는 루트 노.. 2021. 9. 27. 이진 트리 구현 두개의 포스트에 걸쳐서 이진 트리를 설명했으니 드디어 구현에 들어가볼 차례입니다. 1. 배열로 이진 트리 구현하기? 트리도 배열을 이용해서 구현할 수는 있습니다. 그림처럼 노드에 번호를 부여하고 배열의 인덱스와 노드 번호를 일치시켜 데이터를 저장하죠. 다시 말하자면 배열의 크기를 (노드의 수+1) 만큼 잡고 인덱스 0번을 제외한 나머지 번호를 이용해서 구현합니다. 하지만 크기 가변이 힘들고, 위와 같은 그림의 완전 이진 트리가 아닌경우에, 비는 인덱스가 생긴다는 등의 문제로 인해서 일반적으로 트리를 배열로 구현하지는 않습니다. 물론 이진 트리 마지막에 소개드릴 '히프'라는 자료구조가 있는데, 이 구조에서 배열을 이용하게 됩니다. 2. 연결 리스트로 이진 트리 구현하기 노드 특히 양방향 노드를 이용하면 이.. 2021. 9. 24. 이전 1 2 다음 300x250
