이진 검색 트리

난이도 쉽게
자주 묻는 질문 아마존 디보이 포카이트 인포시스 Microsoft
이진 검색 트리 이진 트리 이론 나무조회수 28

이진 검색 트리는 이진 나무 정렬 된 방식으로 데이터를 유지할 수있는 몇 가지 규칙이 있습니다.

그것은 이진 트리 따라서 노드는 최대 2 개의 자식을 가질 수 있습니다.

이진 검색 트리 노드의 구조

 

이진 검색 트리

이진 트리가 이진 검색 트리가되는 규칙

  1. 노드의 왼쪽 하위 트리에있는 노드는 해당 노드보다 작아야합니다.
  2. 노드의 오른쪽 하위 트리에있는 노드는 해당 노드보다 커야합니다.
  3. 위의 두 조건은 트리의 모든 노드에 대해 참이어야합니다.

이진 검색 트리

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 조건을 확인해야합니다.

예 :

이진 검색 트리가 아닙니다.

이진 검색 트리

이진 검색 트리의 장점

  1. 검색은 O (log (h))에서 수행 할 수 있습니다. 여기서 h는 BST의 높이입니다. 데이터가 BST에서 정렬 된 방식으로 저장되는 속성을 사용하여 이진 검색을 적용 할 수 있기 때문입니다.
  2. 정렬 된 방식으로 데이터를 삽입하는 것도 O (log (h))에서 수행되는 반면 배열 및 연결된 목록과 같은 다른 데이터 구조는이 작업에 O (n) 시간이 걸립니다.

이진 검색 트리 생성

암호알고리즘

  1. 삽입 할 값으로 노드를 만듭니다.
  2. insertBST (노드, 값)
    1. root == NULL이면 생성 된 노드를 반환합니다.
    2. 루트-> 값 <키 :
      • 생성 된 노드를 오른쪽 하위 트리에 삽입
      • root-> right = insertBST (root-> right, value)
    3.  루트-> 값> 키 :
      • 생성 된 노드를 왼쪽 하위 트리에 삽입
      • 루트-> 왼쪽 = insertBST (루트-> 왼쪽, 값)
  1. 루트 반환

예를 들어 이해합시다.

정수 배열 고려 [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-> 

생성 된 트리의 구조

참조

Translate »