Рубрики

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

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

Примеры:

             7
          /     \
         10      15
       /   \    /  \
      17   20  30  35
     / \   /     
    40 41 50      
Input: Node = 3
Output: No

Input: Node = 7
Output: Yes

Input: Node = 30
Output: Yes

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

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

Ниже приведена реализация вышеуказанного подхода:

// C ++ реализация подхода

import java.util.*;

import java.io.*;

  
/ * Класс, содержащий левый и правый
дочерний элемент текущего узла и значение ключа * /

class Node {

    int data;

    Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

class GFG {

  

    / * Функция для определения уровня проверки

    для существования ключа. * /

    public static int findLevel(Node root, int data)

    {

  

        // Если ключ меньше корня,

        // он точно не будет существовать в дереве

        // потому что дерево отсортировано по уровню

        if (data < root.data)

            return -1;

  

        // Если ключ равен корню, то

        // просто возвращаем 0 (нулевой уровень)

        if (data == root.data)

            return 0;

  

        int cur_level = 0;

  

        while (true) {

            cur_level++;

            root = root.left;

  

            // Если ключ найден в любом крайнем левом элементе

            // затем просто возвращаем true

            // Нет необходимости дополнительного поиска

            if (root.data == data)

                return -2;

  

            // Если ключ лежит между корневыми данными и

            // данные левого ребенка ИЛИ, если ключ больше

            // чем корневые данные и нет уровня

            // под ним, возвращаем текущий уровень

            if (root.data < data

                && (root.left == null

                    || root.left.data > data)) {

                break;

            }

        }

  

        return cur_level;

    }

  

    / * Функция для обхода двоичного файла

    закодированный путь и возвращаем значение

    встречаются после прохождения. * /

    public static int traversePath(Node root,

                                   ArrayList<Integer> path)

    {

        for (int i = 0; i < path.size(); i++) {

            int direction = path.get(i);

  

            // Налево

            if (direction == 0) {

  

                // Неполный путь

                if (root.left == null)

                    return -1;

                root = root.left;

            }

  

            // Иди направо

            else {

  

                // Неполный путь

                if (root.right == null)

                    return -1;

                root = root.right;

            }

        }

  

        // Возвращаем данные в узле

        return root.data;

    }

  

    / * Функция для генерации серого кода

    соответствующее двоичное число целого числа i * /

    static ArrayList<Integer> generateGray(int n, int x)

    {

  

        // Создать новый массив для хранения

        // серый код

        ArrayList<Integer> gray = new ArrayList<Integer>();

  

        int i = 0;

        while (x > 0) {

            gray.add(x % 2);

            x = x / 2;

            i++;

        }

  

        // Обратное кодирование до здесь

        Collections.reverse(gray);

  

        // крайние левые цифры заполняются 0

        for (int j = 0; j < n - i; j++)

            gray.add(0, 0);

  

        return gray;

    }

  

    / * Функция для поиска ключа в

    определенный уровень дерева. * /

    public static boolean binarySearch(Node root,

                                       int start,

                                       int end,

                                       int data,

                                       int level)

    {

        if (end >= start) {

  

            // Найти средний индекс

            int mid = (start + end) / 2;

  

            // Кодировать путь от корня до этого индекса

            // в форме 0 и 1, где

            // 0 означает ВЛЕВО, а 1 - ВПРАВО

            ArrayList<Integer> encoding = generateGray(level, mid);

  

            // Обход пути в дереве

            // и проверяем, найден ли ключ

            int element_found = traversePath(root, encoding);

  

            // Если путь не полный

            if (element_found == -1)

  

                // Проверяем левую часть уровня

                return binarySearch(root, start, mid - 1, data, level);

  

            if (element_found == data)

                return true;

  

            // Проверяем правую часть уровня

            if (element_found < data)

                return binarySearch(root, mid + 1, end, data, level);

  

            // Проверяем левую часть уровня

            else

                return binarySearch(root, start, mid - 1, data, level);

        }

  

        // Ключ не найден на этом уровне

        return false;

    }

  

    // Функция, которая возвращает true, если

    // ключ найден в дереве

    public static boolean findKey(Node root, int data)

    {

        // Находим уровень, на котором может лежать ключ

        int level = findLevel(root, data);

  

        // Если уровень равен -1, вернуть false

        if (level == -1)

            return false;

  

        // Если уровень -2, то есть ключ был найден в любом

        // самый левый элемент, затем просто возвращаем true

        if (level == -2)

            return true;

  

        // Применяем бинарный поиск по элементам

        // этого уровня

        return binarySearch(root, 0, (int)Math.pow(2, level) - 1, data, level);

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        / * Рассмотрим следующее отсортированное по уровню дерево

          

                          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);

  

        // Ключи для поиска

        int arr[] = { 5, 8, 9 };

        int n = arr.length;

  

        for (int i = 0; i < n; i++) {

            if (findKey(root, arr[i]))

                System.out.println("Yes");

            else

                System.out.println("No");

        }

    }

}

Выход:

Yes
Yes
No

Сложность времени : уровень можно найти за время O (logn). Время прохождения любого пути для выполнения бинарного поиска составляет O (logn). Кроме того, в худшем случае уровень может иметь не более n / 2 узлов.

Следовательно, временная сложность выполнения поиска становится O (logn) * O (log (n / 2)) = O (logn) ^ 2 .

Рекомендуемые посты:

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

0.00 (0%) 0 votes