이진 검색 트리는 이진 나무 정렬 된 방식으로 데이터를 유지할 수있는 몇 가지 규칙이 있습니다.
그것은 이진 트리 따라서 노드는 최대 2 개의 자식을 가질 수 있습니다.
차례
이진 검색 트리 노드의 구조
이진 트리가 이진 검색 트리가되는 규칙
- 노드의 왼쪽 하위 트리에있는 노드는 해당 노드보다 작아야합니다.
- 노드의 오른쪽 하위 트리에있는 노드는 해당 노드보다 커야합니다.
- 위의 두 조건은 트리의 모든 노드에 대해 참이어야합니다.
예
Left subtree of 8 contains: 5, 3, 7 which are smaller than 8 Right subtree of 8 contains: 16, 18 which are greater than 8 Left subtree of 5 contains: 3 which is smaller than 5 Right subtree of 5 contains: 7 which is greater than 5 Left subtree of 16 does not contain any node. Right subtree of 16 contains: 18 which is greater than 16 3, 7, 18 are leaf nodes hence there will be no left and right subtree present.
항상 모든 노드의 BST 조건을 확인해야합니다.
예 :
이진 검색 트리가 아닙니다.
이진 검색 트리의 장점
- 검색은 O (log (h))에서 수행 할 수 있습니다. 여기서 h는 BST의 높이입니다. 데이터가 BST에서 정렬 된 방식으로 저장되는 속성을 사용하여 이진 검색을 적용 할 수 있기 때문입니다.
- 정렬 된 방식으로 데이터를 삽입하는 것도 O (log (h))에서 수행되는 반면 배열 및 연결된 목록과 같은 다른 데이터 구조는이 작업에 O (n) 시간이 걸립니다.
이진 검색 트리 생성
암호알고리즘
- 삽입 할 값으로 노드를 만듭니다.
- insertBST (노드, 값)
- root == NULL이면 생성 된 노드를 반환합니다.
- 루트-> 값 <키 :
- 생성 된 노드를 오른쪽 하위 트리에 삽입
- root-> right = insertBST (root-> right, value)
- 루트-> 값> 키 :
- 생성 된 노드를 왼쪽 하위 트리에 삽입
- 루트-> 왼쪽 = insertBST (루트-> 왼쪽, 값)
- 루트 반환
예를 들어 이해합시다.
정수 배열 고려 [4, 7, 2, 8, 5]
배열에서 각 요소를 순차적으로 가져와 BST를 만들어 보겠습니다.
1 단계 : 4 삽입
루트가 null이므로 새로 생성 된 노드를 루트로 만듭니다.
2 단계 : 7 삽입
루트 값은 4이므로 7은 루트의 오른쪽에 있어야합니다.
3 단계 : 2 삽입
루트 값은 4이므로 루트의 왼쪽에 2를 배치해야합니다.
4 단계 : 8 삽입
루트 값은 4이므로 루트 오른쪽에 8을 배치해야합니다.
이제 7로 확인하겠습니다. 7 <8이므로 8은 7의 오른쪽에 있어야합니다.
5 단계 : 5 삽입
루트 값은 4이므로 루트 오른쪽에 5을 배치해야합니다.
이제 7> 7로 확인하므로 5는 5의 왼쪽에 있어야합니다.
이진 검색 트리 구현
C ++ 프로그램
#include<bits/stdc++.h>
using namespace std;
struct node
{
int value;
struct node* left;
struct node* right;
node(int value){ // constructor
this->value = value;
this->left = NULL;
this->right = NULL;
}
};
struct node* insertBST(node* root, int value)
{
if (root == NULL)
return new node(value); // return newly created node
if (value < root->value) // value should be inserted in the left subtree
root->left = insertBST(root->left, value);
else if (value > root->value) // value should be inserted in the right subtree
root->right = insertBST(root->right, value);
return root;
}
void inorder(node* root){
if(root == NULL)
return;
inorder(root->left);
cout<<root->value<<"-> ";
inorder(root->right);
}
int main(){
node *root = NULL;
root = insertBST(root, 10); //make the first created node as root
insertBST(root, 5);
insertBST(root, 4);
insertBST(root, 16);
insertBST(root, 2);
insertBST(root, 12);
insertBST(root, 17);
inorder(root);
}
JAVA 프로그램
class Node {
int value;
Node left, right;
public Node(int v) { //constructor
value = v;
left = null;
right = null;
}
};
class Main {
public static Node insertBST(Node root, int value) {
if (root == null) {
return new Node(value); // return newly created node
}
if (value < root.value) // value should be inserted in the left subtree
root.left = insertBST(root.left, value);
else if (value > root.value) // value should be inserted in the right subtree
root.right = insertBST(root.right, value);
return root;
}
public static void inorder(Node root) {
if (root != null) {
inorder(root.left);
System.out.print(root.value+"-> ");
inorder(root.right);
}
}
public static void main(String[] args) {
Node root = null;
root = insertBST(root, 10); //make the first created node as root
insertBST(root, 5);
insertBST(root, 4);
insertBST(root, 16);
insertBST(root, 2);
insertBST(root, 12);
insertBST(root, 17);
inorder(root);
}
}
2-> 4-> 5-> 10-> 12-> 16-> 17->
생성 된 트리의 구조
