Рубрики

Двоичное дерево поиска | Набор 1 (поиск и вставка)

Ниже приведено определение Бинарного Поискового Дерева (BST) согласно Википедии.

Двоичное дерево поиска — это структура данных двоичного дерева на основе узлов, которая имеет следующие свойства:

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

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

C / C ++

// C функция для поиска заданного ключа в заданном BST

struct node* search(struct node* root, int key)

{

    // Базовые случаи: root имеет значение null или ключ присутствует в root

    if (root == NULL || root->key == key)

       return root;

     

    // Ключ больше ключа root

    if (root->key < key)

       return search(root->right, key);

  

    // Ключ меньше ключа root

    return search(root->left, key);

}

Джава

// Полезная функция для поиска заданного ключа в BST

public Node search(Node root, int key)

{

    // Базовые случаи: root имеет значение null или ключ присутствует в root

    if (root==null || root.key==key)

        return root;

  

    // val больше ключа root

    if (root.key > key)

        return search(root.left, key);

  

    // val меньше ключа root

    return search(root.right, key);

}

питон

# Полезная функция для поиска заданного ключа в BST

def search(root,key):

      

    # Базовые случаи: root имеет значение null или ключ присутствует в root

    if root is None or root.val == key:

        return root

  

    # Ключ больше ключа root

    if root.val < key:

        return search(root.right,key)

    

    # Ключ меньше ключа root

    return search(root.left,key)

  
# Этот код предоставлен Bhavya Jain


Иллюстрация для поиска 6 в дереве ниже:
1. Начните с корня.
2. Сравните вставляемый элемент с корнем, если меньше, чем корень, затем рекурсивно для левого, иначе рекурсивно для правого.
3. Если элемент для поиска найден где-либо, верните true, иначе верните false.

Вставка ключа
Новый ключ всегда вставляется в лист. Мы начинаем искать ключ от корня, пока не дойдем до конечного узла. Как только конечный узел найден, новый узел добавляется как дочерний узел конечного узла.

         100                               100
        /   \        Insert 40            /    \
      20     500    --------->          20     500 
     /  \                              /  \  
    10   30                           10   30
                                              \   
                                              40

С

// C программа для демонстрации операции вставки в бинарное дерево поиска.
#include<stdio.h>
#include<stdlib.h>

   

struct node

{

    int key;

    struct node *left, *right;

};

   
// Вспомогательная функция для создания нового узла BST

struct node *newNode(int item)

{

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

    temp->key = item;

    temp->left = temp->right = NULL;

    return temp;

}

   
// Утилита для обхода порядка следования BST

void inorder(struct node *root)

{

    if (root != NULL)

    {

        inorder(root->left);

        printf("%d \n", root->key);

        inorder(root->right);

    }

}

   
/ * Утилита для вставки нового узла с заданным ключом в BST * /

struct node* insert(struct node* node, int key)

{

    / * Если дерево пустое, вернуть новый узел * /

    if (node == NULL) return newNode(key);

  

    / * В противном случае вернемся вниз по дереву * /

    if (key < node->key)

        node->left  = insert(node->left, key);

    else if (key > node->key)

        node->right = insert(node->right, key);   

  

    / * вернуть (неизмененный) указатель узла * /

    return node;

}

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

int main()

{

    / * Давайте создадим следующий BST

              50

           / /

          30 70

         / / / /

       20 40 60 80 *

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

   

    // распечатка обхода кодера BST

    inorder(root);

   

    return 0;

}

CPP

// C ++ программа для демонстрации вставки
// в BST рекурсивно.
#include <iostream>

using namespace std;

  

class BST

{

    int data;

    BST *left, *right;

  

    public:

      

    // Конструктор по умолчанию.

    BST();

      

    // Параметризованный конструктор.

    BST(int);

      

    // Вставить функцию.

    BST* Insert(BST *, int);

      

    // Прохождение обхода.

    void Inorder(BST *);

};

  
// Определение конструктора по умолчанию.
BST :: BST() : data(0), left(NULL), right(NULL){}

  
// Определение параметризованного конструктора.

BST :: BST(int value)

{

    data = value;

    left = right = NULL;

}

  
// Вставить определение функции.

BST* BST :: Insert(BST *root, int value)

{

    if(!root)

    {

        // Вставляем первый узел, если root равен NULL.

        return new BST(value);

    }

  

    // Вставить данные.

    if(value > root->data)

    {

        // Вставляем данные правого узла, если 'значение'

        // для вставки больше, чем данные корневого узла.

          

        // Обработка правых узлов.

        root->right = Insert(root->right, value);

    }

    else

    {

        // Вставляем данные левого узла, если 'значение'

        // для вставки больше, чем данные корневого узла.

          

        // Обработка левых узлов.

        root->left = Insert(root->left, value);

    }

      

    // Возвращаем корневой узел после вставки.

    return root;

}

  
// Функция обхода порядка.
// Это дает данные в отсортированном порядке.

