4146. Двоичное дерево поиска 1

Реализуйте сбалансированное двоичное дерево поиска.

Вход. Содержит описание операций с деревом, количество которых не превышает 10⁵. Каждая строка содержит одну из следующих операций:

· insert x – добавить в дерево ключ x. Если ключ x уже присутствует в дереве, то ничего выполнять не надо.

· delete x – удалить из дерева ключ x. Если ключа x нет в дереве, то ничего выполнять не надо.

· exists x – если ключ x присутствует  в дереве, выведите “true”, иначе “false”.

Все числа целые и по модулю не превышают 10⁹.

Выход. Выведите последовательно результаты выполнения всех операций exists, следуя формату, приведённому в примере.

Пример входа	Пример выхода
insert 2 insert 5 insert 3 exists 2 exists 4 delete 5	true false

РЕШЕНИЕ

структуры данных - set

Анализ алгоритма

Промоделируем указанные операции при помощи множества set.

Реализация алгоритма

Объявим множество s.

set<int> s;

Читаем входные данные.

while (cin >> op >> x)

{

Вставка элемента во множество.

if (op == "insert") s.insert(x); else

Удаление элемента из множества если он там существует.

if (op == "delete") s.erase(x); else

{

Проверка существования элемента во множестве.

if (s.find(x) != s.end()) printf("true\n");

else printf("false\n");

}

}

Java реализация

import java.util.*;

public class Main

{

public static void main(String []args)

{

Scanner con = new Scanner(System.in);

TreeSet<Integer> s = new TreeSet<Integer>();

while(con.hasNext())

{

String c = con.next();

int x = con.nextInt();

if (c.charAt(0) == 'i') s.add(x); else

if (c.charAt(0) == 'd') s.remove(x); else

{

if (s.contains(x))

System.out.println("true");

else

System.out.println("false");

}

}

con.close();

}

}

Python реализация

import sys

Объявим рабочее множество.

s = set()

Читаем входные данные.

for line in sys.stdin:

op, x = line.split()

x = int(x)

Вставка элемента во множество.

if op == "insert":

s.add(x)

Удаление элемента из множества если он там существует.

elif op == "delete":

s.discard(x)

else:

Проверка существования элемента во множестве.

if x in s:

print("true")

else:

print("false")