Рубрики

Пол и Потолок из BST

Бинарное дерево поиска

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

Ceil Value Node : Узел с наименьшими данными, большими или равными значению ключа.

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

А) Корневые данные равны ключевым. Мы сделали, корневые данные имеют значение ceil.

B) Корневые данные <значение ключа, конечно, значение ceil не может быть в левом поддереве. Перейдите к поиску на правом поддереве как уменьшенном экземпляре проблемы.

C) Корневые данные> значение ключа, значение ceil может быть в левом поддереве. Мы можем найти узел с данными большего размера, чем значение ключа в левом поддереве, если не сам корень будет узлом ceil.

Вот код для значения ceil.

C ++

// Программа для поиска ceil заданного значения в BST
#include <bits/stdc++.h>

using namespace std;

  
/ * Узел двоичного дерева имеет ключ, левый и правый дочерние элементы * /

class node {

public:

    int key;

    node* left;

    node* right;

};

  
/ * Вспомогательная функция, которая выделяет новый узел с данным ключом и
NULL левый и правый указатели. * /

node* newNode(int key)

{

    node* Node = new node();

    Node->key = key;

    Node->left = NULL;

    Node->right = NULL;

    return (Node);

}

  
// Функция, чтобы найти ceil данного входа в BST. Если вход больше
// чем ключ макс в BST, вернуть -1

int Ceil(node* root, int input)

{

    // Базовый вариант

    if (root == NULL)

        return -1;

  

    // Мы нашли равный ключ

    if (root->key == input)

        return root->key;

  

    // Если ключ root меньше, ceil должен находиться в правом поддереве

    if (root->key < input)

        return Ceil(root->right, input);

  

    // Иначе, либо левое поддерево, либо корень имеют значение ceil

    int ceil = Ceil(root->left, input);

    return (ceil >= input) ? ceil : root->key;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    node* root = newNode(8);

  

    root->left = newNode(4);

    root->right = newNode(12);

  

    root->left->left = newNode(2);

    root->left->right = newNode(6);

  

    root->right->left = newNode(10);

    root->right->right = newNode(14);

  

    for (int i = 0; i < 16; i++)

        cout << i << " " << Ceil(root, i) << endl;

  

    return 0;

}

  
// Этот код предоставлен rathbhupendra

С

// Программа для поиска ceil заданного значения в BST
#include <stdio.h>
#include <stdlib.h>

  
/ * Узел двоичного дерева имеет ключ, левый и правый дочерние элементы * /

struct node {

    int key;

    struct node* left;

    struct node* right;

};

  
/ * Вспомогательная функция, которая выделяет новый узел с данным ключом и
NULL левый и правый указатели. * /

struct node* newNode(int key)

{

    struct node* node = (struct node*)malloc(sizeof(struct node));

    node->key = key;

    node->left = NULL;

    node->right = NULL;

    return (node);

}

  
// Функция, чтобы найти ceil данного входа в BST. Если вход больше
// чем ключ макс в BST, вернуть -1

int Ceil(struct node* root, int input)

{

    // Базовый вариант

    if (root == NULL)

        return -1;

  

    // Мы нашли равный ключ

    if (root->key == input)

        return root->key;

  

    // Если ключ root меньше, ceil должен находиться в правом поддереве

    if (root->key < input)

        return Ceil(root->right, input);

  

    // Иначе, либо левое поддерево, либо корень имеют значение ceil

    int ceil = Ceil(root->left, input);

    return (ceil >= input) ? ceil : root->key;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    struct node* root = newNode(8);

  

    root->left = newNode(4);

    root->right = newNode(12);

  

    root->left->left = newNode(2);

    root->left->right = newNode(6);

  

    root->right->left = newNode(10);

    root->right->right = newNode(14);

  

    for (int i = 0; i < 16; i++)

        printf("%d %d\n", i, Ceil(root, i));

  

    return 0;

}

Джава

// Java-программа для поиска ceil заданного значения в BST

  

class Node { 

  

    int data; 

    Node left, right; 

  

    Node(int d) 

    { 

        data = d; 

        left = right = null; 

    } 

} 

  

class BinaryTree { 

  

    Node root; 

  

    // Функция, чтобы найти ceil данного входа в BST.

    // Если ввод больше, чем максимальная клавиша в BST,

    // возвращаем -1

