이진탐색트리
-
[ Open Data Structure ] - An Unbalanced Binary Search Tree (불균형 이진탐색트리) - 3DataStructure 2020. 12. 29. 15:54
본격적으로 Binary Search Tree 중 Unbalanced Binary Search Tree를 살펴봅니다. Binary Search Tree의 Property는 Tree 내부의 어떤 데이터 x를 빠르게 특정해준다는 점에서 상당히 유용합니다. 그렇다면 바로 Tree 내부의 어떤 데이터 x를 찾는 코드를 살펴보도록 합니다. 그 전에 몇 가지 간단한 규칙부터 공부하는 편이 좋습니다. 여기서 x는 임의의 데이터를 가리키고 u는 임의의 node이며 u.x란 node u가 가진 데이터를 이릅니다. 1. 만약, x left로 진행합니다. 2. 만약, x> u.x라면 탐색 과정은 u->right로 진행합니다. 3. 만약, x == u.x라면 데이터 x를 가진 node u를 찾아..
-
[ Open Data Structure ] An Unbalanced Binary Search Tree - ( 불균형 이진탐색트리) - 2DataStructure 2020. 12. 26. 22:26
전에 첨부한 Figure 2.3의 Application Class의 Private엔 두 가지의 Member variable이 있었는데 하나는 Application을 다루기 위한 Integer type의 mCommand였으며 다른 하나는 An Unbalanced Binary Search Tree의 모든 Implementatios와 Root Node를 포함한 정보를 가진 데이터였습니다(Figure 3.1). BinaryTree는 BinaryTree의 Implemetations를 포함한 Class입니다. 이 Class 안에는 마침내 Binary Search Tree의 Root node의 정보가 다음과 같이 들어 있습니다. Figure 3.2에서처럼 Root node를 포인터로 선언했기 때문에 Class의 Co..
-
[Open Data Structure] - An Unbalanced Binary Search Tree (불균형 이진 탐색 트리) - 1DataStructure 2020. 12. 26. 21:17
그래프의 일종이며 기본적인 형태는 다음과 같습니다. 이는 Computer Science(CS)의 가장 기초를 이루는 구조 중 하나입니다. Tree라는 이름이 붙은 이유는 자료의 구조를 설명하기 위해 그림을 그리면 종종 나무와 나뭇가지를 닮은 구조를 얻을 수 있기 때문입니다. 수학적으로 이 구조를 정의하면 다음과 같습니다. A binary tree is a connected, undirected, finite graph with no cycles, and no vertex of degree greater than three. 각 Vertex(정점 또는 꼭지점)는 세 개 미만의 연결을 가지고 연결되어 있습니다. 또, Graph theory에서 Cycle이란 Simple Circuit이라고도 하는데 어떤 경로..