트리란?
정의는 사이클이 발생하지 않으면서 모든 노드끼리 연결되어있는 것이다.
트리는 rooted tree, unrooted tree로 두가지가있다.
노드가 하나라도 트리라고 부를 수 있다.
이진트리란?
이진트리는 자식이 두개가 있는 것이아니라, 자식을 최대 2개로 제한하는 것이다. 1개나 2개가 될 수도 있다.
이진트리는 구현하기가 쉽다 배열로도 구현이 쉽다 i번 노드에 대해서 왼쪽 노드는 i * 2, 오른쪽 노드는 i * 2 + 1이다
반대로 자식들의 부모 노드는 자식 노드에 대해서 /2를 하면된다.
트리의 순회
- 트리의 순회에서는 트리를 만들고 난 뒤 전위순회, 후위순회, 중위순회가 있다.
- 재귀를 통해서 만들 수 있다
만들기
- Tree를 struct구조체로 만들어서 상태를 관리하는데 해당 트리들은 왼쪽 자식 정보, 오른쪽 자식 정보, 현재 노드 위치가 필요하다
struct Tree {
int idx;
int x;
int y;
Tree *Left;
Tree *Right;
};전위 순회
- 전위탐색은 부모 -> 왼쪽 자식 순회 -> 오른쪽자식순으로 탐색인데 여기서 부모를 먼저 색칠한 후 왼쪽 자식들을 방문하고, 그 이후에 오른쪽 자식들을 방문하는 것이다..
후위 순회
- 후위 순회는 해당 루트노드를 마지막으로 검사하겠다는 것이다.
- 그래서 순서가 LEFT- RIGHT - ROOT이다
- 위의 그림에서는
- 처음 '루트' 9에서 왼쪽으로간다 그럼 4번노드가 또 다시 새로운 '루트'가되고 4번의 왼쪽으로 가서 1번노드에 입장한다.
- 1번 노드입장에서는 해당 노드가 왼쪽이기에 1번을 보고 1번 입장에서 '루트인 4번'의 right노드인 3번을 본다
- 또 다시 3번입장에서는 해당 노드가 '루트'노드가 되고 해당 노드의 왼쪽이 없다면 right노드를 보게되고 2번노드를 보게된다.
void PostOrder(Tree * Root, vector<int> &anwer) { if(Root == NULL) return; PostOrder(Root -> Left, anwer); PostOrder(Root -> Right, anwer); anwer.push_back(Root -> idx); }
전위 순회
- 전위순회는 해당 루트노드를 먼저 (전위) 검사하겠다는 의미이다.
- 순서는 root -> left -> right이다
- 루트를 먼저보니 1번을 보고 왼쪽인 2번으로 내려가는데 2번입장에서는 해당 노드가 '루트'노드이기에 해당 노드를 검사하고 다시 왼쪽으로 쭉 쭉 간다 이런식으로 진행하면된다.
void preOrder(Tree * Root, vector<int> &answer) {
if(Root == NULL) return ;
answer.push_back(Root -> idx);
preOrder(Root -> Left, answer);
preOrder(Root -> Right, answer);
}순회에서 문제!! (두종류 순회의 결과를 알고 있다면 한 종류의 결과도 알 수 있다)
이진트리 vs 이진 탐색트리 vs 완전이진트리
이진트리는 노드의 갯수가 최대 2개로 제한되는 것이고 이진 탐색트리는 루트의 왼쪽에는 자신보다 작은 값이 오른쪽은 자신보다 큰 값을 두는 것이다..
완전이진트리는 트리의 모든 값이 왼쪽에서 순서대로 차 있는 것을 의미힌다..
이진탐색트리에서 삽입
null에 도달하기 전까지 계속 진행하여 삽입하려는 값 x가 들어갈 위치를 찾아줘야한다
node가 도달한 null인 지점에서의 parent 정보를 알아야지만, 삽입이 가능하다는 것을 알 수 있다.
node가 null이 되면 parent는 바로 그 위의 부모 노드를 가리킨다.
노드를 추가할 때 3가지 경우가 존재한다
- parent가 null일때 root를 새로운 노드로 정한다.
- parent가 삽입하려는 값보다 더 큰 경우는 삽입하려는 값을 parent의 왼쪽에 넣어두자
- parent < node->data 인경우는 parent의 오른쪽에 두자..
이진 탐색트리에서 삭제
자식이 없는 경우 해당 노드만 그냥 지우면된다.
자식이 하나만 있는 경우 해당 자식을 지울 노드위치로 올리면된다.
자식이 두개가 있을 경우.. 지울려는 노드의 next값(지울려는 노드보다 크면서 최솟값)을 찾아서 next값을 지울려는 node위치에 두고 next를 지우면된다.
20
10 30
25 40
26 50위의 경우에서 20을 지울려고할 때 next는 26이다 그럼 26을 20자리로 올리고 26자리를 지우면된다.
이진 탐색 트리에서 발생할 수 있는 문제점
만약 이진탐색트리가 균형잡혀 있지 않는 경우에서는 시간복잡도가 o(n)이 될 수도 있다. 해당 경우를 방지하기 위해서 노드를 회전 등의 작업을 통해 적절하게 조절하여 왼쪽과 오른쪽 자식간의 높이 차가 크게 벌어지지 않도록 하여 시간복잡도를 줄일 수 있다.
이진 탐색 트리 소스 1
#pragma once
#include <iostream>
using namespace std;
/*
* 10
* 20
* 30
*/
struct Node
{
Node* parent = nullptr;
Node* left = nullptr;
Node* right = nullptr;
int key = 0;
};
class BinarySearchTree
{
public:
void Print_Inorder() { Print_Inorder(_root); }
void Print_Inorder(Node* node);
void Insert(int key);
void Delete(Node* node);
void Replace(Node* u, Node* v);
Node* Search(Node* node, int key);
Node* Min(Node* node);
Node* Max(Node* node);
Node* Next(Node* node);
private:
Node* _root = nullptr;
};
이진 탐색트리 소스2
#include "BinarySearchTree.h"
void BinarySearchTree::Print_Inorder(Node* node)
{
if (node == nullptr)
return;
cout << node->key << endl;
Print_Inorder(node->left);
Print_Inorder(node->right);
}
void BinarySearchTree::Insert(int key)
{
Node* newNode = new Node();
newNode->key = key;
if (_root == nullptr)
{
_root = newNode;
return;
}
Node* node = _root;
Node* parent = _root;
//어디에 놓을 것인지 찾아주기
while (node != nullptr)
{
parent = node;
if (node->key < key)
{
node = node->right;
}
else node = node->left;
}
// 붙이기작업시작..
newNode->parent = parent;
if (key < parent->key)
{
parent->left = newNode;
}
else parent->right = newNode;
}
void BinarySearchTree::Delete(Node* node)
{
//자식이 없으면 그냥 해당 노드만 지우면된다.
//자식이 하나만 있어도 쉽다 해당 자식만 지울 노드위치로
//올리면된다..
//자식이 두명 다 있을때는 조금힘들다..
/*
* 20
* 10 30
* 25 40
* 26 50
*
* 위에서 20을 지울려고하는데 자식이 둘다있다.
* 그래서 20의 successor, next값을 구해서..
* 그값을 20의 위치에 두고 next인 25는 지우기전에
* 26을 25의 위치에올린다..
*/
//자식이 한명만 있을때 왼족인지 오른쪽인지 구분하지않고..
if (node->left == nullptr)
Replace(node, node->right);
else if (node->right == nullptr)
Replace(node, node->left);
else
{
//successor찾기 다음데이터찾기
Node* next = Next(node);
node->key = next->key;
Delete(next);
}
}
//u서브트리를 v서브트리로 교체
void BinarySearchTree::Replace(Node* u, Node* v)
{
if (u->parent == nullptr)
_root = v;
else if (u == u->parent->left)
u->parent->left = v;
else
u->parent->right = v;
if (v)
v->parent = u->parent;
}
Node* BinarySearchTree::Search(Node* node, int key)
{
if (node == nullptr || node->key == key)
return node;
if (key < node->key)
Search(node->left, key);
else
Search(node->right, key);
return nullptr;
}
Node* BinarySearchTree::Min(Node* node)
{
while (node)
{
node = node->left;
}
return node;
}
Node* BinarySearchTree::Max(Node* node)
{
while (node)
{
node = node->right;
}
return node;
}
Node* BinarySearchTree::Next(Node* node)
{
//node의 오른쪽이 존재한다면
if (node->right)
{
return Min(node->right);
}
//node의 오른쪽이 존재하지않는다면..
Node* parent = node->parent;
/*
20
10 30
25 40
26 50
중에서 26다음을 찾을 때 26이 내부모의 왼쪽자식이면
부모를 바로 리턴하면된다.
그렇지 않을 경우 부모중에서 나보다 큰 값을 찾아야한다..
*/
while (parent && node == parent->right)
{
node = parent;
parent = parent->parent;
}
return parent;
}
레드블랙 트리
레드 블랙 트리란?
루트노드는 블랙이다.
모든 리프 노드들은 블랙이다.
레드 노드의 자식은 언제나 블랙이다. 레드 - 레드는 연속할 수 없다.
각 노드로부터 ~ 리프까지 가는 경로들은 모두 같은 수의 black을 만난다..
red - black - tree의 삭제
삭제할 노드가 빨간색이면 문제가 없다. bst처럼 그냥 지우면된다.