CodeGym /Courses /Java Collections /Tasks | Level 6 | Lesson 8

Tasks | Level 6 | Lesson 8

Java Collections

Level 6 , Lesson 8

Available

Previous Previous lesson

Next Next lesson

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......