package nowe_algo_4;

class BinarySearchTree {
    long comp=0;
    long mod=0;
static class Node {
     String key;
     Node left, right,parent;

     public Node(String item) {
         key = item;
         left = right = parent = null;
     }

 }
static Node newNode(String data)
{
    Node temp = new Node("");

    temp.key = data;

    temp.left = null;
    temp.right = null;

    return temp;
}
static Node root;
 BinarySearchTree() {
   root = null;
 }
  Node insert2(String key)
 {
     Node newnode = newNode(key);

     Node x = root;

     Node y = null;

     while (root != null) {
         comp++;
         y = root;
         comp++;
         if (key.compareTo(root.key) < 0) {
             root = root.left;
             mod++;
         }
         else{
             root = root.right;
             mod++;
         }
     }
     comp++;
     if (root == null) {
         root = newnode;
         mod++;
     }

     else if (key.compareTo(root.key) < 0) {
         comp++;
         root.left = newnode;
     }


     else{
         comp++;
         mod++;
         root.right = newnode;
     }

     return root;
 }
 void insert(String key) {
     char insert = key.charAt(key.length() - 1);
     if (!((insert >= 'a' && insert <= 'z') || (insert >= 'A' && insert <= 'Z'))) {
         key = key.substring(0, key.length() - 1);
     }
     insert = key.charAt(0);
     if (!((insert >= 'a' && insert <= 'z') || (insert >= 'A' && insert <= 'Z'))) {
         key = key.substring(1);
     }
    root = insertRec(root, key);
 }
 Node insertRec(Node root, String key) {
     comp++;
     if (root == null) {
         mod++;
         root = new Node(key);
         return root;
     }
     else{

         Node temp=null;
         comp++;
     if (key.compareTo(root.key)<0){
         temp = insertRec(root.left, key);
         mod++;;
         root.left=temp;
         temp.parent=root;
     }
     else if (key.compareTo(root.key)>0){
         comp++;
         temp = insertRec(root.right, key);
         mod++;
         root.right=temp;
         temp.parent=root;
     }
     return root;
     }
 }

 void inorder()  {
    inorderRec(root);
 }
 void inorderRec(Node root) {
     if (root != null) {
         inorderRec(root.left);
         System.out.println(root.key);
         inorderRec(root.right);
     }
 }
 void deleteKey(String key)
 {
     root = deleteRec(root, key);
 }
 Node deleteRec(Node root, String key)
 {

     comp++;
     if (root == null){
         mod++;
         return root;

     }
     if (key.compareTo(root.key)<0){
         comp++;
         //mod++;
         root.left = deleteRec(root.left, key);
     }
     else if (key.compareTo(root.key)>0){
         comp+=2;
        // mod++;
         root.right = deleteRec(root.right, key);
     }
     else
     {
         comp++;
         if (root.left == null){
             mod++;
             return root.right;

         }
         else if (root.right == null){
             comp++;
             mod++;
             return root.left;
         }
         mod+=2;
         root = min(root.right);
         root.right = deleteRec(root.right, root.key);
     }

     return root;
 }

 Node min(Node root)
 {
     if(root==null){
         return root;
     }
     Node minv = root;
     while (root.left != null)
     {
         minv = root.left;
         root = root.left;
     }
     return minv;
 }
 Node max(Node root)
 {
     if(root==null){
         return root;
     }
     Node max = root;
     while (root.right != null)
     {
         max = root.right;
         root = root.right;
     }
     return max;
 }
 public Node search(Node root, String key)
 {
     comp++;
     if(root==null||root.key.equals(key))
         return root;
     comp++;
     if (key.compareTo(root.key)<0){
         return search(root.left, key);
     }

     return search(root.right, key);
 }

