ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Java [игнор отключен] [закрыт для гостей] / Всем привет! Помогите решить задание
6 сообщений из 6, страница 1 из 1
Всем привет! Помогите решить задание
    #40024856
angelinasok
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
angelinasok
Гость
Требуется реализовать структуру Красно-черное бинарное дерево поиска.
Выбрать корректный вариант реализации на языке Java.

1.
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
public class Container < Key extends java.lang.Comparable < Key > , Value > { 
    private Node root; 
    private class Node { 
        private Key key; 
        private Value val; 
        private Node left, right; 
        private int N; 
        public Node(Key key, Value val, int N) { 
            this.key = key; 
            this.val = val; 
            this.N = N; 
        } 
    } 
    public int size() { 
        return size(root); 
    } 
    private int size(Node x) { 
        if (x == null) 
            return 0; 
        else 
            return x.N; 
    } 
    public Value get(Key key) { 
        return get(root, key); 
    } 
    private Value get(Node x, Key key) { 
        if (x == null) 
            return null; 
        int cmp = key.compareTo(x.key); 
        if (cmp < 0) 
            return get(x.left, key); 
        else 
        if (cmp > 0) 
            return get(x.right, key); 
        else 
            return x.val; 
    } 
    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 
            x.val = val; 
        x.N = size(x.left) + size(x.right) + 1; 
        return x; 
    } 
}


2.
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
public class Container < Key extends java.lang.Comparable < Key > , Value > { 
    private Node root; 
    private class Node { 
        Key key; 
        Value val; 
        Node left, right; 
        I nt N; 
        boolean param; 
        Node(Key key, Value val, int N, boolean param) { 
            this.key = key; 
            this.val = val; 
            this.N = N; 
            this.param = param; 
        } 
    } 
    private boolean check(Node x) { 
        if (x == null) 
            return false; 
        return x.param == true; 
    } 
    Node rotateLeft(Node h) { 
        Node x = h.right; 
        h.right = x.left; 
        x.left = h; 
        x.param = h.param; 
        h.param = true; 
        x.N = h.N; 
        h.N = 1 + size(h.left) + size(h.right); 
        return x; 
    } 
    Node rotateRight(Node h) { 
        Node x = h.left; 
        h.left = x.right; 
        x.right = h; 
        x.param = h.param; 
        h.param = true; 
        x.N = h.N; 
        h.N = 1 + size(h.left) + size(h.right); 
        return x; 
    } 
    void flip(Node h) { 
        h.param = true; 
        h.left.param = false; 
        h.right.param = false; 
    } 
    private int size(Node x) { 
        if (x == null) 
            return 0; 
        else 
            return x.N; 
    } 
    public void put(Key key, Value val) { 
        root = put(root, key, val); 
        root.param = false; 
    } 
    private Node put(Node h, Key key, Value val) { 
        if (h == null) 
            return new Node(key, val, 1, true); 
        int cmp = key.compareTo(h.key); 
        if (cmp < 0) 
            h.left = put(h.left, key, val); 
        else 
        if (cmp > 0) 
            h.right = put(h.right, key, val); 
        else 
            h.val = val; 
        if (check(h.right) && !check(h.left)) 
            h = rotateLeft(h); 
        if (check(h.left) && check(h.left.left)) 
            h = rotateRight(h); 
        if (check(h.left) && check(h.right)) 
            flip(h); 
        h.N = size(h.left) + size(h.right) + 1; 
        return h; 
    } 
}


3.
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
public class Container < Key extends java.lang.Comparable < Key > , Value > { 
    private Key[] keys; 
    private Value[] vals; 
    private int N; 
    public Container(int capacity) { 
        keys = (Key[]) new java.lang.Comparable[capacity]; 
        vals = (Value[]) new Object[capacity]; 
    } 
    public int size() { 
        return N; 
    } 
    public Value get(Key key) { 
        if (vals.length == 0) 
            return null; 
        int i = rank(key); 
        if (i < N && keys[i].compareTo(key) == 0) 
            return vals[i]; 
        else 
            return null; 
    } 
    private int rank(Key key) { 
        int lo = 0, hi = N - 1; 
        while (lo <= hi) { 
            int mid = lo + (hi - lo) / 2; 
            int cmp = key.compareTo(keys[mid]); 
            if (cmp < 0) 
                hi = mid - 1; 
            else 
            if (cmp > 0) 
                lo = mid + 1; 
            else 
                return mid; 
        } 
        return lo; 
    } 
    public void put(Key key, Value val) { 
        int i = rank(key); 
        if (i < N && keys[i].compareTo(key) == 0) { 
            vals[i] = val; 
            return; 
        } 
        for (int j = N; j > i; j--) { 
            keys[j] = keys[j - 1]; 
            vals[j] = vals[j - 1]; 
        } 
        keys[i] = key; 
        vals[i] = val; 
        N++; 
    } 
}


1 2 3
...
Рейтинг: 0 / 0
05.12.2020, 15:17
| Ответить | Цитировать | Написать  
Всем привет! Помогите решить задание
    #40024861
chpasha
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
chpasha
Участник
хорошая попытка. за идею 5, за лабу - неуд
...
Рейтинг: 0 / 0
05.12.2020, 15:56
| Ответить | Цитировать | Написать  
Всем привет! Помогите решить задание
    #40025121
Фотография Valentin Kolesnikov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Valentin Kolesnikov
Участник
Нашёл статью.

http://javist.ru/krasnoe-derevo-chernyj-osushhestvleniya-v-java/

Хорошего вам дня!
...
Рейтинг: 0 / 0
07.12.2020, 01:32
| Ответить | Цитировать | Написать  
Всем привет! Помогите решить задание
    #40025440
Андрей Панфилов
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Андрей Панфилов
Участник
Zzz79
Код: java
1.
private Node left, right;


вот за это сразу нах с профессии сволочь!
Чего бы это вдруг?
...
Рейтинг: 0 / 0
08.12.2020, 00:08
| Ответить | Цитировать | Написать  
Всем привет! Помогите решить задание
    #40025569
PetroNotC Sharp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
PetroNotC Sharp
Участник
Zzz79
Код: java
1.
private Node left, right;



вот за это сразу нах с профессии сволочь!


Выпил - не лезь за клаву!
...
Рейтинг: 0 / 0
08.12.2020, 13:34
| Ответить | Цитировать | Написать  
Всем привет! Помогите решить задание
    #40025576
Андрей Панфилов
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Андрей Панфилов
Участник
Zzz79
Андрей Панфилов
пропущено...
Чего бы это вдруг?

c того,что потом эту срань кто то будет поддержтивать
какую именно срань?
...
Рейтинг: 0 / 0
08.12.2020, 13:46
| Ответить | Цитировать | Написать  
6 сообщений из 6, страница 1 из 1
Форумы / Java [игнор отключен] [закрыт для гостей] / Всем привет! Помогите решить задание
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]