주어진 BST , 작업은 이 노드에서 노드를 검색하는 것입니다 BST .
BST에서 값을 검색하려면 이를 정렬된 배열로 간주하세요. 이제 다음을 사용하여 BST에서 검색 작업을 쉽게 수행할 수 있습니다. 이진 검색 알고리즘 .
f영화
주어진 이진 검색 트리에서 키를 검색하는 알고리즘:
숫자를 검색하고 싶다고 가정해 보겠습니다. 엑스, 우리는 루트에서 시작합니다. 그 다음에:
- 검색할 값과 루트 값을 비교합니다.
- 만약 같으면 더 작으면 검색이 완료됩니다. 이진 검색 트리에서는 왼쪽 하위 트리의 모든 요소가 더 작고 오른쪽 하위 트리의 모든 요소가 더 크기 때문에 왼쪽 하위 트리로 이동해야 한다는 것을 알고 있습니다.
- 더 이상 순회가 불가능할 때까지 위 단계를 반복합니다.
- 반복에서 키가 발견되면 True를 반환합니다. 그렇지 않으면 거짓입니다.
BST 검색 예시:
더 잘 이해하려면 아래 그림을 참조하세요.
권장 사례BST에서 노드 검색해 보세요!
BST에서 검색을 구현하는 프로그램:
C++
// C++ function to search a given key in a given BST> #include> using> namespace> std;> struct> node {> >int> key;> >struct> node *left, *right;> };> // A utility function to create a new BST node> struct> node* newNode(>int> item)> {> >struct> node* temp> >=>new> struct> node;> >temp->키 = 항목;> >temp->왼쪽 = 임시->오른쪽 = NULL;> >return> temp;> }> // A utility function to insert> // a new node with given key in BST> struct> node* insert(>struct> node* node,>int> key)> {> >// If the tree is empty, return a new node> >if> (node == NULL)> >return> newNode(key);> >// Otherwise, recur down the tree> >if> (key key)> >node->왼쪽 = 삽입(노드->왼쪽, 키);> >else> if> (key>노드->키)> >node->right = insert(노드->오른쪽, 키);> >// Return the (unchanged) node pointer> >return> node;> }> // Utility function to search a key in a BST> struct> node* search(>struct> node* root,>int> key)> > >// Base Cases: root is null or key is present at root> >if> (root == NULL> // Driver Code> int> main()> {> >struct> node* root = NULL;> >root = insert(root, 50);> >insert(root, 30);> >insert(root, 20);> >insert(root, 40);> >insert(root, 70);> >insert(root, 60);> >insert(root, 80);> >// Key to be found> >int> key = 6;> >// Searching in a BST> >if> (search(root, key) == NULL)> >cout << key <<>' not found'> << endl;> >else> >cout << key <<>' found'> << endl;> >key = 60;> >// Searching in a BST> >if> (search(root, key) == NULL)> >cout << key <<>' not found'> << endl;> >else> >cout << key <<>' found'> << endl;> >return> 0;> }> |
>
>
씨
// C function to search a given key in a given BST> #include> #include> struct> node {> >int> key;> >struct> node *left, *right;> };> // A utility function to create a new BST node> struct> node* newNode(>int> item)> {> >struct> node* temp> >= (>struct> node*)>malloc>(>sizeof>(>struct> node));> >temp->키 = 항목;> >temp->왼쪽 = 임시->오른쪽 = NULL;> >return> temp;> }> // A utility function to insert> // a new node with given key in BST> struct> node* insert(>struct> node* node,>int> key)> {> >// If the tree is empty, return a new node> >if> (node == NULL)> >return> newNode(key);> >// Otherwise, recur down the tree> >if> (key key)> >node->왼쪽 = 삽입(노드->왼쪽, 키);> >else> if> (key>노드->키)> >node->right = insert(노드->오른쪽, 키);> >// Return the (unchanged) node pointer> >return> node;> }> // Utility function to search a key in a BST> struct> node* search(>struct> node* root,>int> key)> > // Driver Code> int> main()> {> >struct> node* root = NULL;> >root = insert(root, 50);> >insert(root, 30);> >insert(root, 20);> >insert(root, 40);> >insert(root, 70);> >insert(root, 60);> >insert(root, 80);> >// Key to be found> >int> key = 6;> >// Searching in a BST> >if> (search(root, key) == NULL)> >printf>(>'%d not found
'>, key);> >else> >printf>(>'%d found
'>, key);> >key = 60;> >// Searching in a BST> >if> (search(root, key) == NULL)> >printf>(>'%d not found
'>, key);> >else> >printf>(>'%d found
'>, key);> >return> 0;> }> |
>
>
자바
// Java program to search a given key in a given BST> class> Node {> >int> key;> >Node left, right;> >public> Node(>int> item) {> >key = item;> >left = right =>null>;> >}> }> class> BinarySearchTree {> >Node root;> >// Constructor> >BinarySearchTree() {> >root =>null>;> >}> >// A utility function to insert> >// a new node with given key in BST> >Node insert(Node node,>int> key) {> >// If the tree is empty, return a new node> >if> (node ==>null>) {> >node =>new> Node(key);> >return> node;> >}> >// Otherwise, recur down the tree> >if> (key node.left = insert(node.left, key); else if (key>node.key) node.right = insert(node.right, 키); // (변경되지 않은) 노드 포인터를 반환합니다. return node; } // BST 노드 검색에서 키를 검색하는 유틸리티 함수(Node root, int key) // 드라이버 코드 public static void main(String[] args) { BinarySearchTree tree = new BinarySearchTree(); // 노드 삽입 tree.root = tree.insert(tree.root, 50); tree.insert(tree.root, 30); tree.insert(tree.root, 20); tree.insert(tree.root, 40); tree.insert(tree.root, 70); tree.insert(tree.root, 60); tree.insert(tree.root, 80); // 찾을 키 int key = 6; // BST에서 검색 if (tree.search(tree.root, key) == null) System.out.println(key + ' 찾을 수 없음'); else System.out.println(key + '발견'); 키 = 60; // BST에서 검색 if (tree.search(tree.root, key) == null) System.out.println(key + ' 찾을 수 없음'); else System.out.println(key + '발견'); } }> |
>
base64 자바스크립트 디코드
>
파이썬3
# Python3 function to search a given key in a given BST> class> Node:> ># Constructor to create a new node> >def> __init__(>self>, key):> >self>.key>=> key> >self>.left>=> None> >self>.right>=> None> # A utility function to insert> # a new node with the given key in BST> def> insert(node, key):> ># If the tree is empty, return a new node> >if> node>is> None>:> >return> Node(key)> ># Otherwise, recur down the tree> >if> key node.left = insert(node.left, key) elif key>node.key: node.right = insert(node.right, key) # (변경되지 않은) 노드 포인터를 반환 return node # BST에서 키를 검색하는 유틸리티 함수 def search(root, key): # 기본 사례: root is null 또는 키는 루트에 존재합니다. if root is None or root.key == key: return root # 키는 루트의 키보다 큽니다. if root.key return search(root.right, key) # 키는 루트보다 작습니다. 의 키 return search(root.left, key) # 드라이버 코드 if __name__ == '__main__': root = None root = insert(root, 50) insert(root, 30) insert(root, 20) insert (root, 40) insert(root, 70) insert(root, 60) insert(root, 80) # 찾을 키 key = 6 # search(root, key)가 None인 경우 BST에서 검색: print(key, '찾을 수 없음') else: print(key, 'found') key = 60 # BST에서 검색 if search(root, key) is None: print(key, 'notfound') else: print(키, '발견')> |
>
>
씨#
// C# function to search a given key in a given BST> using> System;> public> class> Node {> >public> int> key;> >public> Node left, right;> }> public> class> BinaryTree {> >// A utility function to create a new BST node> >public> Node NewNode(>int> item)> >{> >Node temp =>new> Node();> >temp.key = item;> >temp.left = temp.right =>null>;> >return> temp;> >}> >// A utility function to insert> >// a new node with given key in BST> >public> Node Insert(Node node,>int> key)> >{> >// If the tree is empty, return a new node> >if> (node ==>null>)> >return> NewNode(key);> >// Otherwise, recur down the tree> >if> (key node.left = Insert(node.left, key); else if (key>node.key) node.right = Insert(node.right, 키); // (변경되지 않은) 노드 포인터를 반환합니다. return node; } // BST에서 키를 검색하는 유틸리티 함수 공개 노드 검색(Node root, int key) // 기본 사례: 루트가 null이거나 키가 루트에 존재합니다. if (root == null // 드라이버 코드 public static void Main () { 노드 루트 = null; BinaryTree bt = new BinaryTree(); 루트 = bt.Insert(root, 30); bt.Insert(root, 20); , 40); bt.Insert(root, 60); bt.Insert(root, 80); // 찾을 키 int key = 6; bt.Search(root, key) == null) Console.WriteLine(key + ' 찾을 수 없음'); else Console.WriteLine(key + ' 찾음') // BST에서 검색 중 if (bt.Search(root, key) == null) Console.WriteLine(key + ' 찾을 수 없음') else Console.WriteLine(key + ' 찾음') } }> |
>
>
자바스크립트
// Javascript function to search a given key in a given BST> class Node {> >constructor(key) {> >this>.key = key;> >this>.left =>null>;> >this>.right =>null>;> >}> }> // A utility function to insert> // a new node with given key in BST> function> insert(node, key) {> >// If the tree is empty, return a new node> >if> (node ===>null>) {> >return> new> Node(key);> >}> >// Otherwise, recur down the tree> >if> (key node.left = insert(node.left, key); } else if (key>node.key) { node.right = insert(node.right, 키); } // (변경되지 않은) 노드 포인터를 반환합니다. return node; } // BST 함수에서 키를 검색하는 유틸리티 함수 search(root, key) { // 기본 사례: 루트가 null이거나 키가 루트에 존재합니다. if (root === null || root.key === key ) { 루트를 반환합니다. } // 키가 루트의 키보다 큽니다. if (root.key return search(root.right, key); } // 키가 루트의 키보다 작습니다 return search(root.left, key); } // 드라이버 코드 let root = null; root = insert(root, 30); insert(root, 40); 60); insert(root, 80); // 찾을 키 let key = 6; // BST에서 검색 if (search(root, key) === null) { console.log(key + ' not found'); } else { console.log(key + 'found'); } key = 60; // BST에서 검색 if (search(root, key) === null) { console.log( key + ' 찾을 수 없음'); } else { console.log(key + ' 찾을 수 없음') }> |
>
>산출
6 not found 60 found>
시간 복잡도: O(h), 여기서 h는 BST의 높이입니다.
보조 공간: O(h), 여기서 h는 BST의 높이입니다. 이는 재귀 스택을 저장하는 데 필요한 최대 공간이 다음과 같기 때문입니다. 시간 .
관련된 링크들:
- 이진 검색 트리 삽입 작업
- 이진 검색 트리 삭제 작업