 public int find(String key){
     comp++;
     if(search(root,key)==null)
         return 0;
     else
         return 1;
 }
 void successor(String value) {
     Node temporary = new Node(value);
     Node valueNode = successorVal(root, temporary);
     if (valueNode != null) {
         System.out.println(valueNode.key);
     } else {
         System.out.println("");
     }
 }
 Node successorVal(Node root, Node value) {
     Node successor = null;
     if (value.right != null) {
         return min(value.right);
     }
     while (root != null) {
         if(value.key.compareTo(root.key) < 0) {
             successor = root;
             root = root.left;
         } else if(value.key.compareTo(root.key) > 0) {
             root = root.right;
         } else {
             break;
         }

     }
     return successor;
 }
}
package nowe_algo_4;

public class RedBlackTree {

    int RED = 0;
    int BLACK = 1;
    int comp=0;
    int mod=0;

     class Node {
        String key;
        int color = BLACK;
        Node left = nil, right = nil, parent = nil;

        public Node(String key) {
            this.key = key;
        }
    }

    Node nil = new Node(null);
    Node root=nil ;
    RedBlackTree() {
        root = nil;
    }

    public Node search(Node root, String key)
    {
        comp++;
        if(root==nil||root.key.equals(key))
            return root;
        comp++;
        if (key.compareTo(root.key)<0){
            return search(root.left, key);
        }

        return search(root.right, key);
    }

    public int find(String key){
        comp++;
        if(search(root,key)==nil)
            return 0;
        else
            return 1;
    }
    void insert(String value) {
        Node node = new Node(value);
        char insert = value.charAt(value.length() - 1);
        if (!((insert >= 'a' && insert <= 'z') || (insert >= 'A' && insert <= 'Z'))) {
            value = value.substring(0, value.length() - 1);
        }
        insert = value.charAt(0);
        if (!((insert >= 'a' && insert <= 'z') || (insert >= 'A' && insert <= 'Z'))) {
            value = value.substring(1);
        }
        Node temporary = root;
        comp++;
        if (root == nil) {
            mod++;
            root = node;
            node.color = BLACK;
            node.parent = nil;
        } else {
            node.color = RED;
            while (true) {
                comp++;
                if (node.key.compareTo(temporary.key) < 0) {
                    comp++;
                    if (temporary.left == nil) {
                        mod++;
                        temporary.left = node;
                        node.parent = temporary;
                        break;
                    } else {
                        temporary = temporary.left;
                    }
                } else if (node.key.compareTo(temporary.key) >= 0) {
                    comp+=2;
                    if (temporary.right == nil) {
                        mod++;
                        temporary.right = node;
                        node.parent = temporary;
                        break;
                    } else {
                        temporary = temporary.right;
                    }
                }
            }
            fixTree(node);
        }
    }
    private void fixTree(Node node) {
        while (node.parent.color == RED) {
            comp++;
            Node uncle = nil;
            comp++;
            if (node.parent == node.parent.parent.left) {
                uncle = node.parent.parent.right;

                comp++;
                if (uncle != nil && uncle.color == RED) {
                    //mod++;
                    node.parent.color = BLACK;
                    uncle.color = BLACK;
                    node.parent.parent.color = RED;
                    node = node.parent.parent;
                    continue;
                }
                comp++;
                if (node == node.parent.right) {
                    //Double rotation needed
                    mod++;
                    node = node.parent;
                    rotateLeft(node);
                }

                node.parent.color = BLACK;
                node.parent.parent.color = RED;
                //if the "else if" code hasn't executed, this
                //is a case where we only need a single rotation
                rotateRight(node.parent.parent);
            } else {
                uncle = node.parent.parent.left;
                comp++;
                 if (uncle != nil && uncle.color == RED) {
                    // mod++;
                    node.parent.color = BLACK;
                    uncle.color = BLACK;
                    node.parent.parent.color = RED;
                    node = node.parent.parent;
                    continue;
                }
                 comp++;
                if (node == node.parent.left) {
                    //Double rotation needed
                    node = node.parent;
                    rotateRight(node);
                }
                node.parent.color = BLACK;
                node.parent.parent.color = RED;
                //if the "else if" code hasn't executed, this
                //is a case where we only need a single rotation
                rotateLeft(node.parent.parent);
            }
        }
        root.color = BLACK;
    }

