e-olymp 6125. Простая очередь

22/07/2016 by Артур Тарасов

Задача

Реализуйте структуру данных «очередь». Напишите программу, содержащую описание очереди и моделирующую работу очереди, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:

push n — Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.
pop — Удалить из очереди первый элемент. Программа должна вывести его значение.
front — Программа должна вывести значение первого элемента, не удаляя его из очереди.
size — Программа должна вывести количество элементов в очереди.
clear — Программа должна очистить очередь и вывести ok.
exit — Программа должна вывести bye и завершить работу.

Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в очереди в любой момент не превосходит 100, все команды pop и front корректны, то есть при их исполнении в очереди содержится хотя бы один элемент.

Данную задачу также можно найти здесь.

Входные данные

Описаны в условии. Смотрите также тесты, расположенные ниже.

Выходные данные

Описаны в условии. Смотрите также тесты, расположенные ниже.

Тесты

№	Входные данные	Выходные данные
1	push 123 size push -5 pop exit	ok 1 ok 123 bye
2	push 1 push 2 front push 42 pop exit	ok ok 1 ok 1 bye
3	push 1 push 2 pop pop size exit	ok ok 1 2 0 bye

Код

import java.util.*;
import java.lang.*;
import java.io.*;

class MyQueue {
    int[] storage = new int[100];
    int start;
    int finish;
    MyQueue() {
        start = 0;
        finish = 0;
    }
    void push(int n) {
        storage[finish] = n;
        finish++;
    }
    int pop() {
        int a = storage[start];
        start++;
        return a;
    }
    int front() {
        return storage[start];
    }
    int size() {
        return finish - start;
    }
    String clear() {
        finish = 0;
        start = 0;
        return "ok";
    }
    String exit() {
        return "bye";
    }
}

