Проверьте, существует ли значение в отсортированном полном двоичном дереве

Опубликовано: 12 Января, 2022

Учитывая упорядоченное по уровням полное двоичное дерево, задача состоит в том, чтобы проверить, существует ли в нем ключ или нет. Полное двоичное дерево имеет все уровни, за исключением, возможно, последнего, полностью заполненного, со всеми узлами как можно дальше слева.

Примеры:

 7
          / 
         10 15
       /  / 
      17 20 30 35
     /  /     
    40 41 50      
Ввод: Узел = 3
Выход: Нет

Ввод: Узел = 7
Выход: Да

Ввод: Узел = 30
Выход: Да
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход Простым решением O (n) было бы полностью пройти по дереву и проверить значение ключа. Однако мы можем использовать информацию о том, что дерево отсортировано и работать лучше с точки зрения временной сложности.

  • Узнайте уровень, на котором может существовать ключ. Начните с корневого узла и продолжайте движение влево, пока не встретите значение, превышающее значение ключа. Уровень до этого будет содержать ключ, если он вообще существует в дереве. Допустим, это уровень l .
  • Теперь выполните двоичный поиск в узлах l . В отличие от обычного бинарного поиска, к узлам этого уровня нельзя получить прямой доступ. Однако путь от корня к каждому узлу на этом уровне может быть закодирован с использованием двоичной логики. Например, рассмотрим 3-й уровень в дереве примеров. Он может содержать до 2 3 = 8 узлов. В эти узлы можно попасть из корневого узла, идя влево, влево, влево; или идя налево, налево, направо; и так далее. Если слева обозначено 0, а справа - 1, то возможные способы достижения узлов на этом уровне могут быть закодированы как arr = [000, 001, 010, 011, 100, 101, 110, 111].
  • Однако этот массив не нужно создавать, можно применить бинарный поиск, рекурсивно выбрав средний индекс и просто сгенерировав l- битный серый код этого индекса (см. Эту статью).
  • В случае неполных путей просто проверьте левую часть массива. Например, закодированный путь 011 не соответствует никакому значению в дереве выборки. Поскольку дерево завершено, оно гарантирует, что справа больше не будет элементов.
  • Если ключ найден, верните true, иначе верните false.

Below is the implementation of the above approach: 

C++

// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
 
/* Class containing left and right
child of current node and key value*/
class Node
{
    public :
    int data;
    Node *left, *right;
 
    Node(int item)
    {
        data = item;
        left = right = NULL;
    }
};
 
/* Function to locate which level to check
for the existence of key. */
int findLevel(Node *root, int data)
{
 
    // If the key is less than the root,
    // it will certainly not exist in the tree
    // because tree is level-order sorted
    if (data < root->data)
        return -1;
 
    // If the key is equal to the root then
    // simply return 0 (zero"th level)
    if (data == root->data)
        return 0;
 
    int cur_level = 0;
 
    while (true)
    {
        cur_level++;
        root = root->left;
 
        // If the key is found in any leftmost element
        // then simply return true
        // No need for any extra searching
        if (root->data == data)
            return -2;
 
        // If key lies between the root data and
        // the left child"s data OR if key is greater
        // than root data and there is no level
        // underneath it, return the current level
        if (root->data < data
            && (root->left == NULL
            || root->left->data > data))
        {
            break;
        }
    }
 
    return cur_level;
}
 
/* Function to traverse a binary
encoded path and return the value
encountered after traversal. */
int traversePath(Node *root,vector<int> path)
{
    for (int i = 0; i < path.size(); i++)
    {
        int direction = path[i];
 
        // Go left
        if (direction == 0)
        {
 
            // Incomplete path
            if (root->left == NULL)
                return -1;
            root = root->left;
        }
 
        // Go right
        else
        {
 
            // Incomplete path
            if (root->right == NULL)
                return -1;
            root = root->right;
        }
    }
 
    // Return the data at the node
    return root->data;
}
 
/* Function to generate gray code of
corresponding binary number of integer i */
vector<int> generateGray(int n, int x)
{
 
    // Create new arraylist to store
    // the gray code
    vector<int> gray ;
 
    int i = 0;
    while (x > 0)
    {
        gray.push_back(x % 2);
        x = x / 2;
        i++;
    }
 
    // Reverse the encoding till here
    reverse(gray.begin(),gray.end());
 
    // Leftmost digits are filled with 0
    for (int j = 0; j < n - i; j++)
        gray.insert(gray.begin(), 0);
 
    return gray;
}
 