    void rotateLeft(Node node) {
        comp++;
        if (node.parent != nil) {
            comp++;
            if (node == node.parent.left) {
                mod++;
                node.parent.left = node.right;
            } else {
                mod++;
                node.parent.right = node.right;
            }
            mod+=1;
            node.right.parent = node.parent;
            node.parent = node.right;
            comp++;
            if (node.right.left != nil) {
                mod++;
                node.right.left.parent = node;
            }
            mod+=1;
            node.right = node.right.left;
            node.parent.left = node;
        } else {//Need to rotate root
            Node right = root.right;
            root.right = right.left;
            right.left.parent = root;
            root.parent = right;
            right.left = root;
            right.parent = nil;
            root = right;
            mod+=6;
        }
    }

    void rotateRight(Node node) {
        comp++;
        if (node.parent != nil) {
            comp++;
            if (node == node.parent.left) {
                node.parent.left = node.left;
            } else {
                mod++;
                node.parent.right = node.left;
            }
            mod+=2;
            node.left.parent = node.parent;
            node.parent = node.left;
            comp++;
            if (node.left.right != nil) {
                mod++;
                node.left.right.parent = node;
            }
            mod+=2;
            node.left = node.left.right;
            node.parent.right = node;
        } else {//Need to rotate root
            Node left = root.left;
            root.left = root.left.right;
            left.right.parent = root;
            root.parent = left;
            left.right = root;
            left.parent = nil;
            root = left;
            mod+=6;
        }
    }
    void transplant(Node target, Node with){
        comp++;
          if(target.parent == nil){
              root = with;
              mod++;
          }else if(target == target.parent.left){
              comp++;
              mod++;
              target.parent.left = with;
          }else{
              comp++;
              mod++;
              target.parent.right = with;
          }

          with.parent = target.parent;
    }

    boolean delete(String key){
        Node z;
        comp++;
        if((z = search(root,key))==nil) return false;
        Node x;
        Node y = z; // temporary reference y
        int y_original_color = y.color;
        comp++;
        if(z.left == nil){
            x = z.right;
            transplant(z, z.right);
        }else if(z.right == nil){
            comp++;
            x = z.left;
            transplant(z, z.left);
        }else{
            comp++;
            y = min(z.right);
            y_original_color = y.color;
            x = y.right;
            comp++;
            if(y.parent == z){
                x.parent = y;
              //  mod++;
            }
            else{
                transplant(y, y.right);
               // mod+=2;
                y.right = z.right;
                y.right.parent = y;
            }
            transplant(z, y);
          //  mod+=2;
            y.left = z.left;
            y.left.parent = y;
            y.color = z.color;
        }
        comp++;
        if(y_original_color==BLACK)
            deleteFixup(x);
        return true;
    }

    void deleteFixup(Node x){
        while(x!=root && x.color == BLACK){
            comp++;
            if(x == x.parent.left){
                Node w = x.parent.right;
                comp++;
                if(w.color == RED){
                    //mod++;
                    w.color = BLACK;
                    x.parent.color = RED;
                    rotateLeft(x.parent);
                    w = x.parent.right;
                }
                comp++;
                if(w.left.color == BLACK && w.right.color == BLACK){
                    //mod++;
                    w.color = RED;
                    x = x.parent;
                    continue;
                }
                else if(w.right.color == BLACK){
                //  mod++;
                    comp++;
                    w.left.color = BLACK;
                    w.color = RED;
                    rotateRight(w);
                    w = x.parent.right;
                }
                comp++;
                if(w.right.color == RED){
                    //mod++;
                    w.color = x.parent.color;
                    x.parent.color = BLACK;
                    w.right.color = BLACK;
                    rotateLeft(x.parent);
                    x = root;
                }
            }else{
                Node w = x.parent.left;
                if(w.color == RED){
                    //mod++;
                    w.color = BLACK;
                    x.parent.color = RED;
                    rotateRight(x.parent);
                    w = x.parent.left;
                }
                comp++;
                if(w.right.color == BLACK && w.left.color == BLACK){
                    w.color = RED;
                    x = x.parent;
                    continue;
                }
                else if(w.left.color == BLACK){
                    //mod++;
                    comp++;
                    w.right.color = BLACK;
                    w.color = RED;
                    rotateLeft(w);
                    w = x.parent.left;
                }
                comp++;
                if(w.left.color == RED){
                    //mod++;
                    w.color = x.parent.color;
                    x.parent.color = BLACK;
                    w.left.color = BLACK;
                    rotateRight(x.parent);
                    x = root;
                }
            }
        }
        x.color = BLACK;
    }