    int Ceil(Node node, int input) 

    { 

  

        // Базовый вариант

        if (node == null) { 

            return -1; 

        } 

  

        // Мы нашли равный ключ

        if (node.data == input) { 

            return node.data; 

        } 

  

        // Если ключ root меньше,

        // ceil должен быть в правильном поддереве

        if (node.data < input) { 

            return Ceil(node.right, input); 

        } 

  

        // Иначе, либо левое поддерево, либо корень

        // имеет значение ceil

        int ceil = Ceil(node.left, input); 

          

        return (ceil >= input) ? ceil : node.data; 

    } 

  

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

    public static void main(String[] args) 

    { 

        BinaryTree tree = new BinaryTree(); 

        tree.root = new Node(8); 

        tree.root.left = new Node(4); 

        tree.root.right = new Node(12); 

        tree.root.left.left = new Node(2); 

        tree.root.left.right = new Node(6); 

        tree.root.right.left = new Node(10); 

        tree.root.right.right = new Node(14); 

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

              

            System.out.println(i + " " + 

                        tree.Ceil(tree.root, i)); 

        } 

    } 

} 

  
// Этот код предоставлен Mayank Jaiswal

питон

# Python программа для поиска ceil заданного значения в BST

  
# Узел двоичного дерева

class Node:

      

    # Конструктор для создания нового узла

    def __init__(self, data):

        self.key = data

        self.left = None

        self.right = None

  
# Функция, чтобы найти ceil данного входа в BST. Если вход
# больше максимального ключа в BST, возврат -1

def ceil(root, inp):

      

    # Базовый вариант

    if root == None:

        return -1

      

    # Мы нашли равный ключ

    if root.key == inp :

        return root.key 

      

    # Если ключ root меньше, ceil должен находиться в правом поддереве

    if root.key < inp:

        return ceil(root.right, inp)

      

    # Иначе, либо левый subtre, либо root имеют значение ceil

    val = ceil(root.left, inp)

    return val if val >= inp else root.key 

  
# Программа драйвера для проверки вышеуказанной функции

root = Node(8)

  

root.left = Node(4)

root.right = Node(12)

  

root.left.left = Node(2)

root.left.right = Node(6)

  

root.right.left = Node(10)

root.right.right = Node(14)

  

for i in range(16):

    print "% d % d" %(i, ceil(root, i))

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

using System;

  
// C # программа для поиска ceil заданного значения в BST

  

public class Node {

  

    public int data;

    public Node left, right;

  

    public Node(int d)

    {

        data = d;

        left = right = null;

    }

}

  

public class BinaryTree {

  

    public static Node root;

  

    // Функция, чтобы найти ceil данного входа в BST. Если вход больше

    // чем ключ макс в BST, вернуть -1

    public virtual int Ceil(Node node, int input)

    {

  

        // Базовый вариант

        if (node == null) {

            return -1;

        }

  

        // Мы нашли равный ключ

        if (node.data == input) {

            return node.data;

        }

  

        // Если ключ root меньше, ceil должен находиться в правом поддереве

        if (node.data < input) {

            return Ceil(node.right, input);

        }

  

        // Иначе, либо левое поддерево, либо корень имеют значение ceil

        int ceil = Ceil(node.left, input);

        return (ceil >= input) ? ceil : node.data;

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

        BinaryTree.root = new Node(8);

        BinaryTree.root.left = new Node(4);

        BinaryTree.root.right = new Node(12);

        BinaryTree.root.left.left = new Node(2);

        BinaryTree.root.left.right = new Node(6);

        BinaryTree.root.right.left = new Node(10);

        BinaryTree.root.right.right = new Node(14);

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

            Console.WriteLine(i + " " + tree.Ceil(root, i));

        }

    }

}

  
// Этот код предоставлен Shrikant13


Выход:

0  2
1  2
2  2
3  4
4  4
5  6
6  6
7  8
8  8
9  10
10  10
11  12
12  12
13  14
14  14
15  -1

Упражнение:

1. Измените приведенный выше код, чтобы найти минимальное значение ключа ввода в бинарном дереве поиска.

2. Напишите аккуратный алгоритм, чтобы найти значения floor и ceil в отсортированном массиве. Убедитесь, что обработаны все возможные граничные условия.

— Венки . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Пол и Потолок из BST

0.00 (0%) 0 votes