본문 바로가기

728x90

tree5

[Data Structure] B-Tree란? 안녕하세요 Foma 💻 입니다! 오늘은 트리 자료구조 중 균형 끝판왕 (이름 자체가 Balanced - Tree)인 B-Tree에 대해 알아보겠습니다. 바로 시작할게요~ B-Tree의 배경 B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. - 위키 백과 - 즉, 이진 트리를 조금 더 효율적으로 확장한 자료구조에요! 이진 탐색 트리는 최악의 경우 O(n)의 시간 복잡도를 갖기 때문에 그것을 조금 더 효율적으로 만든 것이 O(logn)의 시간 복잡도를 갖는 AVL 트리였습니다. 하지만 만약 2천만개의 데이터가 있다면 log20,000,000 = 24 즉, 최대 2.. 2021. 12. 6.

[Data Structure] AVL 트리 구현해보기 (feat. Swift) 안녕하세요 Foma 💻 입니다! 저번 시간에 AVL 트리가 뭔지 이론에 대해 알아보았는데요. (혹시 안보신 분들은 여기 에서 확인해주세요!) 오늘은 AVL 트리를 직접 구현해보려고 합니다. 바로 시작할게요~ AVLNode 기본적으로 이진탐색트리의 노드와 똑같지만 왼쪽과,오른쪽 자식의 높이와 밸런스 팩터를 측정할 변수를 따로 만들어었습니다. class AVLNode { var value:T var leftChild:AVLNode? var rightChild:AVLNode? var height:Int = 0 var leftHeight:Int { return leftChild?.height ?? -1 } var rightHeight:Int { return rightChild?.height ?? -1 } var.. 2021. 12. 6.

[Data Structure] AVL(Adelson-Velsky and Landis) 트리란? 안녕하세요 Foma 💻 입니다! 오늘은 저번에 정리했던 이진 탐색 트리를 더 업그레이드(?)한 자료구조인 AVL 트리에 대해서 알아보도록 하겠습니다. (혹시 이진 탐색 트리에 대해 모르시는 분들은 여기 에서 보고 와주세요!) 바로 시작할게요~ AVL(Adelson-Velsky and Landis) 트리란? 🤔 컴퓨터 과학에서 AVL 트리(발명자의 이름인 Adelson-Velsky and Landis에서 따온 이름)는 스스로 균형을 잡는 이진 탐색 트리이다. 스스로 균형을 잡는 데이터 구조 중 처음으로 발명되었다. AVL 트리에서, 두 자식 서브트리의 높이는 항상 최대 1만큼 차이난다. 만약 어떤 시점에서 높이 차이가 1보다 커지면 이 속성을 유지하기 위해서 스스로 균형을 잡는다. - 위키 백과 - 즉, .. 2021. 12. 1.

[Data Structure] 이진 탐색 트리(Binary Search Tree) 구현해보기 (feat.Swift) 안녕하세요 Foma 💻 입니다! 저번 시간에 이진 탐색 트리가 뭔지 이론에 대해 알아보았는데요. 오늘은 이진 탐색 트리를 직접 구현해보려고 합니다. 바로 시작할게요~ BSTNode 이진 탐색 트리의 노드를 만들어 주겠습니다. 노드는 값,왼쪽,오른쪽 자식의 노드 정보를 가지고 있습니다. class BSTNode { var value:T var leftChild:BSTNode? var rightChild:BSTNode? init(value:T) { self.value = value } } Binary Search Tree 이진 탐색 트리의 최상단 값을 가질 root를 프로퍼티로 정의했습니다. struct BinarySearchTree { var root:BSTNode? Insert public mutatin.. 2021. 11. 18.

[Data Structure] 이진 탐색 트리(Binary Search Tree)란? 안녕하세요 Foma 💻 입니다! 오늘은 트리 자료구조 중 효율적인 검색,삽입,삭제를 할 수 있는 이진 탐색 트리에 대해서 알아보겠습니다. 바로 시작할게요~ 이진 트리(Binary Tree)란? 🤔 이진 탐색 트리는 이진 트리 자료구조로 되어있기 때문에 먼저 이진 트리가 뭔지에 대해 알아보겠습니다. 이진 트리는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.... - 위키 백과 - 즉, 노드마다 자식이 2개 이하인 트리를 말합니다. 아래 그림처럼 이루어진 트리를 말합니다. (자식이 없어도 되고, 하나여도 되고, 두 개여도 됩니다.) 이진 탐색 트리(Binary Search Tree)란? 🧐 이진 탐색 트리는 다음과 같은 속.. 2021. 11. 17.

이전 1 다음

728x90

티스토리툴바