    Node min(Node root)
    {
     if(root==nil){
         return root;
     }
        Node minv = root;
        while (root.left != nil)
        {
            minv = root.left;
            root = root.left;
        }
        return minv;
    }
    Node max(Node root)
    {
     if(root==nil){
         return root;
     }
        Node max = root;
        while (root.right != nil)
        {
            max = root.right;
            root = root.right;
        }
        return max;
    }


    void inorder()  {
        inorderRec(root);
     }
     void inorderRec(Node root) {
         if (root != null) {
             inorderRec(root.left);
             if(root.key!=null)
             System.out.println(root.key);
             inorderRec(root.right);
         }
     }
     void successor(String value) {
         Node temporary = new Node(value);
         Node valueNode = successorVal(root, temporary);
         if (valueNode != null) {
             System.out.println(valueNode.key);
         } else {
             System.out.println("");
         }
     }
     Node successorVal(Node root, Node value) {
         Node successor = null;
         if (value.right != null) {
             return min(value.right);
         }
         while (root != null) {
             if(value.key.compareTo(root.key) < 0) {

                 successor = root;
                 root = root.left;
             } else if(value.key.compareTo(root.key) > 0) {

                 root = root.right;
             } else {
                 break;
             }

         }
         return successor;
     }

}
package nowe_algo_4;

 class SplayNode
 {
     SplayNode left, right, parent;
     String element;
     public SplayNode()
     {
         this("", null, null, null);
     }
     public SplayNode(String ele)
     {
         this(ele, null, null, null);
     }
     public SplayNode(String ele, SplayNode left, SplayNode right, SplayNode parent)
     {
         this.left = left;
         this.right = right;
         this.parent = parent;
         this.element = ele;
     }
 }
 class SplayTree
 {
     int comp=0;
     int mod=0;
     private SplayNode root;
     private int count = 0;
     public SplayTree()
     {
         root = null;
     }
     public boolean isEmpty()
     {
         return root == null;
     }
     public void clear()
     {
         root = null;
         count = 0;
     }
     public void insert(String ele)
     {
         SplayNode z = root;
         SplayNode p = null;
         while (z != null)
         {comp++;
             p = z;
             comp++;
             if (ele.compareTo(p.element) > 0)
                 z = z.right;
             else
                 z = z.left;
         }
         z = new SplayNode();
         z.element = ele;
         z.parent = p;
         comp++;
         if (p == null)
             root = z;
         else if (ele.compareTo(p.element) > 0){
             p.right = z;
             comp++;
         }
         else{
             comp++;
             p.left = z;
         }
         Splay(z);
         count++;
     }
     public void makeLeftChildParent(SplayNode c, SplayNode p)
     {
         comp++;
         if ((c == null) || (p == null) || (p.left != c) || (c.parent != p))
             throw new RuntimeException("WRONG");
         comp++;
         if (p.parent != null)
         {
             comp++;
             if (p == p.parent.left){
                 p.parent.left = c;
                 mod++;
             }
             else {
                 mod++;
                 p.parent.right = c;
             }
         }
         comp++;
         if (c.right != null){
             c.right.parent = p;
             mod++;
         }
         mod+=4;
         c.parent = p.parent;
         p.parent = c;
         p.left = c.right;
         c.right = p;
     }
     public void makeRightChildParent(SplayNode c, SplayNode p)
     {
         comp++;
         if ((c == null) || (p == null) || (p.right != c) || (c.parent != p))
             throw new RuntimeException("WRONG");
         comp++;
         if (p.parent != null)
         {
             comp++;
             if (p == p.parent.left){
                 p.parent.left = c;
                 mod++;
             }
             else{
                 p.parent.right = c;
                 mod++;
             }
         }
         comp++;
         if (c.left != null){
             mod++;
             c.left.parent = p;
         }
         mod+=4;
         c.parent = p.parent;
         p.parent = c;
         p.right = c.left;
         c.left = p;
     }
     private void Splay(SplayNode x)
     {
         while (x.parent != null)
         {
             comp++;
             SplayNode Parent = x.parent;
             SplayNode GrandParent = Parent.parent;
             comp++;
             if (GrandParent == null)
             {
                 comp++;
                 if (x == Parent.left)
                     makeLeftChildParent(x, Parent);
                 else
                     makeRightChildParent(x, Parent);
             }
             else
             {
                 comp++;
                 if (x == Parent.left)
                 {
                     comp++;
                     if (Parent == GrandParent.left)
                     {
                         makeLeftChildParent(Parent, GrandParent);
                         makeLeftChildParent(x, Parent);
                     }
                     else
                     {
                         makeLeftChildParent(x, x.parent);
                         makeRightChildParent(x, x.parent);
                     }
                 }
                 else
                 {
                     comp++;
                     if (Parent == GrandParent.left)
                     {
                         makeRightChildParent(x, x.parent);
                         makeLeftChildParent(x, x.parent);
                     }
                     else
                     {
                         makeRightChildParent(Parent, GrandParent);
                         makeRightChildParent(x, Parent);
                     }
                 }
             }
         }
         root = x;
     }
     public void remove(String ele)
     {
         SplayNode node = findNode(ele);
        remove(node);
     }
     private void remove(SplayNode node)
     {
         comp++;
         if (node == null)
             return;
         Splay(node);
         comp++;
         if( (node.left != null) && (node.right !=null))
         {
             SplayNode min = node.left;
             while(min.right!=null){
                 min = min.right;
                 comp++;
             }
             min.right = node.right;
             node.right.parent = min;
             node.left.parent = null;
             root = node.left;
             mod+=3;
         }
         else if (node.right != null)
         {
             comp++;
             mod+=2;
             node.right.parent = null;
             root = node.right;
         }
         else if( node.left !=null)
         {
             comp+=2;
             mod+=2;
             node.left.parent = null;
             root = node.left;
         }
         else
         {
             mod+=2;
             root = null;
         }
         mod+=4;
         node.parent = null;
         node.left = null;
         node.right = null;
         node = null;
         count--;
     }
     public int countNodes()
     {
         return count;
     }
     public int search(String val)
     {
         comp++;
         if(findNode(val) != null)
             return 1;
         return 0;
     }
     private SplayNode findNode(String ele)
     {
         SplayNode PrevNode = null;
         SplayNode z = root;
         while (z != null)
         {
             comp++;
             PrevNode = z;
             comp++;
             if (ele.compareTo(z.element) > 0)
                 z = z.right;
             else if (ele.compareTo(z.element) < 0){
                 z = z.left;
                 comp++;
             }
             else if(ele.compareTo(z.element)==0) {
                 comp+=2;
                 Splay(z);
                 return z;
             }
         }
         comp++;
         if(PrevNode != null)
         {
             Splay(PrevNode);
             return null;
         }
         return null;
     }
     public void inorder()
     {
         inorder(root);
     }
     private void inorder(SplayNode r)
     {
         if (r != null)
         {
             inorder(r.left);
             System.out.print(r.element +" ");
             inorder(r.right);
         }
     }
     public void preorder()
     {
         preorder(root);
     }
     private void preorder(SplayNode r)
     {
         if (r != null)
         {
             System.out.print(r.element +" ");
             preorder(r.left);
             preorder(r.right);
         }
     }
     public void postorder()
     {
         postorder(root);
     }
     private void postorder(SplayNode r)
     {
         if (r != null)
         {
             postorder(r.left);
             postorder(r.right);
             System.out.print(r.element +" ");
         }
     }
 }