Fabrice E Iyolo

Turn coke into code


Radix trie - a simple way to sort binary values

A radix tree (also patricia trie or radix trie or compact prefix tree) is a space-optimized trie data structure where each node with only one child is merged with its child. The result is that every internal node has at least two children. You can see more about the redix tree here.


Build the radix tree

We build our radix Tree by inserting different values in the same time than building the tree. If a value is bigger than the depth of the tree, we keep adding nodes until the tree will be able to store the value.
In our example, we're dealing with binaries (1 or 0), so it's not necessary to store values at the nodes, we just add a boolean property shaded in the node class. Shaded is true for 1 and false for 0. So we just shade the node with values. The way taken to reach a shaded node determine the value for this node, it means each time we take left, we add 0 in the value and each time we go left, we add 1 to the value.

The algorithm do some check on each bit of all strings. This is done in O(n) time since the cost of inserting a string is proportional to the length of the string and the lengths of all string sum up to n.

Here is the java code, to insert values and of course building the tree in the same time

 public static void insert(Node mynode, String key, int depth){
        Node x = new Node();
        if(depth > key.length()){
            System.out.println("someting is wrong with this prgram");
        }

        if(key.length()-1 == depth){
            if (key.charAt(depth) == '0'){
                if (mynode.leftchild == null){
                    mynode.leftchild = x;
                    mynode.leftchild.parent = mynode;
                    mynode.leftchild.shaded = true;
                }else{
                    mynode.leftchild.shaded = true;
                }
            }else{
                if(mynode.rightchild == null){
                    mynode.rightchild = x;
                    mynode.rightchild.parent =mynode;
                    mynode.rightchild.shaded = true;
                }else{
                    mynode.rightchild.shaded = true;
                }
            }
        }else{
            if (key.length() > depth && key.charAt(depth) == '0'){
                if (mynode.leftchild == null){
                    mynode.leftchild  = x;
                    insert(mynode.leftchild, key, depth+1);
                }else{
                    insert(mynode.leftchild, key, depth+1);
                }
            }else{
                if(key.length() > depth && key.charAt(depth) == '1'){
                    if(mynode.rightchild == null){
                        mynode.rightchild = x;
                        insert(mynode.rightchild, key, depth+1);
                    }else{
                        insert(mynode.rightchild, key, depth+1);
                    }
                }
            }
        }
    }

This method instantiate a Node object each time it's called. He is the abstract definition of this object.

public class Node {

    boolean shaded;
    Node leftchild;
    Node rightchild;
    Node parent;

    public Node()
    {
        shaded = false;
        leftchild = null;
        rightchild = null;
    }
}

Sort the values

We can using a preorder traversal (root, left, right), of the tree to print the string in sorted order. It will take in O(n) time as well since the number of nodes in the tree is at most n +1, a string of length i corresponds to i nodes plus the root, and lengths of all strings sum to n. It is just like INORDER-TREE-WALK. It prints the current node and calls itself recursively on the left and right sub-trees), so it takes time proportional to the number of nodes in the tree. The number of nodes is at most 1 plus the sum (n).

Here is the function pre_order_walk which started by printing the root, then left child and the right child, recursively.

    public static void pre_order_walk(Node root){
        String currString = "";
        pre_order_print(root, currString);
    }

    public static void pre_order_print(Node root, String currString){
        if (root == null){
            return;
        }else if(currString.equals("")){
            pre_order_print(root.leftchild, currString + "0");
            pre_order_print(root.rightchild, currString + "1");
        }else if(root.shaded){
            System.out.println(currString);
            pre_order_print(root.leftchild, currString + "0");
            pre_order_print(root.rightchild, currString + "1");
        }else{
            pre_order_print(root.leftchild, currString + "0");
            pre_order_print(root.rightchild, currString + "1");
        }
    }

These methods are implemented in  a Netbeans project, with a GUI,  along with Young tableaus. Download it here, and play with it.

A propos

Je suis techniquement fort, expérimenté, pratique et curieux. Je travaille depuis plus de 15 ans dans le domaine de technologies de l'information. Je suis passionné de technologie et de ses applications. J'ai des connaissances et des compétences étendues et approfondies dans les domaines de la cloud computing, des outils, de l'automatisation et de la business intelligence.

Contact