개발공부

[알고리즘] AVL Tree(트리) : 필수기본정리 - Balanced Factor, 4가지 Rotation(회전), 삽입, 제거, Kotlin구현

목차 AVL 트리 개념 우선 AVL 트리는 이진 탐색 트리를 기초로 합니다. 이진 탐색 트리에 대하여 자세히 알고 싶으시다면 아래 링크를 확인해주세요 [알고리즘] Binary Search Tree 이진탐색 트리 : 기본정리 - 탐색,삽입,삭제, 검색연산, 삭제연산 - Kotlin 목차 이진 탐색 트리(BSF - Binary Search Tree) 이진 탐색 트리는 시간 복잡도에서 log(n) 오퍼레이션 이기 때문에 선형 데이터 구조보다 빠른 검색을 가능하게 하고, 데이터를 삽입하거나 지울 수 있게 underdog11.tistory.com 위 포스트를 보셨다면 이진 탐색트리의 단점은 불균형한 트리 모형을 하고 있을 때 트리의 성능이 O(log n)에서 O(n)으로 떨어진다는 것을 알 수 있었습니다. AVL..

[알고리즘] Binary Search Tree 이진탐색 트리 : 필수기본정리 - 탐색,삽입,삭제, 검색연산, 삭제연산 - Kotlin

목차 이진 탐색트리를 알아보기전 이진트리와 익숙하시지않으시다면 아래 포스트를 참고해주세요. [알고리즘] Binary Tree 바이너리 트리: 기본정리 - 바이너리트리 구현, 중위순회, 전위순회, 후위순 목차 바이너리 트리 개념 바이너리 트리는 트리와 같지만 최대 2개의 자식만 가질 수 있는 트리구조입니다. 자식 두 개의 왼쪽을 LeftChild 오른쪽을 rightChild로 부릅니다. 바이너리 트리 구현하기 underdog11.tistory.com 이진 탐색 트리(BSF - Binary Search Tree) 이진 탐색 트리는 시간 복잡도에서 log(n) 오퍼레이션 이기 때문에 선형 데이터 구조보다 빠른 검색을 가능하게 하고, 데이터를 삽입하거나 지울 수 있게 해주는 데이터 구조입니다. 이진 탐색 트리가..

[알고리즘] Binary Tree 이진 트리: 기본정리 - in-order 중위순회, pre-order 전위순회, post-order 후위순회 구현 - Kotlin

목차 이번 포스트에서는 이진 트리에 대해서 알아보겠습니다. 이진 트리를 알아보기전, 트리의 용어와 익숙하시지않으시다면 아래 포스트를 먼저 보고와주세요. [알고리즘] Tree 트리 : 기본정리 - 트리 구성, 깊이우선순회(Depth-First Traversal), 레벨순회(LevelOrderTra 목차 Tree 개념 Tree는 데이터 구조중 하나입니다. 1. 계층구조의 관계를 가진 데이터 구조이고 2. 정리되어 나열된 데이터를 다룰 때 검색이 빠릅니다. 3. Tree에는 사이즈, 모양이 다른 여러 tree들 underdog11.tistory.com 이진 트리 개념 이진 트리는 트리와 같지만 최대 2개의 자식만 가질 수 있는 트리구조입니다. 자식 두 개의 왼쪽을 LeftChild 오른쪽을 rightChild..

[알고리즘] Tree 트리 : 기본정리 - 트리 구성, 깊이우선순회(Depth-First Traversal), 레벨순회(LevelOrderTraversal), 검색(Search) - Kotlin

목차 Tree 개념 Tree는 데이터 구조중 하나입니다. 1. 계층구조의 관계를 가진 데이터 구조이고 2. 정리되어 나열된 데이터를 다룰 때 검색이 빠릅니다. 3. Tree에는 사이즈, 모양이 다른 여러 tree들 이 있습니다. 4. 트리는 노드들과 노드들을 연결하는 링크로 구성되어있습니다. Tree 구성 및 용어 우선 시작하기에 앞서 tree에 구성과 용어들을 살펴보겠습니다. 용어 설명 다이어그램 Node LinkedList와 비슷하게 tree에도 node가 있습니다. 각 node는 데이터를 포함하고있습니다. Parent(부모) / Child(자식) 부모노드는 다수의 자식 노드를 가지고있을수있습니다. 하지만 자식 노드는 하나의 부모만 가지고있을수있습니다. 루트 노드(Root) 트리에 가장 상단에 위치한..