void BST :: Inorder(BST *root)

{

    if(!root)

    {

        return;

    }

    Inorder(root->left);

    cout << root->data << endl;

    Inorder(root->right);

}

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

int main()

{

    BST b, *root = NULL;

    root = b.Insert(root, 50);

    b.Insert(root, 30);

    b.Insert(root, 20);

    b.Insert(root, 40);

    b.Insert(root, 70);

    b.Insert(root, 60);

    b.Insert(root, 80);

  

    b.Inorder(root);

    return 0;

}

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

Джава

// Java-программа для демонстрации операции вставки в двоичное дерево поиска

class BinarySearchTree {

  

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

    class Node {

        int key;

        Node left, right;

  

        public Node(int item) {

            key = item;

            left = right = null;

        }

    }

  

    // Корень BST

    Node root;

  

    // Конструктор

    BinarySearchTree() { 

        root = null

    }

  

    // Этот метод в основном вызывает insertRec ()

    void insert(int key) {

       root = insertRec(root, key);

    }

      

    / * Рекурсивная функция для вставки нового ключа в BST * /

    Node insertRec(Node root, int key) {

  

        / * Если дерево пустое, вернуть новый узел * /

        if (root == null) {

            root = new Node(key);

            return root;

        }

  

        / * В противном случае вернемся вниз по дереву * /

        if (key < root.key)

            root.left = insertRec(root.left, key);

        else if (key > root.key)

            root.right = insertRec(root.right, key);

  

        / * вернуть (неизмененный) указатель узла * /

        return root;

    }

  

    // Этот метод в основном вызывает InorderRec ()

    void inorder()  {

       inorderRec(root);

    }

  

    // Утилита для обхода порядка следования BST

    void inorderRec(Node root) {

        if (root != null) {

            inorderRec(root.left);

            System.out.println(root.key);

            inorderRec(root.right);

        }

    }

  

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

    public static void main(String[] args) {

        BinarySearchTree tree = new BinarySearchTree();

  

        / * Давайте создадим следующий BST

              50

           / /

          30 70

         / / / /

       20 40 60 80 *

        tree.insert(50);

        tree.insert(30);

        tree.insert(20);

        tree.insert(40);

        tree.insert(70);

        tree.insert(60);

        tree.insert(80);

  

        // выводим порядок следования BST

        tree.inorder();

    }

}
// Этот код предоставлен Ankur Narain Verma

питон

# Python программа для демонстрации операции вставки в бинарное дерево поиска

  
# Сервисный класс, который представляет отдельный узел в BST

class Node:

    def __init__(self,key):

        self.left = None

        self.right = None

        self.val = key

  
# Полезная функция для вставки нового узла с заданным ключом

def insert(root,node):

    if root is None:

        root = node

    else:

        if root.val < node.val:

            if root.right is None:

                root.right = node

            else:

                insert(root.right, node)

        else:

            if root.left is None:

                root.left = node

            else:

                insert(root.left, node)

  
# Полезная функция для обхода дерева заказов

def inorder(root):

    if root:

        inorder(root.left)

        print(root.val)

        inorder(root.right)

  

  
# Драйвер программы для проверки вышеуказанных функций
# Давайте создадим следующий BST
№ 50
# / /
# 30 70
# / / / /
# 20 40 60 80

r = Node(50)

insert(r,Node(30))

insert(r,Node(20))

insert(r,Node(40))

insert(r,Node(70))

insert(r,Node(60))

insert(r,Node(80))

  
# Печать Inoder обхода BST
inorder(r)

  
# Этот код предоставлен Bhavya Jain


Выход:

20
30
40
50
60
70
80

Иллюстрация для вставки 2 в дерево ниже:
1. Начните с корня.
2. Сравните вставляемый элемент с корнем, если меньше, чем корень, затем рекурсивно для левого, иначе рекурсивно для правого.
3. После достижения конца просто вставьте этот узел слева (если он меньше текущего), а затем справа.

Сложность времени: сложность времени поиска и вставки в наихудшем случае равна O (h), где h — высота Двоичного дерева поиска. В худшем случае нам, возможно, придется пройти от корня до самого глубокого листового узла. Высота перекошенного дерева может стать n, а временная сложность операций поиска и вставки может стать O (n).

Некоторые интересные факты:

  • Обход по порядку следования BST всегда производит отсортированный вывод.
  • Мы можем построить BST только с помощью предзаказа или после заказа или прохождения уровня заказа. Обратите внимание, что мы всегда можем получить обход по порядку, отсортировав единственный заданный обход.
  • Количество уникальных BST с n различными ключами является каталонским

Ссылки по теме:

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

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

Двоичное дерево поиска | Набор 1 (поиск и вставка)

0.00 (0%) 0 votes