/* Function to search the key in a
particular level of the tree. */
bool binarySearch(Node *root, int start,
                    int end, int data,
                    int level)
{
    if (end >= start)
    {
 
        // Find the middle index
        int mid = (start + end) / 2;
 
        // Encode path from root to this index
        // in the form of 0s and 1s where
        // 0 means LEFT and 1 means RIGHT
        vector<int> encoding = generateGray(level, mid);
 
        // Traverse the path in the tree
        // and check if the key is found
        int element_found = traversePath(root, encoding);
 
        // If path is incomplete
        if (element_found == -1)
 
            // Check the left part of the level
            return binarySearch(root, start,
                                mid - 1, data, level);
 
        if (element_found == data)
            return true;
 
        // Check the right part of the level
        if (element_found < data)
            return binarySearch(root, mid + 1,
                                end, data, level);
 
        // Check the left part of the level
        else
            return binarySearch(root, start,
                                mid - 1, data, level);
    }
 
    // Key not found in that level
    return false;
}
 
// Function that returns true if the
// key is found in the tree
bool findKey(Node *root, int data)
{
    // Find the level where the key may lie
    int level = findLevel(root, data);
 
    // If level is -1 then return false
    if (level == -1)
        return false;
 
    // If level is -2 i.e. key was found in any
    // leftmost element then simply return true
    if (level == -2)
        return true;
 
    // Apply binary search on the elements
    // of that level
    return binarySearch(root, 0, (int)pow(2, level) -
                        1, data, level);
}
 
// Driver code
int main()
{
    /* Consider the following level-order sorted tree
     
                    5
                /
                8     10
                / /
            13 23 25 30
            / /
            32 40 50
    */
 
    Node* root = new Node(5);
    root->left = new Node(8);
    root->right = new Node(10);
    root->left->left = new Node(13);
    root->left->right = new Node(23);
    root->right->left = new Node(25);
    root->right->right = new Node(30);
    root->left->left->left = new Node(32);
    root->left->left->right = new Node(40);
    root->left->right->left = new Node(50);
 
    // Keys to be searched
    int arr[] = { 5, 8, 9 };
    int n = sizeof(arr)/sizeof(int);
 
    for (int i = 0; i < n; i++)
    {
        if (findKey(root, arr[i]))
            cout << ("Yes") << endl;
        else
            cout << ("No") << endl;
    }
}
 
// This code is contributed by Arnab Kundu

Java

// Java implementation of the approach
import java.util.*;
import java.io.*;
 
/* Class containing left and right
child of current node and key value*/
class Node {
    int data;
    Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
class GFG {
 
    /* Function to locate which level to check
    for the existence of key. */
    public static int findLevel(Node root, int data)
    {
 
        // If the key is less than the root,
        // it will certainly not exist in the tree
        // because tree is level-order sorted
        if (data < root.data)
            return -1;
 
        // If the key is equal to the root then
        // simply return 0 (zero"th level)
        if (data == root.data)
            return 0;
 
        int cur_level = 0;
 
        while (true) {
            cur_level++;
            root = root.left;
 
            // If the key is found in any leftmost element
            // then simply return true
            // No need for any extra searching
            if (root.data == data)
                return -2;
 
            // If key lies between the root data and
            // the left child"s data OR if key is greater
            // than root data and there is no level
            // underneath it, return the current level
            if (root.data < data
                && (root.left == null
                    || root.left.data > data)) {
                break;
            }
        }
 
        return cur_level;
    }
 
    /* Function to traverse a binary
    encoded path and return the value
    encountered after traversal. */
    public static int traversePath(Node root,
                                   ArrayList<Integer> path)
    {
        for (int i = 0; i < path.size(); i++) {
            int direction = path.get(i);
 
            // Go left
            if (direction == 0) {
 
                // Incomplete path
                if (root.left == null)
                    return -1;
                root = root.left;
            }
 
            // Go right
            else {
 
                // Incomplete path
                if (root.right == null)
                    return -1;
                root = root.right;
            }
        }
 
        // Return the data at the node
        return root.data;
    }
 
    /* Function to generate gray code of
    corresponding binary number of integer i */
    static ArrayList<Integer> generateGray(int n, int x)
    {
 
        // Create new arraylist to store
        // the gray code
        ArrayList<Integer> gray = new ArrayList<Integer>();
 
        int i = 0;
        while (x > 0) {
            gray.add(x % 2);
            x = x / 2;
            i++;
        }
 
        // Reverse the encoding till here
        Collections.reverse(gray);
 
        // Leftmost digits are filled with 0
        for (int j = 0; j < n - i; j++)
            gray.add(0, 0);
 
        return gray;
    }
 
    /* Function to search the key in a
    particular level of the tree. */
    public static boolean binarySearch(Node root,
                                       int start,
                                       int end,
                                       int data,
                                       int level)
    {
        if (end >= start) {
 
            // Find the middle index
            int mid = (start + end) / 2;
 
            // Encode path from r
Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023
Введение в связанный список — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в массивы — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Как подготовиться к ICFP или Международной конференции по функциональному программированию?
12 Декабря, 2022