public class Main {
	public static void main(String[] args) throws java.lang.Exception {
		String a;
		MyQueue x = new MyQueue();
		try (Scanner sc = new Scanner(System.in)) {
			while (sc.hasNextLine()){
				a = sc.next();
				if (a.equals("push")) {
					int n;
					n = sc.nextInt();
					x.push(n);
					System.out.println("ok");
				}
				if (a.equals("pop")) {
					System.out.println(x.pop());
				}
				if (a.equals("front")) {
					System.out.println(x.front());
				}
				if (a.equals("size")) {
					System.out.println(x.size());
				}
				if (a.equals("clear")) {
					System.out.println(x.clear());
				}
				if (a.equals("exit")) {
					System.out.println(x.exit());
					break;
				}
			}
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class MyQueue {

int[] storage = new int[100];

int start;

int finish;

MyQueue() {

start = 0;

finish = 0;

}

void push(int n) {

storage[finish] = n;

finish++;

}

int pop() {

int a = storage[start];

start++;

return a;

}

int front() {

return storage[start];

}

int size() {

return finish - start;

}

String clear() {

finish = 0;

start = 0;

return "ok";

}

String exit() {

return "bye";

}

public class Main {

public static void main(String[] args) throws java.lang.Exception {

String a;

MyQueue x = new MyQueue();

try (Scanner sc = new Scanner(System.in)) {

while (sc.hasNextLine()){

a = sc.next();

if (a.equals("push")) {

int n;

n = sc.nextInt();

x.push(n);

System.out.println("ok");

}

if (a.equals("pop")) {

System.out.println(x.pop());

}

if (a.equals("front")) {

System.out.println(x.front());

}

if (a.equals("size")) {

System.out.println(x.size());

}

if (a.equals("clear")) {

System.out.println(x.clear());

}

if (a.equals("exit")) {

System.out.println(x.exit());

break;

}

Реализуем абстрактный тип данных очередь, который отвечает принципу FIFO («первый вошёл – первый вышел») с помощью массива. Очередь имеет начало и конец, на которые указывают соответственно start и finish. Изначально очередь является пустой, поэтому start = 0, finish = 0. При добавлении нового элемента в очередь записываем его в конец. finish при этом увеличиваем на единицу. Извлекаемый же элемент берём в начале очереди, после чего start++. Если необходимо получить значение начала очереди, не извлекая его, воспользуемся функцией front(), возвращающей значение первого элемента. Для получения размера очереди используем функцию size(), которая возвращает разницу между концом и началом очереди. Если очередь нужно очистить, то приравниваем finish и start к нулю.

Код на сайте ideone.com находится здесь.

Timus №2002

28/12/2015 by yanishevskaya

Условие и начальные данные можно посмотреть по ссылке.

Тест:

исходные данные	результат
6
register alena 223344	success: new user added
login alena 223	fail: incorrect password
login alena 223344	success: user logged in
login john 454545	fail: no such user
logout alena	success: user logged out
logout alena	fail: already logged out

Решение:

import java.util.*;
import java.lang.*;
import java.io.*;
 
public class Main
{
	public static String register(String username, String password, HashMap< String, String> usersAndPasswords)
	{
		//проверяем, есть ли такой пользователь
		if(usersAndPasswords.containsKey(username)){
			//если есть, то мы не можем добавить нового с таким же именем
			return "fail: user already exists";
		} else {
			//если нет, то добавляем нового пользователя
			usersAndPasswords.put(username, password);
			return "success: new user added";
		}
	}
	public static String login(String username, String password, HashMap< String, String> usersAndPasswords, HashMap< String, Integer> loggedInUsers)
	{
		//проверяем, зарегистрирован ли такой пользователь
		if(usersAndPasswords.containsKey(username)){
			//проверяем, совпадает ли зарегистрированный пароль с введенным паролем
			if (usersAndPasswords.get(username).equals(password)){
				//проверяем, есть ли такой пользователь в списке вошедших пользователей
				if(loggedInUsers.containsKey(username)) {
					return "fail: already logged in";
				} else { 
					loggedInUsers.put(username,1);
					return "success: user logged in";
				}
			} else return "fail: incorrect password";
		} else return "fail: no such user";
	}
	public static String logout(String username, HashMap< String, String> usersAndPasswords, HashMap< String, Integer> loggedInUsers)
	{
		//проверяем, зарегистрирован ли такой пользователь
		if(usersAndPasswords.containsKey(username)){
			//проверяем, есть ли пользователь в списке вошедших
			if(loggedInUsers.containsKey(username)) {
				//если есть, то удаляем его
				loggedInUsers.remove(username);
				return "success: user logged out";
			} else return "fail: already logged out";
		} else return "fail: no such user";
	}
	public static void main (String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int n;
		n = sc.nextInt();
		//список зарегистрированных пользователей и их пароли
		HashMap< String, String> usersAndPasswords = new HashMap< String, String>();
		//список вошедших пользователей
		HashMap< String, Integer> loggedInUsers = new HashMap< String, Integer>();
		String command;
		String username;
		String password;
		for(int i = 0; i < n; i++) {
			command = sc.next();
			if(command.equals("register")) {
				username = sc.next();
				password = sc.next();
				System.out.println(register(username, password, usersAndPasswords));
			} else if(command.equals("login")){
				username = sc.next();
				password = sc.next();
				System.out.println(login(username, password, usersAndPasswords, loggedInUsers));
			} else if(command.equals("logout")){
				username = sc.next();
				System.out.println(logout(username, usersAndPasswords, loggedInUsers));
			}
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

public static String register(String username, String password, HashMap< String, String> usersAndPasswords)

{

//проверяем, есть ли такой пользователь

if(usersAndPasswords.containsKey(username)){

//если есть, то мы не можем добавить нового с таким же именем

return "fail: user already exists";

} else {

//если нет, то добавляем нового пользователя

usersAndPasswords.put(username, password);

return "success: new user added";

}

public static String login(String username, String password, HashMap< String, String> usersAndPasswords, HashMap< String, Integer> loggedInUsers)

{

//проверяем, зарегистрирован ли такой пользователь

if(usersAndPasswords.containsKey(username)){

//проверяем, совпадает ли зарегистрированный пароль с введенным паролем

if (usersAndPasswords.get(username).equals(password)){

//проверяем, есть ли такой пользователь в списке вошедших пользователей

if(loggedInUsers.containsKey(username)) {

return "fail: already logged in";

} else {

loggedInUsers.put(username,1);

return "success: user logged in";

}

} else return "fail: incorrect password";

} else return "fail: no such user";

}

public static String logout(String username, HashMap< String, String> usersAndPasswords, HashMap< String, Integer> loggedInUsers)

{

//проверяем, зарегистрирован ли такой пользователь

if(usersAndPasswords.containsKey(username)){

//проверяем, есть ли пользователь в списке вошедших

if(loggedInUsers.containsKey(username)) {

//если есть, то удаляем его

loggedInUsers.remove(username);

return "success: user logged out";

} else return "fail: already logged out";

} else return "fail: no such user";

}

public static void main (String[] args)

{

Scanner sc = new Scanner(System.in);

int n;

n = sc.nextInt();

//список зарегистрированных пользователей и их пароли

HashMap< String, String> usersAndPasswords = new HashMap< String, String>();

//список вошедших пользователей

HashMap< String, Integer> loggedInUsers = new HashMap< String, Integer>();

String command;

String username;

String password;

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

command = sc.next();

if(command.equals("register")) {

username = sc.next();

password = sc.next();

System.out.println(register(username, password, usersAndPasswords));

} else if(command.equals("login")){

username = sc.next();

password = sc.next();

System.out.println(login(username, password, usersAndPasswords, loggedInUsers));

} else if(command.equals("logout")){

username = sc.next();

System.out.println(logout(username, usersAndPasswords, loggedInUsers));

}

Для решения этой задачи я использовала два ассоциативных массива. Первый (usersAndPasswords) хранит в качестве ключа имя зарегистрированного пользователя, а в качестве значения — пароль этого пользователя; второй (loggedInUsers) хранит вошедших на форум пользователей, а в качестве значения всегда единица, потому что мы никак не используем значение, нам важно только есть ли имя пользователя в этом массиве или нет.

Когда пользователь входит на форум мы добавляем его имя как ключ в массив loggedInUsers. А когда он выходит мы удаляем его из этого массива. Для проверки есть ли пользователь на форуме или он уже вышел, мы проверяем есть ли он в массиве loggedInUsers или нету.

Ссылка на решение на ideone.

Ссылка на засчитанное решение на http://acm.timus.ru/.

Timus 2002 by Tolia

25/12/2015 by Осецимский Анатолий

Для решения использовалось AVL-дерево выложенное тут.

Алгоритм решения задачи с соответствием с условием задачи.

import java.util.Scanner;

/**
 * Created by green on 25.12.15.
 */

class State{
    String password;
    Boolean login;
    State(String password){
        this.password = password;
        login = false;
    }
}


public class Task2002 {
    public static void main (String[] args) {
        AVL<String, State> DB = new AVL();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String s;
        for(int i = 0; i < n; i++){
            s = in.next();
            if(s.equals("register")){
                String name = in.next(), pass = in.next();
                if(DB.containKey(name)){
                    System.out.println("fail: user already exists");
                }else{
                    DB.add(name,new State(pass));
                    System.out.println("success: new user added");
                }
            }else if(s.equals("login")){
                String name = in.next(), pass = in.next();
                State temp = DB.get(name);
                if (temp == null) {
                    System.out.println("fail: no such user");
                }
                else if (!pass.equals(temp.password)) {
                    System.out.println("fail: incorrect password");
                }
                else {
                    if (temp.login == false) {
                        temp.login = true;
                        DB.add(name, temp);
                        System.out.println("success: user logged in");
                    }
                    else {
                        System.out.println("fail: already logged in");
                    }
                }
            }else{
                String name = in.next();
                State temp = DB.get(name);
                if (temp == null) {
                    System.out.println("fail: no such user");
                }
                else {
                    if (temp.login == true) {
                        temp.login = false;
                        DB.add(name, temp);
                        System.out.println("success: user logged out");
                    }
                    else {
                        System.out.println("fail: already logged out");
                    }
                }
            }
        }
    }
}

import java.util.Scanner;

/**

* Created by green on 25.12.15.

class State{

String password;

Boolean login;

State(String password){

this.password = password;

}

public class Task2002 {

public static void main (String[] args) {

AVL<String, State> DB = new AVL();

Scanner in = new Scanner(System.in);

int n = in.nextInt();

String s;

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

s = in.next();

if(s.equals("register")){

String name = in.next(), pass = in.next();

if(DB.containKey(name)){

System.out.println("fail: user already exists");

}else{

DB.add(name,new State(pass));

System.out.println("success: new user added");

}

}else if(s.equals("login")){

String name = in.next(), pass = in.next();

State temp = DB.get(name);

if (temp == null) {

System.out.println("fail: no such user");

}

else if (!pass.equals(temp.password)) {

System.out.println("fail: incorrect password");

}

else {

if (temp.login == false) {

temp.login = true;

DB.add(name, temp);

System.out.println("success: user logged in");

}

else {

System.out.println("fail: already logged in");

}

}else{

String name = in.next();

State temp = DB.get(name);

if (temp == null) {

System.out.println("fail: no such user");

}

else {

if (temp.login == true) {

temp.login = false;

DB.add(name, temp);

System.out.println("success: user logged out");

}

else {

System.out.println("fail: already logged out");

}

Ссылка на решение.

BST – Двоичные деревья поиска

24/12/2015 by Максим Швандт

Задача

Разработать класс, реализующий функциональность дерева двоичного поиска.

Ссылка на условие http://java.mazurok.com/word-of-week/bst

Тесты

input	output
put S 11.11	Ok
put E 22.22	Ok
put A 33.33	Ok
put R 44.44	Ok
put H 55.55	Ok
put C 66.66	Ok
put X 77.77	Ok
put M 88.88	Ok
size	8
min	(A->33.33)/2
max	(X->77.77)/1
print	L0: (S->11.11)/8 .L1: (E->22.22)/6 ..L2: (A->33.33)/2 …L3: (C->66.66)/1 ..L2: (R->44.44)/3 …L3: (H->55.55)/2 ….L4: (M->88.88)/1 .L1: (X->77.77)/1
delete E	Ok
size	7
min	(A->33.33)/2
max	(X->77.77)/1
print	L0: (S->11.11)/7 .L1: (H->55.55)/5 ..L2: (A->33.33)/2 …L3: (C->66.66)/1 ..L2: (R->44.44)/2 …L3: (M->88.88)/1 .L1: (X->77.77)/1
exit	N/A

Критерий тестирования

В ходе тестирования мы добавляем 8 ключей с уникальными значениями. Затем мы определяем размер, минимальный и максимальный узлы, а также распечатываем все дерево, чтобы убедится, что оно имеет ожидаемою конфигурацию. Затем мы удаляем 1 ключ с серединным значением и повторяем вышеперечисленные операции, чтобы увидеть ожидаемые изменения в дереве.

Формат вывода:

Команды min и max выводят одиночный узел в следующем формате: (ключ->значение)/кол-во узлов

Команда print выводит дерево по уровням, каждая строчка имеет следующий формат: уровень: (ключ->значение)/кол-во узлов

Структура программы

Код программы состоит из следующих элементов, объединенных в пакет odessa.uni.imem.maxim:

Класс CountingBST, реализующий функциональность дерева двоичного поиска с подсчетом количества узлов в дереве
Класс CountingBSTTestApp, реализующий тестовое приложение

Класс CountingBST

package odessa.uni.imem.maxim;

class CountingBST<Key extends Comparable<Key>, Value>
{

   // --------------------------------------------------------------------------
   public class Node
   {
      Key key;
      Value value;
      Node left, right;
      int count;

      public Node( Key key, Value value, int count)
      {
         this.key = key;
         this.value = value;
         this.left = this.right = null;
         this.count = count;
      }
   }

   private Node root;

   // --------------------------------------------------------------------------
   public void put( Key key, Value val )
   {
      root = put( root, key, val );
   }

   // --------------------------------------------------------------------------
   private Node put( Node x, Key key, Value val )
   {
      if (x == null)
         return new Node( key, val, 1 );
      int cmp = key.compareTo( x.key );
      if (cmp < 0)
         x.left = put( x.left, key, val );
      else if (cmp > 0)
         x.right = put( x.right, key, val );
      else if (cmp == 0)
         x.value = val;
      x.count = 1 + size( x.left ) + size( x.right );
      return x;
   }

   // --------------------------------------------------------------------------
   public Value get( Key key )
   {
      Node x = root;
      while (x != null)
      {
         int cmp = key.compareTo( x.key );
         if (cmp < 0)
            x = x.left;
         else if (cmp > 0)
            x = x.right;
         else if (cmp == 0)
            return x.value;
      }
      return null;
   }

   // --------------------------------------------------------------------------
   public int size()
   {
      return size( root );
   }

   // --------------------------------------------------------------------------
   private int size( Node x )
   {
      if (x == null)
         return 0;
      return x.count;
   }
   
   // --------------------------------------------------------------------------
   public Node min()
   {
      return min(root);
   }
   
   // --------------------------------------------------------------------------
   private Node min( Node x )
   {
      if ( x != null )
      {
         if (x.left == null)
         {
            return x;
         }
         return min( x.left );
      }
      return null;
   }

   // --------------------------------------------------------------------------
   public Node max()
   {
      return max(root);
   }
   
   // --------------------------------------------------------------------------
   private Node max( Node x )
   {
      if ( x != null )
      {
         if (x.right == null)
         {
            return x;
         }
         return max( x.right );
      }
      return null;
   }
 

   // --------------------------------------------------------------------------
   private Node deleteMin( Node x )
   {
      if ( x != null )
      {
         if (x.left == null)
            return x.right;
         x.left = deleteMin( x.left );
         x.count = 1 + size(x.left) + size(x.right);
         return x;
      }
      return null;
   }

   // --------------------------------------------------------------------------
   public void delete( Key key )
   {
      root = delete( root, key );
   }

   // --------------------------------------------------------------------------
   private Node delete( Node x, Key key )
   {
      if (x == null)
         return null;
      int cmp = key.compareTo( x.key );
      if (cmp < 0)
         x.left = delete( x.left, key );
      else if (cmp > 0)
         x.right = delete( x.right, key );
      else
      {
         if (x.right == null)
            return x.left;
         if (x.left == null)
            return x.right;
         Node t = x;
         x = min( t.right );
         x.right = deleteMin( t.right );
         x.left = t.left;
      }
      x.count = size( x.left ) + size( x.right ) + 1;
      return x;
   }

   // --------------------------------------------------------------------------
   private void print( Node node, int level )
   {
      if (node != null)
      {
         for( int i = 0; i<level; i++ )
         {
            System.out.print( "." );
         }
         System.out.printf( "L%d: (", level );
         System.out.print( node.key );
         System.out.print( "->" );
         System.out.print( node.value );
         System.out.print( ")" );
         System.out.printf( "/%d", node.count );
         System.out.println();

         print( node.left, level + 1 );
         print( node.right, level + 1 );
      }
   }

   // --------------------------------------------------------------------------
   public void print()
   {
      print( root, 0 );
   }

   // also maxKey, minKey,

}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

package odessa.uni.imem.maxim;

class CountingBST<Key extends Comparable<Key>, Value>

{

// --------------------------------------------------------------------------

public class Node

{

Key key;

Value value;

Node left, right;

int count;

public Node( Key key, Value value, int count)

{

this.key = key;

this.value = value;

this.left = this.right = null;

this.count = count;

}

private Node root;

// --------------------------------------------------------------------------

public void put( Key key, Value val )

{

root = put( root, key, val );

}

// --------------------------------------------------------------------------

private Node put( Node x, Key key, Value val )

{

if (x == null)

return new Node( key, val, 1 );

int cmp = key.compareTo( x.key );

if (cmp < 0)

x.left = put( x.left, key, val );

else if (cmp > 0)

x.right = put( x.right, key, val );

else if (cmp == 0)

x.value = val;

x.count = 1 + size( x.left ) + size( x.right );

return x;

}

// --------------------------------------------------------------------------

public Value get( Key key )

{

Node x = root;

while (x != null)

{

int cmp = key.compareTo( x.key );

if (cmp < 0)

x = x.left;

else if (cmp > 0)

x = x.right;

else if (cmp == 0)

return x.value;

}

return null;

}

// --------------------------------------------------------------------------

public int size()

{

return size( root );

}

// --------------------------------------------------------------------------

private int size( Node x )

{

if (x == null)

return 0;

return x.count;

}

// --------------------------------------------------------------------------

public Node min()

{

return min(root);

}

// --------------------------------------------------------------------------

private Node min( Node x )

{

if ( x != null )

{

if (x.left == null)

{

return x;

}

return min( x.left );

}

return null;

}

// --------------------------------------------------------------------------

public Node max()

{

return max(root);

}

// --------------------------------------------------------------------------

private Node max( Node x )

{

if ( x != null )

{

if (x.right == null)

{

return x;

}

return max( x.right );

}

return null;

}

// --------------------------------------------------------------------------

private Node deleteMin( Node x )

{

if ( x != null )

{

if (x.left == null)

return x.right;

x.left = deleteMin( x.left );

x.count = 1 + size(x.left) + size(x.right);

return x;

}

return null;

}

// --------------------------------------------------------------------------

public void delete( Key key )

{

root = delete( root, key );

}

// --------------------------------------------------------------------------

private Node delete( Node x, Key key )

{

if (x == null)

return null;

int cmp = key.compareTo( x.key );

if (cmp < 0)

x.left = delete( x.left, key );

else if (cmp > 0)

x.right = delete( x.right, key );

else

{

if (x.right == null)

return x.left;

if (x.left == null)

return x.right;

Node t = x;

x = min( t.right );

x.right = deleteMin( t.right );

x.left = t.left;

}

x.count = size( x.left ) + size( x.right ) + 1;

return x;

}

// --------------------------------------------------------------------------

private void print( Node node, int level )

{

if (node != null)

{

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

{

System.out.print( "." );

}

System.out.printf( "L%d: (", level );

System.out.print( node.key );

System.out.print( "->" );

System.out.print( node.value );

System.out.print( ")" );

System.out.printf( "/%d", node.count );

System.out.println();

print( node.left, level + 1 );

print( node.right, level + 1 );

}

// --------------------------------------------------------------------------

public void print()

{

print( root, 0 );

}

// also maxKey, minKey,

}

Все методы разделены на пары — один метод пары приватный, а другой — публичный. Это необходимо для того, чтобы передавать первым аргументом корень дерева, начиная с которого выполняются все операции. Каждый приватный метод содержит первым аргументом узел, начиная с которого будет выполнятся операция. Публичный метод вызывает приватный и передает ему в качестве первого аргумента корень дерева. Это относится к основным операциям на дереве:

put — помещает ключ и значение в дерево
get — извлекает значение по клчу
size — возвращает количество узлов дерева
min — находит узел с минимальным ключом
max — находит узел с максимальным ключом
delete — удаление по Хиббарду ( Coursera presentation )
print — печать дерева

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

Класс CountingBSTTestApp

package odessa.uni.imem.maxim;

import java.util.*;

public class CountingBSTTestApp
{

   // parse text line into tokens, e.g. "put salary 120.22" to "put" "salary" "120.22"
   public static Vector<String> parseTextToTokens( String text )
   {
      Vector<String> tokens = new Vector<String>();
      StringTokenizer st = new StringTokenizer(text);        
      while (st.hasMoreTokens())
      {
         tokens.add(st.nextToken());
      }
      return tokens;
   }

   // helper function: converts string to double if possible or returns null
   public static Double strToDouble( String s )
   {
      Double x = null;
      try
      {
         x = Double.parseDouble( s );
      }
      catch( NumberFormatException e )
      {
      }
      return x;
   }

   // print content of one node into human readable form
   public static void printTreeNode( CountingBST<String,Double>.Node node )
   {
      if ( node != null )
      {
         System.out.print( "(" );
         System.out.print( node.key );
         System.out.print( "->" );
         System.out.print( node.value );
         System.out.print( ")/" );
         System.out.print( node.count );
         System.out.println();
      }
      else
      {
         System.out.println("null");
      }
   }
   
   // main method with command line interpreter
   public static void main(String[] args)
   {
      CountingBST<String,Double> tree = new CountingBST<String,Double>(); 
      
      Scanner in = new Scanner(System.in);
      
      for(;;)
      {
        String inputLine = in.nextLine();
        if ( inputLine.isEmpty() )
        {
           continue;  
        }
        
        String cmd = null;
        String arg1 = null;
        String arg2 = null;
       
        {
           Vector<String> inputTokens = parseTextToTokens( inputLine );
           if ( inputTokens.size() > 0 ) cmd  = inputTokens.get(0);
           if ( inputTokens.size() > 1 ) arg1 = inputTokens.get(1);
           if ( inputTokens.size() > 2 ) arg2 = inputTokens.get(2);
        }
        
        if ( cmd.equals("exit") )
        {
           break;  
        }
        else
        if ( cmd.equals("print") )
        {
           tree.print();
        }
        else 
        if (cmd.equals("size"))
        {
           System.out.println(tree.size());
        }
        else
        if ( cmd.equals("put") )
        {
           String key   = ( arg1 != null && !arg1.isEmpty()) ? arg1 : null ;
           Double value = ( arg2 != null ) ? strToDouble( arg2 ) : null ;
           if ( key == null || value == null )
           {
              System.out.printf("*** ERROR: wrong arguments: <%s> <%s> <%s>\n",cmd,arg1,arg2);
              continue;
           }
           tree.put( key, value );
           System.out.println("Ok");
        }
        else if ( cmd.equals("get") )
        {
           String key   = ( arg1 != null && !arg1.isEmpty()) ? arg1 : null ;
           if ( key == null )
           {
              System.out.printf("*** ERROR: wrong arguments: <%s> <%d>\n",cmd,arg1);
              continue;
           }
           Double value = tree.get( key );
           System.out.println(value);
        }
        else if ( cmd.equals("delete") )
        {
           String key   = ( arg1 != null && !arg1.isEmpty()) ? arg1 : null ;
           if ( key == null )
           {
              System.out.printf("*** ERROR: wrong arguments: <%s> <%d>\n",cmd,arg1);
              continue;
           }
           tree.delete( key );
           System.out.println("Ok");
        }
        else if ( cmd.equals("min") )
        {
           printTreeNode( tree.min() );
        } 
        else if ( cmd.equals("max") )
        {
           printTreeNode( tree.max() );
        }
        
      }
      
      in.close();

  } 
   
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

package odessa.uni.imem.maxim;

import java.util.*;

public class CountingBSTTestApp

{

// parse text line into tokens, e.g. "put salary 120.22" to "put" "salary" "120.22"

public static Vector<String> parseTextToTokens( String text )

{

Vector<String> tokens = new Vector<String>();

StringTokenizer st = new StringTokenizer(text);

while (st.hasMoreTokens())

{

tokens.add(st.nextToken());

}

return tokens;

}

// helper function: converts string to double if possible or returns null

public static Double strToDouble( String s )

{

Double x = null;

try

{

x = Double.parseDouble( s );

}

catch( NumberFormatException e )

{

}

return x;

}

// print content of one node into human readable form

public static void printTreeNode( CountingBST<String,Double>.Node node )

{

if ( node != null )

{

System.out.print( "(" );

System.out.print( node.key );

System.out.print( "->" );

System.out.print( node.value );

System.out.print( ")/" );

System.out.print( node.count );

System.out.println();

}

else

{

System.out.println("null");

}

// main method with command line interpreter

public static void main(String[] args)

{

CountingBST<String,Double> tree = new CountingBST<String,Double>();

Scanner in = new Scanner(System.in);

for(;;)

{

String inputLine = in.nextLine();

if ( inputLine.isEmpty() )

{

continue;

}

String cmd = null;

String arg1 = null;

String arg2 = null;

{

Vector<String> inputTokens = parseTextToTokens( inputLine );

if ( inputTokens.size() > 0 ) cmd = inputTokens.get(0);

if ( inputTokens.size() > 1 ) arg1 = inputTokens.get(1);

if ( inputTokens.size() > 2 ) arg2 = inputTokens.get(2);

}

if ( cmd.equals("exit") )

{

break;

}

else

if ( cmd.equals("print") )

{

tree.print();

}

else

if (cmd.equals("size"))

{

System.out.println(tree.size());

}

else

if ( cmd.equals("put") )

{

String key = ( arg1 != null && !arg1.isEmpty()) ? arg1 : null ;

Double value = ( arg2 != null ) ? strToDouble( arg2 ) : null ;

if ( key == null || value == null )

{

System.out.printf("*** ERROR: wrong arguments: <%s> <%s> <%s>\n",cmd,arg1,arg2);

continue;

}

tree.put( key, value );

System.out.println("Ok");

}

else if ( cmd.equals("get") )

{

String key = ( arg1 != null && !arg1.isEmpty()) ? arg1 : null ;

if ( key == null )

{

System.out.printf("*** ERROR: wrong arguments: <%s> <%d>\n",cmd,arg1);

continue;

}

Double value = tree.get( key );

System.out.println(value);

}

else if ( cmd.equals("delete") )

{

String key = ( arg1 != null && !arg1.isEmpty()) ? arg1 : null ;

if ( key == null )

{

System.out.printf("*** ERROR: wrong arguments: <%s> <%d>\n",cmd,arg1);

continue;

}

tree.delete( key );

System.out.println("Ok");

}

else if ( cmd.equals("min") )

{

printTreeNode( tree.min() );

}

else if ( cmd.equals("max") )

{

printTreeNode( tree.max() );

}

in.close();

}

Данный класс реализует тестовое приложение для класса CountingBST. Он содержит вспомогательные функции ввода и функцию main, содержащую код теста. Он реализует командный интерпритатор, где каждая команда вызывает соответствующий публичный метод тестируемого класса. По-этому тест представляет собой текстовый файл с командами для стандартного потока ввода с консоли.

Ссылка на Ideone: https://ideone.com/b0xrPX

acm.timus.ru №2002. Тестовое задание

22/12/2015 by Максим Швандт

Автор задачи: Кирилл Бороздин
Источник задачи: Уральская региональная командная олимпиада по программированию 2013

Ограничения:

Время:	0.5 секунды
Память	64 Мб

Условие

Это было обычное хмурое октябрьское утро. Небо было затянуто тяжёлыми серыми тучами, накрапывал дождь. Капли падали на стёкла автомобилей, били в окна домов. Илья сидел за компьютером и угрюмо взирал на унылый пейзаж за окном. Внезапно его взгляд привлекла надпись, появившаяся в правом нижнем углу экрана: «You have 1 unread email message(s)». Заранее приготовившись удалить бесполезный спам, Илья открыл письмо. Однако оно оказалось куда интереснее…

Вас приветствует отдел по работе с персоналом компании «Рутнок БКС»!

Мы рассмотрели вашу заявку на вакансию разработчика программного обеспечения и были заинтересованы вашей кандидатурой. Для оценки ваших профессиональных навыков мы предлагаем вам выполнить несложное тестовое задание: необходимо реализовать систему регистрации для форума. Она должна поддерживать три операции:

«register username password» — зарегистрировать нового пользователя с именем «username» и установить для него пароль «password». Если такой пользователь уже есть в базе данных, необходимо выдать ошибку «fail: user already exists». Иначе нужно вывести сообщение «success: new user added».
«login username password» — войти в систему от имени пользователя «username» с паролем «password». Если такого пользователя не существует в базе данных, необходимо выдать «fail: no such user». Иначе, если был введен неправильный пароль, нужно выдать «fail: incorrect password». Иначе, если пользователь уже находится в системе в данный момент, необходимо вывести «fail: already logged in». Иначе нужно вывести сообщение «success: user logged in».
«logout username» — выйти из системы пользователем «username». Если такого пользователя не существует, необходимо вывести «fail: no such user». Иначе, если пользователь не находится в системе в данный момент, следует выдать «fail: already logged out». Иначе необходимо выдать сообщение «success: user logged out».

Пользуйтесь этим письмом как формальным описанием алгоритма и строго соблюдайте порядок обработки ошибок. Желаем вам удачи!

И вот Илья, откинув все дела, уже решает тестовое задание. Попробуйте и вы выполнить его!

Исходные данные

В первой строке дано целое число [latex]n[/latex] — количество операций [latex]1\leq n\leq 100[/latex]. В каждой из следующих [latex]n[/latex] строк содержится один запрос в соответствии с форматом, описанным выше. В качестве «username» и «password» могут выступать любые непустые строки длиной до 30 символов включительно. Строки могут состоять только из символов с кодами от 33 до 126.

Результат

Для каждой операции выведите в отдельной строке сообщение в соответствии с форматом, описанным выше. Строго соблюдайте расстановку пробелов и знаков препинания в этих сообщениях.

Пример

Исходные данные

Результат

6register vasya 12345

logout vasya

success: new user addedfail: incorrect password

success: user logged in

fail: no such user

success: user logged out

fail: already logged out

Код

import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.Vector;
import java.util.TreeMap;
import java.lang.NumberFormatException;

public class Timus2002App
{

   //структура, описывающая атрибуты учетной записи
   public class AccountInfo
   {
      public String password;
      public boolean loggedIn;

      public AccountInfo(String argPassword, boolean argLoggedIn)
      {
         password = argPassword;
         loggedIn = argLoggedIn;
      }
   }

   
   //база данных учетной записи
   public class AccountDatabase
   {
      public static final int OK = 0;
      public static final int NOT_REGISTERED = 1;
      public static final int WRONG_PASSWORD = 2;
      public static final int ALREADY_LOGGED_IN = 3;
      public static final int ALREADY_LOGGED_OUT = 4;

      private TreeMap<String, AccountInfo> map;

      //конструктор
      public AccountDatabase()
      {
         map = new TreeMap<String, AccountInfo>();
      }

      //регистрация новой учетной записи
      public boolean register(String name, String password)
      {
         AccountInfo info = map.get(name);

         if (info != null)
         {
            return false;
         }

         map.put(name, new AccountInfo(password, false));

         return true;
      }

      //вход в систему
      public int login(String name, String password)
      {
         int result = NOT_REGISTERED;

         AccountInfo info = map.get(name);

         if (info != null)
         {
            if (!info.password.equals(password))
            {
               result = WRONG_PASSWORD;
            }
            else if (info.loggedIn)
            {
               result = ALREADY_LOGGED_IN;
            }
            else
            {
               map.put(name, new AccountInfo(info.password, true));
               result = OK;
            }
         }

         return result;
      }

      //выход из системы
      public int logout(String name)
      {
         int result = NOT_REGISTERED;

         AccountInfo info = map.get(name);

         if ( info != null )
         {
            if ( info.loggedIn )
            {
               map.put(name, new AccountInfo(info.password, false));
               result = OK;
            }
            else
            {
               result = ALREADY_LOGGED_OUT;
            }
         }

         return result;
      }

   }

   public static void main(String[] args)
   {
      int loginCount = 0;
      String line = null;
      
      Scanner in = new Scanner(System.in);
      //System.out.println("please enter number of logins: ");
      line = ( in.hasNextLine( ) ) ? in.nextLine() : null;
      try
      {
         loginCount = Integer.parseInt(line.trim());
      }
      catch( NumberFormatException e )
      {
      }
      
      if ( loginCount < 1 || loginCount > 100 )
      {
         System.out.println("**** ERROR: wrong number of logins ****");
         in.close();
         return;
      }
      
      Timus2002App mainObj = new Timus2002App();
      AccountDatabase accounts = mainObj.new AccountDatabase();
      
      for( int i = 0; i < loginCount; i++ )
      {
         //System.out.println("please enter command:");
         
         line = ( in.hasNextLine( ) ) ? in.nextLine() : null;
         if ( line == null || line.isEmpty() )
         {
            System.out.println("**** ERROR: empty input, abort processing ****");
            break;
         }
         
         //превращение введенной строки текста в вектор лексем
         StringTokenizer st = new StringTokenizer(line, " ");
         Vector<String> tokens = new Vector<String>();
         while (st.hasMoreTokens())
         {
            tokens.add( st.nextToken() );
         }

         //превращение вектора лексем в команду с аргументами
         String command   = ( tokens.size() > 0 ) ? tokens.get(0) : null;
         String name      = ( tokens.size() > 1 ) ? tokens.get(1) : null;
         String password  = ( tokens.size() > 2 ) ? tokens.get(2) : null;
         String message = null;
        
        //выполнение команд
         if ( command.equals("register"))
         {
            if ( name != null || password != null )
            {
               if ( accounts.register(name, password) )
               {
                  message = "success: new user added";
               }
               else
               {
                  message = "fail: user already exists";
               }
            }
            else
            {
               message = "fail: missing user name or password";
            }
         }
         else if ( command.equals("login"))
         {
            if ( name != null || password != null )
            {
               switch( accounts.login(name, password) )
               {
                  case AccountDatabase.NOT_REGISTERED:
                     message = "fail: no such user";
                  break;
                  case AccountDatabase.WRONG_PASSWORD:
                     message = "fail: incorrect password";
                  break;
                  case AccountDatabase.ALREADY_LOGGED_IN:
                     message = "fail: already logged in";
                  break;
                  default:
                     message = "success: user logged in";
                  break;
              }
           }
           else
           {
              message = "fail: missing user name or password";
           }
         }
         else if ( command.equals("logout"))
         {
            if ( name != null )
            {
               switch( accounts.logout(name) )
               {
                  case AccountDatabase.ALREADY_LOGGED_OUT:
                     message = "fail: already logged out";
                  break;
                  case AccountDatabase.NOT_REGISTERED:
                     message = "fail: no such user";
                  break;
                  default:
                     message = "success: user logged out";
                  break;
               }
            }
            else
            {
               message = "fail: missing user name";
            }
         }
         
         if ( message != null )
         {
            System.out.println(message);
         }
      }
      in.close();
   } 
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

import java.util.Scanner;

import java.util.StringTokenizer;

import java.util.Vector;

import java.util.TreeMap;

import java.lang.NumberFormatException;

public class Timus2002App

{

//структура, описывающая атрибуты учетной записи

public class AccountInfo

{

public String password;

public boolean loggedIn;

public AccountInfo(String argPassword, boolean argLoggedIn)

{

password = argPassword;

loggedIn = argLoggedIn;

}

//база данных учетной записи

public class AccountDatabase

{

public static final int OK = 0;

public static final int NOT_REGISTERED = 1;

public static final int WRONG_PASSWORD = 2;

public static final int ALREADY_LOGGED_IN = 3;

public static final int ALREADY_LOGGED_OUT = 4;

private TreeMap<String, AccountInfo> map;

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

public AccountDatabase()

{

map = new TreeMap<String, AccountInfo>();

}

//регистрация новой учетной записи

public boolean register(String name, String password)

{

AccountInfo info = map.get(name);

if (info != null)

{

return false;

}

map.put(name, new AccountInfo(password, false));

return true;

}

//вход в систему

public int login(String name, String password)

{

int result = NOT_REGISTERED;

AccountInfo info = map.get(name);

if (info != null)

{

if (!info.password.equals(password))

{

result = WRONG_PASSWORD;

}

else if (info.loggedIn)

{

result = ALREADY_LOGGED_IN;

}

else

{

map.put(name, new AccountInfo(info.password, true));

result = OK;

}

return result;

}

//выход из системы

public int logout(String name)

{

int result = NOT_REGISTERED;

AccountInfo info = map.get(name);

if ( info != null )

{

if ( info.loggedIn )

{

map.put(name, new AccountInfo(info.password, false));

result = OK;

}

else

{

result = ALREADY_LOGGED_OUT;

}

return result;

}

public static void main(String[] args)

{

int loginCount = 0;

String line = null;

Scanner in = new Scanner(System.in);

//System.out.println("please enter number of logins: ");

line = ( in.hasNextLine( ) ) ? in.nextLine() : null;

try

{

loginCount = Integer.parseInt(line.trim());

}

catch( NumberFormatException e )

{

}

if ( loginCount < 1 || loginCount > 100 )

{

System.out.println("**** ERROR: wrong number of logins ****");

in.close();

return;

}

Timus2002App mainObj = new Timus2002App();

AccountDatabase accounts = mainObj.new AccountDatabase();

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

{

//System.out.println("please enter command:");

line = ( in.hasNextLine( ) ) ? in.nextLine() : null;

if ( line == null || line.isEmpty() )

{

System.out.println("**** ERROR: empty input, abort processing ****");

break;

}

//превращение введенной строки текста в вектор лексем

StringTokenizer st = new StringTokenizer(line, " ");

Vector<String> tokens = new Vector<String>();

while (st.hasMoreTokens())

{

tokens.add( st.nextToken() );

}

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

String command = ( tokens.size() > 0 ) ? tokens.get(0) : null;

String name = ( tokens.size() > 1 ) ? tokens.get(1) : null;

String password = ( tokens.size() > 2 ) ? tokens.get(2) : null;

String message = null;

//выполнение команд

if ( command.equals("register"))

{

if ( name != null || password != null )

{

if ( accounts.register(name, password) )

{

message = "success: new user added";

}

else

{

message = "fail: user already exists";

}

else

{

message = "fail: missing user name or password";

}

else if ( command.equals("login"))

{

if ( name != null || password != null )

{

switch( accounts.login(name, password) )

{

case AccountDatabase.NOT_REGISTERED:

message = "fail: no such user";

break;

case AccountDatabase.WRONG_PASSWORD:

message = "fail: incorrect password";

break;

case AccountDatabase.ALREADY_LOGGED_IN:

message = "fail: already logged in";

break;

default:

message = "success: user logged in";

break;

}

else

{

message = "fail: missing user name or password";

}

else if ( command.equals("logout"))

{

if ( name != null )

{

switch( accounts.logout(name) )

{

case AccountDatabase.ALREADY_LOGGED_OUT:

message = "fail: already logged out";

break;

case AccountDatabase.NOT_REGISTERED:

message = "fail: no such user";

break;

default:

message = "success: user logged out";

break;

}

else

{

message = "fail: missing user name";

}

if ( message != null )

{

System.out.println(message);

}

in.close();

}

Данная программа представляет собой типичный пример использования таблицы символов, согласно терминологии Coursera. Для доступа к учетным записям используется интерфейс Map, а для реализации самой базы данных учетных записей — объект типа TreeMap. Учетная запись пользователей реализована в виде одного элемента типа Map.entry, где имя пользователя — это ключ, а атрибуты учетной записи — пароль и флаг подключен/отключен — реализованы в виде отдельной структуры AccountInfo, которая является значением этого ключа.

Время работы	Выделено памяти
0.124	1 928 КБ

Ссылка на Ideone: https://ideone.com/3Y2W4z

Binary Heap (двоичная куча)

22/12/2015 by marchelaphil

В данном отчёте я напишу о структуре данных под названием куча (Heap), а точнее — о её разновидности.

Двоичная куча

Двоичная куча — структура данных, двоичное дерево, для которого выполнены три условия:

Значение в любой вершине не меньше чем значение в потомках
Расстояние до корня отличается не более чем на один уровень
Заполняется слева на право

Зафиксируем операции, которые будем проводить над кучей:

Достать максимальный элемент из кучи, не удаляя его
Добавить элемент в кучу
Создать кучу
Отсортировать массив путём превращения его в кучу, а кучи — в отсортированный массив
Узнать размер кучи
Удалить максимальный элемент из кучи

Описание методов

1. Восстановление свойства кучи

Каждый элемент помещается в конец кучи, потом становится на своё место, соответственно свойств кучи.

Сложность: [latex]O(\log(n))[/latex]

2. Возврат максимального элемента

Возвратить содержимое самой верхней вершины.

Сложность: [latex]O(1)[/latex]

3. Удаление максимального элемента

Меняются местами первая и последняя вершины, после чего последняя вершина запоминается и удаляется, а новая первая вершина проталкивается в кучу, согласно её свойствам.

Сложность: [latex]O(\log(n))[/latex]

4. Пирамидальная сортировка

Достаточно заметить, что в самую первую вершину кучи всегда (по крайней мере, по введённым свойствам) встаёт максимальный элемент. Если каждый раз удалять максимальный элемент — получим отсортированный массив.

Сложность: [latex]O(n\log(n))[/latex]

О реализации

Реализуется структура данных с абстрактным типом данных. Для хранения вершин будем использовать ArrayList. Для каждой вершины под номером [latex]i[/latex] её левый сын хранится в [latex]2*i+1[/latex] вершине, а правый — в [latex]2*i+2[/latex] вершине.

Класс содержит следующие методы:

Heap() — конструктор
shiftUp() — восходящее восстановление свойства кучи
shiftDown() — нисходящее восстановление свойства кучи
insert() — добавление элемента в кучу
delete() — удаление первой вершины
size() — размер кучи
isEmpty() — проверка на пустоту
toString() — преобразование в строку
max() — максимальный элемент
print() — вывод кучи на экран

Код

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Heap <T extends Comparable<T> > {
    //arraylist is much better than an array. There is no need to carry about a capacity.
    private ArrayList<T> items;
 
    //construct
    public Heap() {
        items = new ArrayList<T> ();   
    }
 
    //using shiftUp for insert. 
    private void shiftUp () {
        int k = items.size() - 1;
        while (k > 0){
            int curr = (k-1)/2;
            T Item = items.get(k);
            T Parent = items.get(curr);
            if (Item.compareTo(Parent) > 0){
                items.set(k, Parent);
                items.set(curr, Item);
                k = curr;
            }
            else break;
        }
    }
 
    //using shiftDown fo delete
    private void shiftDown() {
        int curr = 0; 
        int leftChild = 2*curr+1;
        while (leftChild < items.size()) {
            int max = leftChild;
            int rightChild = leftChild + 1;
            if (rightChild < items.size()) {
                if (items.get(rightChild).compareTo(items.get(1)) > 0) {
                    ++max;
                }
            }
            if (items.get(curr).compareTo(items.get(max)) < 0) {
                T tmp = items.get(curr);
                items.set(curr, items.get(max));
                items.set(max, tmp);
                curr = max;
                leftChild = 2*curr+1;
            }
            else break;
        }
    }
 
    public void insert(T item) {
        items.add(item);
        shiftUp();
    }
 
    public T delete() throws NoSuchElementException {
        if (items.size() == 0) {
            throw new NoSuchElementException();
        }
        if (items.size() == 1) return items.remove(0);
        T x = items.get(0);
        items.set(0, items.remove(items.size()-1));
        shiftDown();
        return x;
    }
 
    public int size() {
        return items.size();
    }
 
    public boolean isEmpty() {
        return items.isEmpty();
    }
 
    public String toString() {
        return items.toString();
    }
 
    public T max() {
        return items.get(0);
    }
    public void print() {
        for (int i = 0; i < items.size(); i++) {
            System.out.print(items.get(i).toString() + " ");
        }
        System.out.println();
    }
}
 
class Codechef {   
	public static void main (String[] args) {
		Heap <Integer> test = new Heap<Integer> ();
		test.insert(16);
		test.insert(9);
		test.insert(11);
		test.insert(10);
		test.insert(13);
		test.insert(31);
		test.insert(19);
		test.insert(2);
		test.insert(50);
		test.insert(23);
		test.print();
		//To kill some hares in the same time:
		//- isEmpty() works;
		// max() and toString() too
		// so does delete() => shiftDown() works;
		// heapsort :D
		for (;!test.isEmpty();) {
		    System.out.print(test.max().toString() + " ");
		    test.delete();
		}
	}
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

import java.util.*;

import java.lang.*;

import java.io.*;

class Heap <T extends Comparable<T> > {

//arraylist is much better than an array. There is no need to carry about a capacity.

private ArrayList<T> items;

//construct

public Heap() {

items = new ArrayList<T> ();

}

//using shiftUp for insert.

private void shiftUp () {

int k = items.size() - 1;

while (k > 0){

int curr = (k-1)/2;

T Item = items.get(k);

T Parent = items.get(curr);

if (Item.compareTo(Parent) > 0){

items.set(k, Parent);

items.set(curr, Item);

k = curr;

}

else break;

}

//using shiftDown fo delete

private void shiftDown() {

int curr = 0;

int leftChild = 2*curr+1;

while (leftChild < items.size()) {

int max = leftChild;

int rightChild = leftChild + 1;

if (rightChild < items.size()) {

if (items.get(rightChild).compareTo(items.get(1)) > 0) {

++max;

}

if (items.get(curr).compareTo(items.get(max)) < 0) {

T tmp = items.get(curr);

items.set(curr, items.get(max));

items.set(max, tmp);

curr = max;

leftChild = 2*curr+1;

}

else break;

}

public void insert(T item) {

items.add(item);

shiftUp();

}

public T delete() throws NoSuchElementException {

if (items.size() == 0) {

throw new NoSuchElementException();

}

if (items.size() == 1) return items.remove(0);

T x = items.get(0);

items.set(0, items.remove(items.size()-1));

shiftDown();

return x;

}

public int size() {

return items.size();

}

public boolean isEmpty() {

return items.isEmpty();

}

public String toString() {

return items.toString();

}

public T max() {

return items.get(0);

}

public void print() {

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

System.out.print(items.get(i).toString() + " ");

}

System.out.println();

}

class Codechef {

public static void main (String[] args) {

Heap <Integer> test = new Heap<Integer> ();

test.insert(16);

test.insert(9);

test.insert(11);

test.insert(10);

test.insert(13);

test.insert(31);

test.insert(19);

test.insert(2);

test.insert(50);

test.insert(23);

test.print();

//To kill some hares in the same time:

//- isEmpty() works;

// max() and toString() too

// so does delete() => shiftDown() works;

// heapsort :D

for (;!test.isEmpty();) {

System.out.print(test.max().toString() + " ");

test.delete();

}

Частотный словарь

21/12/2015 by Осецимский Анатолий

Определение понятия «частотный словарь» можно посмотреть в Википедии.

Реализовывалось на своем АВЛ-дереве.

Сначала надо распарсить строку на слова, которые удовлетворяют условию задачи 1. Потому, надо с помощью структуры данных как map реализовать дерево, поддерживающее ключ -> значение структуру. АВЛ-дерево в каком-то роде схоже с map, так что можно использовать его. Правда оно не имплемирует ни одного интерфейса, которые имплемирует map. Разбив текст на слова и добавив их в дерево с количеством их вхождений мы можем вывести частоту каждого из них. Для хранения общего количества слов используется переменная внутри словаря. Библиотека имеет один метод для получения результата — это по заданному слову выдать частоту его вхождения. Если необходимо вывести все слова в словаре, то тогда можно расширить класс АВЛ-дерева.

#include <iostream>
using namespace std;int main() {for( int i = 0; i < 10; i++ )
{
if( i % 2 == 0 )
{
cout << “Even” << endl;
}
else
{
cout << “Odd” << endl;
}
}
return 0;
}%EOF%

0 3 0.1111111111111111
10 1 0.037037037037037035
2 1 0.037037037037037035
Even 1 0.037037037037037035
Odd 1 0.037037037037037035
cout 2 0.07407407407407407
else 1 0.037037037037037035
endl 2 0.07407407407407407
for 1 0.037037037037037035
i 4 0.14814814814814814
if 1 0.037037037037037035
include 1 0.037037037037037035
int 2 0.07407407407407407
iostream 1 0.037037037037037035
main 1 0.037037037037037035
namespace 1 0.037037037037037035
return 1 0.037037037037037035
std 1 0.037037037037037035
using 1 0.037037037037037035

aaa for bbb aaa for if
%EOF%

aaa 2 0.3333333333333333
bbb 1 0.16666666666666666
for 2 0.3333333333333333
if 1 0.16666666666666666

import java.util.Scanner;
import java.util.StringTokenizer;

/**
 * Created by green on 20.12.15.
 */
class Vocabular{
    private AVL<String, Statistic> voc;
    int gloablCount = 0;
    public class Statistic{
        private int Count;
        private double Percent;
        Statistic(){
            Count = 1;
            Percent = 0;
        }
        public int getCount(){
            return Count;
        }
        public double getPercent(){
            return Percent;
        }

    }
    public Vocabular(String text, String delimiters){
        voc = new AVL();
        StringTokenizer st = new StringTokenizer(text, delimiters);
        while (st.hasMoreTokens()){
            String key = st.nextToken();
            Statistic value = voc.get(key);
            if (null != value){
                value.Count++;
                voc.add(key, value);
            }else{
                value = new Statistic();
                voc.add(key, value);
            }
            gloablCount++;
        }
        for(AVL<String, Statistic>.Node e = voc.getFirstNode(); e != null; e = e.next()){
            e.value.Percent = (double)e.value.Count/gloablCount;
        }
    }

    public AVL<String, Statistic>.Node getFirstNode(){
        return voc.getFirstNode();
    }

    public double getValue(String key){
        Statistic v = voc.get(key);
        if(v == null) return 0;
        else return v.Percent;
    }
}



public class Vocabulary {
    public static void main(String[] args){
        String text = "";
        Scanner in = new Scanner(System.in);
        for(;;){
            if(!in.hasNextLine()) break;
            String inputLine = in.nextLine();
            if(inputLine == null || inputLine.equals("%EOF%")) break;
            text = text + inputLine + "\n";
        }
        in.close();
        if(text.isEmpty()){
            System.out.println("*** Empty text ****");
            return;
        }
        Vocabular voc = new Vocabular(text, " ?.,;:-+\n\t{}[]=()<>*&%$#@\"\'“”`~!");
        for(AVL<String, Vocabular.Statistic>.Node e = voc.getFirstNode(); e != null; e = e.next()){
            System.out.println(e.key+" "+e.value.getCount()+" "+e.value.getPercent());
        }
    }
}

import java.util.Scanner;

import java.util.StringTokenizer;

/**

* Created by green on 20.12.15.

class Vocabular{

private AVL<String, Statistic> voc;

int gloablCount = 0;

public class Statistic{

private int Count;

private double Percent;

Statistic(){

Count = 1;

Percent = 0;

}

public int getCount(){

return Count;

}

public double getPercent(){

return Percent;

}

public Vocabular(String text, String delimiters){

voc = new AVL();

StringTokenizer st = new StringTokenizer(text, delimiters);

while (st.hasMoreTokens()){

String key = st.nextToken();

Statistic value = voc.get(key);

if (null != value){

value.Count++;

voc.add(key, value);

}else{

value = new Statistic();

voc.add(key, value);

}

gloablCount++;

}

for(AVL<String, Statistic>.Node e = voc.getFirstNode(); e != null; e = e.next()){

e.value.Percent = (double)e.value.Count/gloablCount;

}

public AVL<String, Statistic>.Node getFirstNode(){

return voc.getFirstNode();

}

public double getValue(String key){

Statistic v = voc.get(key);

if(v == null) return 0;

else return v.Percent;

}

public class Vocabulary {

public static void main(String[] args){

String text = "";

Scanner in = new Scanner(System.in);

for(;;){

if(!in.hasNextLine()) break;

String inputLine = in.nextLine();

if(inputLine == null || inputLine.equals("%EOF%")) break;

text = text + inputLine + "\n";

}

in.close();

if(text.isEmpty()){

System.out.println("*** Empty text ****");

return;

}

Vocabular voc = new Vocabular(text, " ?.,;:-+\n\t{}[]=()<>*&%$#@\"\'“”`~!");

for(AVL<String, Vocabular.Statistic>.Node e = voc.getFirstNode(); e != null; e = e.next()){

System.out.println(e.key+" "+e.value.getCount()+" "+e.value.getPercent());

}

Ссылка на ideone.

Обратная польская запись

20/12/2015 by Осецимский Анатолий

Что такое обратная польская запись можно прочитать в Википедии.

Использовался свой стек, выложенный ранее тут.

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

Лексемы по сути те же самые, только нет ни слова про функции. Для вычисления строки была сложность в нахождении «числовых значений». Для это бралась подстрока данной строки от начала числа до пробела после него.

15 * -(3 - 4)

1	15 * -(3 - 4)

15 3 4 - u *

1	15 3 4 - u *

15

92/10

92/10

92 10 /

92 10 /

9

2+2-2*2/2

2+2-2*2/2

2 2 + 2 2 * 2 / -

1	2 2 + 2 2 * 2 / -

2

import java.util.Scanner;
import java.util.StringTokenizer;

/**
 * Created by green on 20.12.15.
 */
class Parser{
        private String operators = "u+-*/";
        private String delimiters = operators + "( )";
        public boolean correct = true;
        private boolean isOperator(String x){
            if(x.length() != 1) return false;
            for(int i = 0; i < operators.length(); i++){
                if(x.charAt(0) == operators.charAt(i)) return true;
            }
            return false;
        }
        private boolean isDelimiter(String x){
            if(x.length() != 1) return false;
            for(int i = 0; i < delimiters.length(); i++){
                if(x.charAt(0) == delimiters.charAt(i)) return true;
            }
            return false;
        }
        private int priority(String x) {
            if (x.equals("(")) return 1;
            if (x.equals("+") || x.equals("-")) return 2;
            if (x.equals("*") || x.equals("/")) return 3;
            return 4;
        }
        public String parse(String infix) {
            String postfix = "";
            steck stack = new steck();
            StringTokenizer tokenizer = new StringTokenizer(infix, delimiters, true);
            String prev = "", curr = "";
            while (tokenizer.hasMoreTokens()) {
                curr = tokenizer.nextToken();
                if (!tokenizer.hasMoreTokens() && isOperator(curr)) {
                    postfix = ("Некорректное выражение.");
                    correct = false;
                    return postfix;
                }
                if (curr.equals(" ")) continue;
                if (isDelimiter(curr)) {
                    if (curr.equals("(")) stack.push(curr);
                    else if (curr.equals(")")) {
                        while (!stack.peek().equals("(")) {
                            postfix += stack.pop().toString() + " ";
                            if (stack.isEmpty()) {
                                postfix = ("Скобки не согласованы.");
                                correct = false;
                                return postfix;
                            }
                        }
                        stack.pop();
                    }else {
                        if (curr.equals("-") && (prev.equals("") || (isDelimiter(prev)  && !prev.equals(")")))) {
                            curr = "u";
                        }else{
                            while (!stack.isEmpty() && (priority(curr) <= priority(stack.peek().toString()))) {
                                postfix += stack.pop().toString()  + " ";
                            }

                        }
                        stack.push(curr);
                    }

                }else {
                    postfix += curr + " ";
                }
                prev = curr;
            }
            while (!stack.isEmpty()) {
                if (isOperator(stack.peek().toString())) postfix += stack.pop().toString() + " ";
                else {
                    postfix = "Скобки не согласованы.";
                    correct = false;
                    return postfix;
                }
            }
            return postfix;
        }
    public int calc(String postfix) {
        if(!correct) return 0;
        steck stack = new steck();
        for (int i = 0; i < postfix.length() ; i++) {
            if(postfix.charAt(i) == ' ') continue;
            if (postfix.charAt(i) == '+') stack.push(Integer.valueOf(stack.pop().toString()) + Integer.valueOf(stack.pop().toString()));
            else if (postfix.charAt(i) == '-') {
                int b = Integer.valueOf(stack.pop().toString()), a = Integer.valueOf(stack.pop().toString());
                stack.push(a - b);
            }
            else if (postfix.charAt(i) == '*') stack.push(Integer.valueOf(stack.pop().toString()) * Integer.valueOf(stack.pop().toString()));
            else if (postfix.charAt(i) == '/') {
                int b = Integer.valueOf(stack.pop().toString()), a = Integer.valueOf(stack.pop().toString());
                stack.push(a / b);
            }
            else if (postfix.charAt(i) == 'u') stack.push(-Integer.valueOf(stack.pop().toString()));
            else{
                int g = postfix.indexOf(' ',i);
                stack.push(Integer.valueOf(postfix.substring(i, g)));
                i = g;
            }
        }
        return Integer.valueOf(stack.pop().toString());
    }
}

public class postfix {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = "15 * -(3 - 4)";
        Parser x = new Parser();
        s = x.parse(s);
        if(x.correct){
            System.out.println(s);
            System.out.println(x.calc(s));
        }else{
            System.out.println("Ошибка:"+s);
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

import java.util.Scanner;

import java.util.StringTokenizer;

/**

* Created by green on 20.12.15.

class Parser{

private String operators = "u+-*/";

private String delimiters = operators + "( )";

public boolean correct = true;

private boolean isOperator(String x){

if(x.length() != 1) return false;

for(int i = 0; i < operators.length(); i++){

if(x.charAt(0) == operators.charAt(i)) return true;

}

return false;

}

private boolean isDelimiter(String x){

if(x.length() != 1) return false;

for(int i = 0; i < delimiters.length(); i++){

if(x.charAt(0) == delimiters.charAt(i)) return true;

}

return false;

}

private int priority(String x) {

if (x.equals("(")) return 1;

if (x.equals("+") || x.equals("-")) return 2;

if (x.equals("*") || x.equals("/")) return 3;

return 4;

}

public String parse(String infix) {

String postfix = "";

steck stack = new steck();

StringTokenizer tokenizer = new StringTokenizer(infix, delimiters, true);

String prev = "", curr = "";

while (tokenizer.hasMoreTokens()) {

curr = tokenizer.nextToken();

if (!tokenizer.hasMoreTokens() && isOperator(curr)) {

postfix = ("Некорректное выражение.");

correct = false;

return postfix;

}

if (curr.equals(" ")) continue;

if (isDelimiter(curr)) {

if (curr.equals("(")) stack.push(curr);

else if (curr.equals(")")) {

while (!stack.peek().equals("(")) {

postfix += stack.pop().toString() + " ";

if (stack.isEmpty()) {

postfix = ("Скобки не согласованы.");

correct = false;

return postfix;

}

stack.pop();

}else {

if (curr.equals("-") && (prev.equals("") || (isDelimiter(prev) && !prev.equals(")")))) {

curr = "u";

}else{

while (!stack.isEmpty() && (priority(curr) <= priority(stack.peek().toString()))) {

postfix += stack.pop().toString() + " ";

}

stack.push(curr);

}

}else {

postfix += curr + " ";

}

prev = curr;

}

while (!stack.isEmpty()) {

if (isOperator(stack.peek().toString())) postfix += stack.pop().toString() + " ";

else {

postfix = "Скобки не согласованы.";

correct = false;

return postfix;

}

return postfix;

}

public int calc(String postfix) {

if(!correct) return 0;

steck stack = new steck();

for (int i = 0; i < postfix.length() ; i++) {

if(postfix.charAt(i) == ' ') continue;

if (postfix.charAt(i) == '+') stack.push(Integer.valueOf(stack.pop().toString()) + Integer.valueOf(stack.pop().toString()));

else if (postfix.charAt(i) == '-') {

int b = Integer.valueOf(stack.pop().toString()), a = Integer.valueOf(stack.pop().toString());

stack.push(a - b);

}

else if (postfix.charAt(i) == '*') stack.push(Integer.valueOf(stack.pop().toString()) * Integer.valueOf(stack.pop().toString()));

else if (postfix.charAt(i) == '/') {

int b = Integer.valueOf(stack.pop().toString()), a = Integer.valueOf(stack.pop().toString());

stack.push(a / b);

}

else if (postfix.charAt(i) == 'u') stack.push(-Integer.valueOf(stack.pop().toString()));

else{

int g = postfix.indexOf(' ',i);

stack.push(Integer.valueOf(postfix.substring(i, g)));

i = g;

}

return Integer.valueOf(stack.pop().toString());

}

public class postfix {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

String s = "15 * -(3 - 4)";

Parser x = new Parser();

s = x.parse(s);

if(x.correct){

System.out.println(s);

System.out.println(x.calc(s));

}else{

System.out.println("Ошибка:"+s);

}

Ссылка на ideone.

Стек v.Java

20/12/2015 by Осецимский Анатолий

Stack test = new Stack(4);

System.out.println(test.isEmpty());

test.push(12);

System.out.println(test.isEmpty());

System.out.println(test.peek());

test.push(13);

test.push(14);

test.push(15);

test.push(16);

test.push(17);

test.push(‘(‘);

System.out.println(test.size());

System.out.println(test.peek().equals(‘(‘));

test.pop();

System.out.println(test.peek());

test.pop();

System.out.println(test.peek());

test.pop();

System.out.println(test.peek());

test.pop();

System.out.println(test.peek());

test.pop();

System.out.println(test.peek());

System.out.println(test.isEmpty());

test.pop();

System.out.println(test.peek());

test.pop();

System.out.println(test.isEmpty());

true

false

true

false

true

Что такое стек прекрасно расскажет Википедия.

Реализация динамического стека. Есть приватная функция resize, которая меняет размер массива, выделяемого под стек. Массив копируется в новый с помощью Java’вского копирования массивов.

Есть тестовый вывод, для проверки корректности всех методов.

/**
 * Created by green on 19.12.15.
 */
class Stack {
    private int size;
    private Object[] date;
    private int capacity;
    public Stack(){
        date = new Object[2];
        capacity = 2;
    }
    public Stack(int x){
        date = new Object[x];;
        capacity = x;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    private void resize(int x){
        Object[] newDate = new Object[x];
        System.arraycopy(date, 0, newDate, 0, size);
        date = null;
        date = newDate;
    }

    public void push(Object x){
        if(size == capacity){
            resize(2*capacity);
        }
        date[size++] = x;
    }

    public Object pop(){
        if(isEmpty()){
            return null;
        }
        if(size < capacity/2){
            resize(capacity/2);
        }
        Object temp = date[size -1];
        size = size -1;
        return temp;
    }

    public Object peek(){
        if(isEmpty()) return null;
        return date[size-1];
    }

    public void clear(){
        size = 0;
    }

    public int size(){
        return size;
    }
    public int getCapacity(){
        return size;
    }
}

public class task {
    public static void main(String[] args) {
        Stack test = new Stack(4);
        System.out.println(test.isEmpty());
        test.push(12);
        System.out.println(test.isEmpty());
        System.out.println(test.peek());
        test.push(13);
        test.push(14);
        test.push(15);
        test.push(16);
        test.push(17);
        test.push('(');
        System.out.println(test.size());
        System.out.println(test.peek().equals('('));
        test.pop();
        System.out.println(test.peek());
        test.pop();
        System.out.println(test.peek());
        test.pop();
        System.out.println(test.peek());
        test.pop();
        System.out.println(test.peek());
        test.pop();
        System.out.println(test.peek());
        System.out.println(test.isEmpty());
        test.pop();
        System.out.println(test.peek());
        test.pop();
        System.out.println(test.isEmpty());
    }
}

/**

* Created by green on 19.12.15.

class Stack {

private int size;

private Object[] date;

private int capacity;

public Stack(){

date = new Object[2];

capacity = 2;

}

public Stack(int x){

date = new Object[x];;

capacity = x;

}

public boolean isEmpty(){

return size == 0;

}

private void resize(int x){

Object[] newDate = new Object[x];

System.arraycopy(date, 0, newDate, 0, size);

date = null;

date = newDate;

}

public void push(Object x){

if(size == capacity){

resize(2*capacity);

}

date[size++] = x;

}

public Object pop(){

if(isEmpty()){

return null;

}

if(size < capacity/2){

resize(capacity/2);

}

Object temp = date[size -1];

size = size -1;

return temp;

}

public Object peek(){

if(isEmpty()) return null;

return date[size-1];

}

public void clear(){

size = 0;

}

public int size(){

return size;

}

public int getCapacity(){

return size;

}

public class task {

public static void main(String[] args) {

Stack test = new Stack(4);

System.out.println(test.isEmpty());

test.push(12);

System.out.println(test.isEmpty());

System.out.println(test.peek());

test.push(13);

test.push(14);

test.push(15);

test.push(16);

test.push(17);

test.push('(');

System.out.println(test.size());

System.out.println(test.peek().equals('('));

test.pop();

System.out.println(test.peek());

test.pop();

System.out.println(test.peek());

test.pop();

System.out.println(test.peek());

test.pop();

System.out.println(test.peek());

test.pop();

System.out.println(test.peek());

System.out.println(test.isEmpty());

test.pop();

System.out.println(test.peek());

test.pop();

System.out.println(test.isEmpty());

}

Ссылка на ideone.

АВЛ-дерево

20/12/2015 by Осецимский Анатолий

Описание АВЛ-дерева вы можете прочитать в Википедии.

Здесь представлен код реализации рекурсивного АВЛ-дерева. Отличается от обычно бинарного дерева тем, что у узлов есть высота и показатель балансировки. Балансировка может меняться при добавлении или удалении, и восстанавливается с помощью малого левого(правого), или большого левого(правого) поворотов. Как это выглядит можно увидеть в той же Википедии.

Показатель балансировки подсчитывается специальной функцией, как и показатель высоты.

Для возможности бегать по узлам дерева, есть приватные функция getHigherNode, getLowerNode. К которым есть доступ у узлов. К примеру мы в самой левой вершине дерева, либо мы лист, либо у нас есть правое поддерево. Если мы лист, то надо вернуть просто нашего предка. Если же есть правое поддерево. То надо вывести следующую вершину справа. Мы попали в эту вершину. Мы снова либо лист, либо есть правое поддерево, либо есть левое поддерево, либо сразу оба. Если мы лист, то нам надо подняться вверх по дереву, пока мы являемся правым сыном нашего предка, как только мы попадем в наш первоначальный самый маленький узел, мы перестаем быть правым сыном, значит нам пора остановиться, и вернуть отца самого маленького узла. Если же есть только правое поддерево(вернулись к моменту, где мы правый узел от самого маленького), то спускаемся снова вправо и имеем те же ситуации. Если же есть только левое поддерево, то заходим в него и действуем по тем же правилам. Если есть оба, то сначала пойдем в левое поддерево, после того, как мы там побываем и вернемся к узлу, нам надо будет продолжить обходить правое поддерево.

Попробуйте данный алгоритм действия, для этого дерева.

Определите следующий элемент для узла 0001.
Определите следующий элемент для узла 0003.
Определите следующий элемент для узла 0004.
Определите следующий элемент для узла 0005.
Определите следующий элемент для узла 0007, зная, что предок корня — это null.

Дерево

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

/**
 * Created by green on 19.12.15.
 */

class AVL <Key extends Comparable<Key>, Value> {
    public class Node {
        private int h;
        private int balance;
        Key key;
        Value value;
        private Node left, right, father;
        public Node (Key key, Value value, Node father) {
            this.key = key;
            this.value = value;
            this.left = this.right = null;
            this.father = father;
            this.h = 1;
            this.balance = 0;
        }
        public Node next(){
            return getHigherNode(this.key);
        }
        public Node previus(){
            return getLowerNode(this.key);
        }
    }

    private Node root;

    //Возвращает ближайщий узел , больше данного ключа, 
//если узла с таким ключом нет, то возвращает ближайщий узел, больше заданного ключа. 
//Если нет ближайщего большего позначению,чем заданый ключ, то возвращает null
    private Node getHigherNode(Key key) {
        Node p = root;
        while (p != null) {
            int cmp = key.compareTo(p.key);
            if (cmp < 0) {
                if (p.left != null)
                    p = p.left;
                else
                    return p;
            } else {
                if (p.right != null) {
                    p = p.right;
                } else {
                    Node father = p.father;
                    Node ch = p;
                    while (father != null && ch == father.right) {
                        ch = father;
                        father = father.father;
                    }
                    return father;
                }
            }
        }
        return null;
    }
    //Возвращает ближайщий узел , меньше данного ключа, 
//если узла с таким ключом нет, то возвращает ближайщий узел, меньше заданного ключа. 
//Если нет ближайщего большего позначению,чем заданый ключ, то возвращает null
    private Node getLowerNode(Key key) {
        Node p = root;
        while (p != null) {
            int cmp = key.compareTo(p.key);
            if (cmp > 0) {
                if (p.right != null)
                    p = p.right;
                else
                    return p;
            } else {
                if (p.left != null) {
                    p = p.left;
                } else {
                    Node father = p.father;
                    Node ch = p;
                    while (father != null && ch == father.left) {
                        ch = father;
                        father = father.father;
                    }
                    return father;
                }
            }
        }
        return null;
    }

    public Node getFirstNode(){
        return min(root);
    }

    public Node getLastNode(){
        return max(root);
    }

    private int height(Node x, Node y){
        if(x == null && y == null) return 0;
        else if(x == null) return y.h;
        else if(y == null) return x.h;
        else return Math.max(x.h, y.h);
    }

    private int balance(Node x, Node y){
        if(x == null && y == null) return 0;
        else if(x == null) return - y.h;
        else if(y == null) return x.h;
        else return x.h - y.h;
    }

    private Node add (Node node,Key key, Value value, Node father){
        if (node == null){
            Node newnode = new Node(key,value, father);
            return newnode;
        }
        int compareResult = key.compareTo(node.key);
        if (compareResult > 0){node.right = add(node.right, key, value, node); node.h = height(node.left, node.right) + 1;}
        else if(compareResult < 0){node.left = add(node.left, key, value, node); node.h = height(node.left, node.right) + 1;}
        else{
            node.value = value;
        }
        node.balance = balance(node.left, node.right);
        if(node.balance == -2){
            node = leftRotation(node);
        }else if(node.balance == 2){
            node = rightRotation(node);
        }
        return node;
    }

    private Node leftRotation(Node node) {
        if(node.right.right == null && node.right.left != null){
            node.right = rightRotation(node.right);
            node = leftRotation(node);
        }else if(node.right.left == null || node.right.left.h <= node.right.right.h){
            Node newnode = node.right;
            newnode.father = node.father;
            node.right = newnode.left;
            if(node.right != null)
                node.right.father = node;
            node.h = height(node.left, node.right)+1;
            node.father = newnode;
            node.balance = balance(node.left, node.right);
            newnode.left = node;
            node = newnode;
            node.balance = balance(node.left, node.right);
            node.h = height(node.left, node.right)+1;
        }else{
            node.right = rightRotation(node.right);
            node = leftRotation(node);
        }
        return node;
    }
    private Node rightRotation(Node node){
        if(node.left.right != null && node.left.left == null){
            node.left = leftRotation(node.left);
            node = rightRotation(node);
        }else if(node.left.right == null || node.left.right.h <= node.left.left.h){
            Node newnode = node.left;
            newnode.father = node.father;
            node.left = newnode.right;
            if(node.left != null)
                node.left.father = node;
            node.h = height(node.left, node.right)+1;
            node.father = newnode;
            node.balance = balance(node.left, node.right);
            newnode.right = node;
            node = newnode;
            node.balance = balance(node.left, node.right);
            node.h = height(node.left, node.right)+1;
        }else{
            node.left = leftRotation(node.left);
            node = rightRotation(node);
        }
        return node;
    }

    public void add(Key key, Value value) {
        root = add(root, key, value, null);
    }

    private Node delete(Node node, Key key){
        if(node == null) return null;
        int compareResult = key.compareTo(node.key);
        if(compareResult > 0){
            node.right = delete(node.right, key);
        }else if(compareResult < 0){
            node.left = delete(node.left, key);
        }else{
            if(node.right == null && node.left == null){
                node = null;
            }else if(node.right == null){
                node.left.father = node.father;
                node = node.left;
            }else if(node.left == null){
                node.right.father = node.father;
                node = node.right;
            }else{
                if(node.right.left == null){
                    node.right.left = node.left;
                    node.right.father = node.father;
                    node.right.father = node.father;
                    node.left.father = node.right;
                    node = node.right;
                }else{
                    Node res = min(node.right);
                    node.key = res.key;
                    node.value = res.value;
                    delete(node.right, node.key);
                }
            }
        }
        if(node != null) {
            node.h = height(node.left, node.right) + 1;
            node.balance = balance(node.left, node.right);
            if (node.balance == -2) {
                node = leftRotation(node);
            } else if (node.balance == 2) {
                node = rightRotation(node);
            }
        }
        return node;
    }

    public void delete(Key key) {
        root = delete(root, key);
    }

    public Key minKey(){
        return min(root).key;
    }

    public Key maxKey(){
        return max(root).key;
    }

    private Node min(Node node){
        if(node.left == null) return node;
        return min(node.left);
    }

    private Node max(Node node){
        if(node.right == null) return node;
        return min(node.right);
    }

    private Value get(Node node, Key key){
        if(node == null) return null;
        int compareResult = key.compareTo(node.key);
        if(compareResult == 0){
            return node.value;
        }else if(compareResult > 0){
            return get(node.right, key);
        }else{
            return get(node.left, key);
        }
    }

    public Value get(Key key) {
        return get(root, key);
    }

    private void print(Node node, int level) {
        if (node != null) {
            print(node.right,level+1);
            for (int i=0;i<level;i++) {
                System.out.print("\t");
            }
            System.out.println(node.key + "->" + node.value+" h="+node.h+" balance="+node.balance);
            print(node.left,level+1);
        }
    }

    public void print() {
        print(root,0);
    }

}

public class avl_tree {
    public static void main(String[] args){
        AVL<Integer, Integer> tree = new AVL<>();
        tree.add(10,10);
        tree.print();
        tree.add(11,11);
        tree.print();
        tree.add(15,12);
        tree.print();
        tree.add(13,12);
        tree.print();
        tree.add(16,12);
        tree.print();
        tree.add(12,12);
        tree.print();
        tree.add(3,2);
        tree.print();
        tree.add(1,1);
        tree.print();
        tree.add(0,1);
        tree.print();
        tree.add(2,1);
        tree.print();
        tree.delete(13);
        tree.print();
        tree.delete(10);
        tree.print();
        for(AVL.Node e = tree.getFirstNode(); e != null; e = e.next()){
            System.out.println(e.key);
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

/**

* Created by green on 19.12.15.

class AVL <Key extends Comparable<Key>, Value> {

public class Node {

private int h;

private int balance;

Key key;

Value value;

private Node left, right, father;

public Node (Key key, Value value, Node father) {

this.key = key;

this.value = value;

this.left = this.right = null;

this.father = father;

this.h = 1;

this.balance = 0;

}

public Node next(){

return getHigherNode(this.key);

}

public Node previus(){

return getLowerNode(this.key);

}

private Node root;

//Возвращает ближайщий узел , больше данного ключа,

//если узла с таким ключом нет, то возвращает ближайщий узел, больше заданного ключа.

//Если нет ближайщего большего позначению,чем заданый ключ, то возвращает null

private Node getHigherNode(Key key) {

Node p = root;

while (p != null) {

int cmp = key.compareTo(p.key);

if (cmp < 0) {

if (p.left != null)

p = p.left;

else

return p;

} else {

if (p.right != null) {

p = p.right;

} else {

Node father = p.father;

Node ch = p;

while (father != null && ch == father.right) {

ch = father;

father = father.father;

}

return father;

}

return null;

}

//Возвращает ближайщий узел , меньше данного ключа,

//если узла с таким ключом нет, то возвращает ближайщий узел, меньше заданного ключа.

//Если нет ближайщего большего позначению,чем заданый ключ, то возвращает null

private Node getLowerNode(Key key) {

Node p = root;

while (p != null) {

int cmp = key.compareTo(p.key);

if (cmp > 0) {

if (p.right != null)

p = p.right;

else

return p;

} else {

if (p.left != null) {

p = p.left;

} else {

Node father = p.father;

Node ch = p;

while (father != null && ch == father.left) {

ch = father;

father = father.father;

}

return father;

}

return null;

}

public Node getFirstNode(){

return min(root);

}

public Node getLastNode(){

return max(root);

}

private int height(Node x, Node y){

if(x == null && y == null) return 0;

else if(x == null) return y.h;

else if(y == null) return x.h;

else return Math.max(x.h, y.h);

}

private int balance(Node x, Node y){

if(x == null && y == null) return 0;

else if(x == null) return - y.h;

else if(y == null) return x.h;

else return x.h - y.h;

}

private Node add (Node node,Key key, Value value, Node father){

if (node == null){

Node newnode = new Node(key,value, father);

return newnode;

}

int compareResult = key.compareTo(node.key);

if (compareResult > 0){node.right = add(node.right, key, value, node); node.h = height(node.left, node.right) + 1;}

else if(compareResult < 0){node.left = add(node.left, key, value, node); node.h = height(node.left, node.right) + 1;}

else{

node.value = value;

}

node.balance = balance(node.left, node.right);

if(node.balance == -2){

node = leftRotation(node);

}else if(node.balance == 2){

node = rightRotation(node);

}

return node;

}

private Node leftRotation(Node node) {

if(node.right.right == null && node.right.left != null){

node.right = rightRotation(node.right);

node = leftRotation(node);

}else if(node.right.left == null || node.right.left.h <= node.right.right.h){

Node newnode = node.right;

newnode.father = node.father;

node.right = newnode.left;

if(node.right != null)

node.right.father = node;

node.h = height(node.left, node.right)+1;

node.father = newnode;

node.balance = balance(node.left, node.right);

newnode.left = node;

node = newnode;

node.balance = balance(node.left, node.right);

node.h = height(node.left, node.right)+1;

}else{

node.right = rightRotation(node.right);

node = leftRotation(node);

}

return node;

}

private Node rightRotation(Node node){

if(node.left.right != null && node.left.left == null){

node.left = leftRotation(node.left);

node = rightRotation(node);

}else if(node.left.right == null || node.left.right.h <= node.left.left.h){

Node newnode = node.left;

newnode.father = node.father;

node.left = newnode.right;

if(node.left != null)

node.left.father = node;

node.h = height(node.left, node.right)+1;

node.father = newnode;

node.balance = balance(node.left, node.right);

newnode.right = node;

node = newnode;

node.balance = balance(node.left, node.right);

node.h = height(node.left, node.right)+1;

}else{

node.left = leftRotation(node.left);

node = rightRotation(node);

}

return node;

}

public void add(Key key, Value value) {

root = add(root, key, value, null);

}

private Node delete(Node node, Key key){

if(node == null) return null;

int compareResult = key.compareTo(node.key);

if(compareResult > 0){

node.right = delete(node.right, key);

}else if(compareResult < 0){

node.left = delete(node.left, key);

}else{

if(node.right == null && node.left == null){

node = null;

}else if(node.right == null){

node.left.father = node.father;

node = node.left;

}else if(node.left == null){

node.right.father = node.father;

node = node.right;

}else{

if(node.right.left == null){

node.right.left = node.left;

node.right.father = node.father;

node.left.father = node.right;

node = node.right;

}else{

Node res = min(node.right);

node.key = res.key;

node.value = res.value;

delete(node.right, node.key);

}

if(node != null) {

node.h = height(node.left, node.right) + 1;

node.balance = balance(node.left, node.right);

if (node.balance == -2) {

node = leftRotation(node);

} else if (node.balance == 2) {

node = rightRotation(node);

}

return node;

}

public void delete(Key key) {

root = delete(root, key);

}

public Key minKey(){

return min(root).key;

}

public Key maxKey(){

return max(root).key;

}

private Node min(Node node){

if(node.left == null) return node;

return min(node.left);

}

private Node max(Node node){

if(node.right == null) return node;

return min(node.right);

}

private Value get(Node node, Key key){

if(node == null) return null;

int compareResult = key.compareTo(node.key);

if(compareResult == 0){

return node.value;

}else if(compareResult > 0){

return get(node.right, key);

}else{

return get(node.left, key);

}

public Value get(Key key) {

return get(root, key);

}

private void print(Node node, int level) {

if (node != null) {

print(node.right,level+1);

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

System.out.print("\t");

}

System.out.println(node.key + "->" + node.value+" h="+node.h+" balance="+node.balance);

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Category Archives: 8. Структуры данных

e-olymp 6125. Простая очередь

Входные данные

Выходные данные

Тесты

Код

Timus №2002

Timus 2002 by Tolia

BST – Двоичные деревья поиска

acm.timus.ru №2002. Тестовое задание

Условие

Исходные данные

Результат

Пример

Binary Heap (двоичная куча)

Двоичная куча

Описание методов

О реализации

Код

Частотный словарь

Обратная польская запись

Стек v.Java

АВЛ-дерево