Lessons
Start
Start learning
CodeGym /Courses /Java Collections /Tasks | Level 6 | Lesson 8

Tasks | Level 6 | Lesson 8

Java Collections
Level 6 , Lesson 8
Available
32
Task
Java Collections, level 6, lesson 8
Locked
Understanding red-black trees
You are given an implementation of a red-black tree. But some methods are broken. Analyze the code and fix the errors. The main method is not tested. All of the modifiers are correct. Don't change variable or method names.
Open
Java university
16
Task
Java Collections, level 6, lesson 8
Locked
Using TreeSet
The first parameter is the file name: file1. file1 only contains Latin letters, spaces, punctuation, dashes, and carriage returns. Sort the letters alphabetically and display the first 5 unique letters on a single line without separators.
Open
16
Task
Java Collections, level 6, lesson 8
Locked
How many potential friends does a person have?
Today we'll analyze some functionality of social networks. How do social networks know who to suggest as friends you might know? This task is easily solved using graphs.
Open
Comments (8)
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION
Lisa Level 41
19 January 2022
The explanation on trees was, euphemistically speaking, compact. In any case, I think it was too little to understand RB trees and to solve the above red task. To understand RB trees you have to know that they are actually 2-3-4 trees converted back to binary trees. The insertion and traversing then works like AVL trees (single and double rotation and in, pre, post and level order traversal). So you have to read up on trees and their implementation in general and then in particular binary trees, AVL trees, 2-3-4 trees and finally you end up with RB trees. In order not to have difficulties with the implementation, you start with something easy like a stack. After that you move on to queues, which already cause some difficulties. Next you write your own implementation of lists (linked and based on an array). If you want you can also implement your own hashset. This is very interesting and no, the CC big tasks to sets do not count here. They are based on existing collections. Then you are ready to implement the first tree and move on to a binary search tree and finally AVL trees. That's a huge lot to learn and that last site doesn't reflect that. This is an insane amount to know and the CC explanations on this are extremely sparse, not to mention somewhat ridiculous. By the way, I did the work and wrote implementations for everything mentioned up to the AVL tree (so no 2-3-4 or RB-trees). Don't let anyone say that I'm just babbling. Oh, and it doesn't hurt to have looked at (and implemented) search algorithms beforehand, too (and for that maybe repeat recursive methods). Especially the binary search. Complexities then also come into play. Trees are a really extensive topic and the article on this is even too little to get a first impression. The link to Wikipedia doesn't help either. Btw, at the university, these above mentioned topics are taught within half a year.
Lisa Level 41
21 January 2022
Maybe it's of help. That's code that allows to traverse the tree and output node values and color 

    /* 
        to test the RB-Tree
        these methods allow traversing the tree and outputting the node values and colors
     */
    public enum Order {
        INORDER, PREODER, POSTORDER, LEVELORDER;
    }
    
    private void printInorder(Node n) {
        if (n != EMPTY) {
            printInorder(n.left);
            System.out.println(n);
            printInorder(n.right);
        }
    }

    public void printPreorder(Node n) {
        if (n != EMPTY) {
            System.out.println(n);
            printPreorder(n.left);
            printPreorder(n.right);
        }
    }
    private void printPostorder(Node n) {
        if (n != EMPTY) {
            printPostorder(n.left);
            printPostorder(n.right);
            System.out.println(n);
        }
    }

    private void printLevelorder(Queue<Node> q) {
        while (! q.isEmpty()) {
            Node n = q.remove();
            if (n.left != EMPTY)
                q.add(n.left);
            if (n.right != EMPTY)
                q.add(n.right);
            System.out.println(n);
        }
    }

    public void traverse(Order strategy) {
        switch (strategy) {
            case INORDER:
                printInorder(header.right);
                break;
            case PREODER:
                printPreorder(header.right);
                break;
            case POSTORDER:
                printPostorder(header.right);
                break;
            case LEVELORDER:
                Queue<Node> queue = new ArrayDeque<>();
                queue.add(header.right);
                printLevelorder(queue);
                break;
        }
    }
    //end test code
Lisa Level 41
21 January 2022
To output nodes we will need to override to Node class' toString method 

        @Override
        public String toString() {
            return "{element: " + element + ", color: " + color + "}";
        }
and finally a sample call for the main method 

        RedBlackTree rbt = new RedBlackTree();
        rbt.insert(5);
        rbt.insert(4);
        rbt.insert(9);
        rbt.insert(3);
        rbt.insert(1);
        rbt.insert(7);
        System.out.println("Inorder:");
        rbt.traverse(RedBlackTree.Order.INORDER); // sorted output
        System.out.println("\nLevelorder:");
        rbt.traverse(RedBlackTree.Order.LEVELORDER);
cute potato Level 46, Poland, Poland
27 March 2023
Thank u, Lisa❤️
yz Level 37, Jakarta, Indonesia
13 April 2020
guys 2nd task want from u from each letter show one ex: aaabbbcc -> a,b,c; it doesnt want u to find which letter is unique like EX: accabca -> b;
Justin Smith Level 41, Greenfield, USA, United States
14 December 2022
I wish I had seen this comment before struggling for a long time on that task.
Senned Level 41, Azov, Russia
19 December 2019
Task about Friends: Friends of index (4) - 0, 1, 3 there is deep=1 Friends of 0 - 1, 4, 5. there is deep=2 Friends of 1 - 0, 2, 4. there is deep=2 Friends of 3 - 4, 7. there is deep=2 Friends and potential friends for index :0, 1, 2, 3, 5, 7 potential friends for index : 2, 5, 7 In conditions description of int deep - seems wrong, with that it will be needs find friends of 0,1 and 3 too.
季军 Level 38, Shanghai, China
21 August 2019
In the task for TreeSet, don't pass any comparator to the constructor, or the validator cannot recognize the set......