데이터 구조의 이진 트리(예)
사라 첸
이진 트리 란 무엇입니까?
바이너리라는 단어는 XNUMX를 의미합니다. 트리 데이터 구조에서 "이진 트리"는 각 노드가 최대 XNUMX개의 자식 노드(왼쪽 및 오른쪽 노드)를 가질 수 있는 트리를 의미합니다. 간단한 이진 트리입니다.
하지만 가장 자주 사용되고 여러 사용 사례가 있는 또 다른 이진 트리가 있습니다. 이진 검색 트리(BST)라고 합니다. 이 트리는 검색 알고리즘을 훨씬 더 빠르게 만들 수 있으며, 정확히 log(n) 시간 복잡도를 갖습니다. 데이터 구조에서 n은 이진 트리의 노드 수를 의미합니다.
이진 트리와 이진 검색 트리의 차이점은 무엇입니까?
BST와 일반 이진 트리의 차이점은 BST 왼쪽 노드는 루트 노드보다 작은 값을 갖고 오른쪽 노드는 루트 노드보다 큰 값을 갖는다는 것입니다. 따라서 왼쪽 하위 트리에는 항상 루트보다 작은 값이 포함되고, 오른쪽 하위 트리에는 항상 루트보다 큰 값이 포함됩니다.
이진 검색 트리의 예
이진 탐색 트리의 개념을 보여주는 다음 예를 살펴보겠습니다.
여기에서는 모든 노드가 지정된 규칙을 따를 수 있습니다. 이진 검색 트리의 최대 노드 수에 대한 공식이 있습니다. 위의 트리를 관찰하면 각 노드에는 모든 리프 노드를 제외하고 두 개의 하위 노드가 있음을 알 수 있습니다. 그리고 주어진 이진 트리의 높이(h)는 4입니다. 공식은 다음과 같습니다. 2h - 1. 그래서 15를 줍니다.
위의 이미지는 완전한 이진 트리 또는 균형 이진 트리가 아니며, 완전 이진 트리 또는 균형 이진 트리라고 합니다. 그림 3과 같이 Binary Tree의 높이를 최적화하고 BST에 대한 검색을 더 빠르게 수행하는 AVL(다른 유형의 Binary Tree)이라는 또 다른 데이터 구조가 있습니다.
위에 주어진 이진 트리의 인오더 순회를 계산해 보세요. 감소하지 않는 정렬된 배열이 나오고, 순회 알고리즘은 이진 트리와 동일하다는 것을 알게 될 것입니다.
이진 트리 유형
다음은 이진 트리의 몇 가지 중요한 유형입니다.
- 완전 이진 트리: 각 노드는 이 이진 트리에서 0개 또는 2개의 하위 노드를 가질 수 있습니다. 이 유형의 이진 트리에서는 하나의 하위 노드만 허용되지 않습니다. 따라서 리프 노드를 제외한 모든 노드에는 2개의 자식이 있습니다.
- 완전 이진 트리: 각 노드는 0개 또는 2개의 노드를 가질 수 있습니다. 완전 이진 트리처럼 보이지만 모든 리프 요소는 왼쪽 하위 트리에 기울어져 있는 반면, 완전 이진 트리에서는 노드가 오른쪽 또는 왼쪽 하위 트리에 있을 수 있습니다.
- 완벽한 이진 트리: 모든 노드에는 0개 또는 2개의 노드가 있어야 하며, 모든 리프 노드는 동일한 레벨이나 높이에 있어야 합니다. 위의 전체 이진 트리 구조 예는 노드 6과 노드 1,2,3이 동일한 높이에 있지 않기 때문에 완벽한 이진 트리가 아닙니다. 그러나 완전 이진 트리의 예는 완전 이진 트리입니다.
- 퇴화된 이진 트리: 모든 노드는 단 하나의 자식만 가질 수 있습니다. 검색, 삽입, 삭제와 같은 모든 작업은 O(N) 시간이 걸립니다.
- 균형 잡힌 이진 트리: 여기 이 이진 트리에서는 왼쪽과 오른쪽 하위 트리의 높이 차이가 최대 1입니다. 따라서 노드를 추가하거나 삭제하는 동안 트리 높이의 균형을 다시 맞춰야 합니다. 이러한 유형의 자체 균형 이진 트리를 AVL 트리.
BST에는 세 가지 기본 작업이 있습니다. 아래에서 자세히 설명합니다.
C 및 C에서 이진 트리 구현 C++
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int value;
struct Node *left, *right;
}
struct Node *getEmptynode(int val)
{
struct Node *tempNode = (struct Node *)malloc(sizeof(struct Node));
tempNode->value = val;
tempNode->left = NULL;
tempNode->right = NULL;
return tempNode;
}
struct Node *successor(struct Node *node)
{
struct Node *present = node;
// going to the left most node
while (present != NULL && present->left != NULL)
{
present = present->left;
}
return present;
}
struct Node *insert(struct Node *node, int value)
{
if (node == NULL)
{
return getEmptynode(value);
}
if (value < node->value)
{
node->left = insert(node->left, value);
}
else
{
node->right = insert(node->right, value);
}
return node;
}
int searchInBST(struct Node *node, int value)
{
struct Node *current = node;
while (current->value != value)
{
if (current->value > value)
{
current = current->left;
}
else
{
current = current->right;
}
if (current == NULL)
{
return 0;
}
}
return 1;
}
void inorder(struct Node *root)
{
if (root != NULL)
{
inorder(root->left);
cout << root->value << " ";
inorder(root->right);
}
}
struct Node *deleteNode(struct Node *node, int value)
{
if (node == NULL)
{
return node;
}
if (value < node->value)
{
node->left = deleteNode(node->left, value);
}
else if (value > node->value)
{
node->right = deleteNode(node->right, value);
}
else
{
if (node->left == NULL)
{
struct Node *temp = node->right;
free(node);
return temp;
}
else if (node->right == NULL)
{
struct Node *temp = node->left;
free(node);
return temp;
}
struct Node *temp = successor(node->right);
node->value = temp->value;
node->right = deleteNode(node->right, temp->value);
}
return node;
}
int main()
{
struct Node *root = NULL;
root = insert(root, 8);
root = insert(root, 4);
root = insert(root, 12);
root = insert(root, 2);
root = insert(root, 6);
root = insert(root, 10);
root = insert(root, 14);
root = insert(root, 1);
root = insert(root, 3);
root = insert(root, 5);
root = insert(root, 7);
root = insert(root, 9);
root = insert(root, 11);
root = insert(root, 13);
root = insert(root, 15);
cout << "InOrder Traversal after inserting all nodes: " << endl;
inorder(root);
root = insert(root, -10);
cout << "\nInOrder Traversal after inserting -10 : " << endl;
inorder(root);
cout << "\nSearching -5 in the BST: " << searchInBST(root, -5) << endl;
cout << "Searching -10 in the BST: " << searchInBST(root, -10) << endl;
root = deleteNode(root,8);
cout<<"After deleting node 8, inorder traversal: "<<endl;
inorder(root);
root = deleteNode(root,-10);
cout<<"\nAfter deleting node -10, inorder traversal: "<<endl;
inorder(root);
}
출력:
InOrder Traversal after inserting all nodes: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 InOrder Traversal after inserting -10 : 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Searching -5 in the BST: 0 Searching -10 in the BST: 1 After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15
이진 트리 구현 Python
class Node:
def __init__(self,value):
self.left = None
self.right = None
self.value = value
def insert(root,value):
if root == None:
return Node(value)
if value< root.value:
root.left = insert(root.left,value)
else:
root.right = insert(root.right,value)
return root
def searchInBST(root,value):
current = root
while current.value != value:
if current.value > value:
current = current.left
else:
current = current.right
if current == None:
return "Not found"
return "Found"
def inorder(root):
if root != None:
inorder(root.left)
print(root.value,end=" ")
inorder(root.right)
def successor(root):
present = root
while present != None and present.left != None:
present = present.left
return present
def deleteNode(root,value):
if root == None:
return root
if value < root.value:
root.left = deleteNode(root.left, value)
elif value>root.value:
root.right = deleteNode(root.right, value)
else:
if root.left == None:
temp = root.right
root = None
return temp
elif root.right == None:
temp = root.left
root = None
return temp
temp = successor(root.right)
root.value = temp.value
root.right = deleteNode(root.right, temp.value)
return root
root = Node(8)
root = insert(root, 4)
root = insert(root, 12)
root = insert(root, 2)
root = insert(root, 6)
root = insert(root, 10)
root = insert(root, 14)
root = insert(root, 1)
root = insert(root, 3)
root = insert(root, 5)
root = insert(root, 7)
root = insert(root, 9)
root = insert(root, 11)
root = insert(root, 13)
root = insert(root, 15)
print("InOrder Traversal after inserting all nodes: ")
inorder(root)
root = insert(root, -10)
print("\nInOrder Traversal after inserting -10 : ")
inorder(root)
print("\nSearching -5 in the BST: ",searchInBST(root, -5))
print("Searching -5 in the BST: ",searchInBST(root, -10))
root = deleteNode(root,8)
print("After deleting node 8, inorder traversal:")
inorder(root)
root = deleteNode(root,-10)
print("\nAfter deleting node -10, inorder traversal:")
inorder(root)
출력:
InOrder Traversal after inserting all nodes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 InOrder Traversal after inserting -10 : -10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Searching -5 in the BST: Not found Searching -5 in the BST: Found After deleting node 8, inorder traversal: -10 1 2 3 4 5 6 7 9 10 11 12 13 14 15 After deleting node -10, inorder traversal: 1 2 3 4 5 6 7 9 10 11 12 13 14 15
이진 트리의 응용
다음은 이진 트리의 몇 가지 일반적인 응용 프로그램입니다.
- 노드 데이터를 정렬된 순서로 구성
- 프로그래밍 언어 라이브러리의 맵 및 세트 노드 개체에 사용됩니다.
- 데이터 구조에서 요소 검색
» 다음에 대한 다음 튜토리얼을 알아보세요. 조합 알고리즘
