MassiGy/Arbres-binaires-recherches.md

## Arbres-binaires-recherches.md

      
    Raw
  

              Arbres-binaires-recherches.md
            
          
    Binary Search Trees Analytics | Analyse des arbres binaires de recherches.

Description et introduction:

Les arbres binaires de recherche, ou bien ABR, sont des structures de données qui nous permettent d'optimiser certaines opérations, qui seraient trop coûteuses si appliquées sur d'autres structures de données, comme les listes chaînées.
Pour cela, ce projet à pour but de confirmer cette hypothèse. Ainsi nous analyserons les complexité en temps des
algorithmes de type CRUD sur les arbres binaires, nous nous intéresserons plus particulièrement aux opérations d'insertion, de recherche et de suppression.

Participants et membres de groupe:


Massiles GHERNAOUT


Répartition des fichiers:

  .
  ├── arbre.dot
  ├── Element.java
  ├── Main.java
  ├── report.md
  └── Tree.java
  ├── LinkedList.java
  └── Node.java


  7 files

Description du code:


./Element.java

C'est la classe élément qui représente la valeur/contenu des nœuds de nos arbres binaires. 

Chaque élément à une clé entière supposé strictement positive, et inspirée des clé primaire entière des SGBD relationnel. 

De même, chaque élément à une valeur à lui, qui est dans ce cas, un nombre réel, modélisé par le type double. 


./Node.java

C'est la classe nœud qui représente les nœuds de nos listes chaînées. 

Chaque nœud à une valeur entière, qui contiendra les valeurs des clés de nos éléments lors des tests.

Chaque nœud à un attribut suivant (next) de même nature, qui contiendra la référence vers son prochain dans la liste.


./Tree.java

C'est la classe arbre (tree) qui représente les nœuds de notre arbre binaire de recherche. 

Chaque nœud à un fils gauche et un fils droit, qui respectent la loi d'ordre d'un ABR. 

Aussi, chaque nœud à une instance de la classe Element qui représente la valeur de ce nœud. 

Note: Cette classe représente aussi bien un nœud qu'un arbre, étant donné que chaque nœud peut être potentiellement un sous-arbre à l'arbre auquel il appartient.


./LinkedList.java

C'est la classe liste chainée (LinkedList) qui représentera les listes utilisées lors des tests.

Chaque élément de la liste est une instance de la classe Node. 

On a choisi cette classe, même si elle utilise pas la classe Element, car elle contenait déjà toutes les méthodes d'ajout, suppression, et de recherche. De plus, lors de ces opérations, il y a que la clé qui nous intéresse et non le contenu, donc la class Element n'est pas nécessaire. (pour la phase de tests) 


./Main.java

C'est la classe Main qui sera notre contrôleur, où on testera toutes nos méthodes.


./arbre.dot

C'est le fichier arbre.dot qui contiendra notre arbre binaire sous forme d'un pseudo code, afin de générer une visualisation utilisant l'outil xdot.

Exemple d'un arbre binaire de recherche affiché par l'outil xdot.


   # cela peut être obtenu avec la commande
   xdot arbre.dot


Analyse de complexité:


Soit A, un arbre binaire de recherche complet. 

Soit n, le nombre d'élément de notre arbre.

Soit el,  un élément.

Soit k, le nombre d'opérations élémentaires nécessaires à notre algorithme.

Soit h, la hauteur à laquelle el se trouve dans A.

Soit nbNoeuds(hauteur), une fonction qui nous renvoie le nombres de nœuds entre la racine et une certaine hauteur passé en paramètre.
Note: on prendra en considération que les tests conditionnels comme opérations élémentaires.


Note: Par la suite, log(n) représentent le logarithm en base 2 de n.


Pour l'insertion:


Pour insérer el dans l'arbre A, on doit faire un parcours sur l'arbre afin de trouver le bon
emplacement pour insérer le nouvel élément.
Pour comprendre la complexité de l'insertion, il suffit de comprendre la nature de ce parcours.
Lors d'un parcours précédant une insertion, on se retrouve en train d'exploiter la loi d'ordre de notre arbre,
afin de décider si on doit continuer vers la droite ou vers la gauche. Cela, afin d'arriver à ajouter une feuille dans notre arbre qui contiendra el.
Ayant un arbre binaire, et étant donné que cette décision est prise à chaque fois qu'on visite un nœud qui n'est pas une feuille, on conclut que le nombre d'éléments à visiter diminue de moitié (50%) à chaque étape. (une étape est quand on visite un nœud qui n'est pas une feuille.)
Par conséquent, notre parcours d'insertion doit visiter log(n) d'éléments avant d'arriver au bon emplacement.
D'autre part, à chaque étape de prise de décision, on effectue un nombre k = 3 de tests conditionnels, donc, le nombre d'opérations élémentaires durant un parcours d'insertion est  k * log(n).
On déduit que la complexité en temps d'une insertion dans un arbre binaires et de l'ordre de O(log(n)), ce qui confirme la complexité théorique de ce type de donnée abstrait.


Pour la recherche:


Lors d'une recherche, tout comme une insertion, on doit faire un parcours dans A afin de trouver
l'emplacement de el.
Il se trouve que la nature de ce parcours est similaire à celle du parcours effectué lors d'une insertion. Autrement dit, dans une recherche à chaque étape on va aussi diviser de moitié le nombre d'éléments dans lesquels la recherche continuera.
Toutefois, dans la recherche, on ne s'intéresse pas qu' aux feuilles, mais aussi aux nœuds qui se trouvent entre la racine et les feuilles. Par conséquent, un nouveau paramètre doit être pris en compte, et c'est la hauteur h ou se situe el.
Du coup, le nombre d'élément à parcourir est égale à log(nbNoeuds(h)), et cela car le parcour à une nature dichotomique et l'élément recherché est à la hauteur h.
Pour la suite, il suffit de calculer la valeur retourné par l'appel à la fonction nbNoeuds(h).
Ayant un ABR, et si on suppose que le dénombrement de la hauteur commence à la valeur 0, on sait qu' à une certaine hauteur, on retrouve un nombre de noeuds égale à 2^h, ces nœuds partagent tous la même hauteur.
Exemple, si on suppose que A est un arbre binaire complet, alors à la hauteur  h = 3, on retrouvera 2³ = 8 noeuds qui partagent la hauteur h.
Par conséquent, le nombre de noeuds entre la hauteur h et la racine est égale à somme(2⁰ + 2¹ + ... + 2^h). Cela est une somme de termes consécutifs d'une suite géométrique de raison 2. Donc, nbNoeuds(h) = 2^(h+1) - 1.
D'autre part, le nombre d'opérations conditionnelles effectuées par parcours est égal à k = 3.
Partant de cela, on déduit que la complexité temporelle d'un parcour de recherche suit la fonction k * (log(2^(h+1) - 1)).
On conclut que la complexité temporelle est de l'ordre de O(log(n)), ce qui confirme la complexité théorique d'une recherche dans ce type de donnée abstrait.


Pour la suppression:


Pour la suppression dans un ABR, c'est un peu plus complexe à décrire et à étudier, étant donné qu'il y a plusieurs algorithmes qu'on peut mettre en place.
Note: J'ai moi même proposé à ma professeur, Madame Véronique Jay, une autre approche pour ce type d'opération, qui consiste à convertir notre ABR à une liste de noeuds énumérés suivant un parcour prefix, puis à supprimer l'élément voulu de la liste, et enfin, recréer l'arbre en défilant du début.
Par ailleurs, étant donné que cette méthode est très coûteuse, on a décidé d'implémenter un algorithme de suppression in-place, qui permet de supprimer l'élément dans l'arbre directement sans structure de données annexe.
Pour la suite, on définit d'abord les différents cas à traiter lors d'une suppression dans un ABR.
les cas sont les suivants:

Si el est une feuille, on le supprime directement.
Si el a qu'un seul fils, on le supprime et on le remplace avec le nœud de son fils.
Si el a deux fils, on suit les étapes suivantes:

On cherche le prochain élément qui vient après el lors d'une énumération ordonnée des nœuds de l'ABR. Forcément ce successeur est une feuille, ou un parent à un fil droit uniquement.
Si le successeur est parent, on le remplace par son fils droit, si non on le supprime de son emplacement.
Enfin, on remplace la valeur de el par celle de son successeur, qu'on devait garder en mémoire.


Pour les deux premiers scénarios, l'ordre de grandeur des complexités temporelles est le même avec celles d'un parcour de recherche. Autrement dit, la complexité est de l'ordre de O(log(n)).
Pour le dernier cas, il faut additionner à cela la complexité de la recherche du successeur, or qu'on sait que la recherche est de l'ordre de grandeur de O(log(n)).
Par conséquent, on peut déduire, même si n représente une valeurs différente, que l'ordre de grandeur de la suppression dans ce cas est de C * O(log(n)), avec C étant une constante.
En conclusion, la complexité temporelle est de l'ordre de O(log(n)), ce qui confirme la complexité théorique d'une suppression dans ce type de donné abstrait.
Note: ces complexité ont étaient calculées dans le cas ou A est un ABR complet, or qu'un arbre binaire peut facilement se transformer en une liste, ce qui aggraverait nos complexités, étant donné qu'on aura un ordre de grandeur de O(n), dans la pire des situations.

Résultats des tests pratique:


Description des tests:

On crée notre arbre binaire de recherche avec un nombre d'éléments égal à 10 000.

Les valeurs des clés sont tirées aléatoirement d'un interval d'entiers entre 0 et 10 000 000, afin d'avoir un minimum de duplications.

D'autre part, on choisit parmi ces valeurs 1000 d'entre elles à supprimer plus tard. 

Enfin, on rassemble 1000 valeurs aléatoires qui ne devrait pas être dans l'arbre, afin de tester l'insertion.

Note:

L'insertion dans les listes chaînées se fait en tête. Par conséquent, l'ordre n'est pas une priorité.


Résultats:

   ➜  binarySearchTrees git:(master) ✗ java Main
   BinarySearchTree Insertions Done in 1762micro seconds
   LinkedList Insertions Done in 80micro seconds
   BinarySearchTree Deletion Done in 1402micro seconds
   LinkedLists Deletion Done in 72600micro seconds


Commentaires:

Soit N le nombre d'éléments.

Pour l'insertion:

Les résultats sont conformes aux attentes, étant donné que l'insertion est plus rapide dans les listes que dans les arbres. Cela à pour
cause le fait que dans les listes l'insertion se fait en tête, qui donne une complexité de l'ordre de O(1), alors que dans l'arbre
une insertion est basée sur un parcour dichotomique de la structure, ce qui nous fait une complexité de O(log(N)).

Pour la suppression:

Les résultats sont conformes aux attentes, étant donné que la suppression est plus rapide dans les arbres binaires. Cela à pour cause le fait que dans les listes la suppression est toujours précédée par un parcour linéaire qui donne une complexité de l'ordre de O(N), alors que dans l'arbre, une suppression est basée sur un parcour dichotomique de la structure, potentiellement deux, ce qui nous fait une complexité de O(log(N)).


## Element.java
public class Element {

    private int id;
    private double content;


    public Element(int id, double content) {
        assert id > 0;

        this.id = id;
        this.content = content;
    }

    public int getId() {
        return id;
    }

    public double getContent() {
        return content;
    }

    public void setId(int id) {
        this.id = id;
    }

    public void setContenu(double content) {
        this.content = content;
    }

    public String toString() {
        return ("ID : " + getId() + "    Content : " + getContent() + "\n");
    }
}


## LinkedList.java
public class LinkedList {
    public Node head;
    public Node tail;
    public int length;

    public LinkedList() {
        this.head = new Node();
        tail = head;
        this.length = 1;
    }

    public LinkedList(int val) {
        this.head = new Node(val);
        tail = head;
        this.length = 1;
    }

    public void readList() {
        Node temp = this.head;

        while (temp != null) {
            System.out.println(temp.val);
            temp = temp.next;
        }

        return;
    }

    /**
     * @description: adds a value to the end of the list
     */
    public void push(int number) {

        if (head == null) {
            return;
        }

        tail.next = new Node(number);
        tail = tail.next;
        this.length++;
        return;
    }

    /**
     * @description: removes a value from the end of the list
     */
    public Node pop() {
        Node temp = this.tail;

        if (this.length == 0) {
            return null;
        }
        if (this.length == 1) {
            head = null;
            tail = null;
            return temp;
        }

        Node walker = this.head;

        while (walker.next != tail) {
            walker = walker.next;
        }

        tail = walker;
        tail.next = null;

        this.length--;
        return temp;
    }

    /**
     * @description: removes a value from the head of the list
     */
    public Node shift() {
        Node temp = head;

        if (this.length == 1) {
            this.head = null;
            this.tail = null;
            this.length--;
            return temp;
        }
        if (head == null || this.length == 0) {
            return null;
        }

        head = head.next;
        this.length--;
        return temp;
    }

    /**
     * @description: add a value to the start of the list
     */
    public void unshift(int number) {

        // if list empty make the item the first element of the list and the last one
        if (this.head == null && this.tail == null) {
            this.head = new Node(number);
            this.tail = head;
            return;
        }

        // otherwise, append to the beginning by attaching the item to the list
        // then, set the item as the new list head.
        Node temp = new Node(number);
        temp.next = head;
        head = temp;
        this.length++;
        return;
    }

    /**
     * @description: Checks whether if a value is in the list or not
     */
    public boolean search(int query) {
        Node temp = head;

        while (temp != null && temp.val != query) {
            temp = temp.next;
        }
        if (temp == null)
            return false;

        return true;
    }

    /**
     * @description: removes a value from the list
     */
    public void delete(int query) {

        if (head.val == query) {
            this.shift();
            return;
        }

        if (head.next == null && head.val != query) {
            return;
        }

        Node temp = head;

        while (temp.next != null && temp.next.val != query) {
            temp = temp.next;
        }

        if (temp.next.val == query) {
            temp.next = temp.next.next;
            this.length--;
        }
        return;
    }

    /**
     * @description: updates a value on the list knowing its position
     */
    public void update(int pos, int newVal) {
        Node temp = head;
        int counter = 0;

        while (temp != null && counter < pos) {
            temp = temp.next;
            counter++;
        }

        if (temp == null || counter != pos) {
            throw new Error("should not be equal to null");
        }

        temp.val = newVal;

        return;
    }

    /**
     * @description: inserts a val to a specific position of the list.
     */
    public void insertAt(int pos, int val) {
        if (pos <= 0) {
            this.unshift(val);
            return;
        }
        if (pos >= this.length) {
            this.push(val);
            return;
        }

        // otherwise, insert into the pos

        // first travers all the list to the position.
        Node temp = head;
        int counter = 0;

        while (temp != null && counter < pos) {
            temp = temp.next;
            counter++;
        }

        // then insert the new item and pay attention to not lose the rest of the list.
        Node newItem = new Node(val);
        newItem.next = temp.next;
        temp.next = newItem;
        this.length++;
        return;
    }

    /**
     * @description: removes a part of the list.
     */
    public void splice(int pos, int deleteCount) {

        if (deleteCount < 0) {
            return;
        }

        int counter;
        this.length -= deleteCount;

        if (pos <= 0) {
            counter = 0;

            while (counter < deleteCount) {
                this.shift();
                counter++;
            }
            return;
        }

        if (pos >= this.length) {
            counter = 0;

            while (counter < deleteCount) {
                this.pop();
                counter++;
            }
            return;
        }

        // otherwise, travers the list to the pos
        // then, start removing the elements and connect the two sides of the list after
        // the deletion.

        Node temp = head;
        counter = 0;

        while (temp != null && counter < pos) {
            temp = temp.next;
            counter++;
        }

        counter = 0;
        Node walker = temp;

        while (counter < deleteCount) { // we should free the memory but JAVA is garbage collected.
            walker = walker.next;
            counter++;
        }

        temp.next = walker.next;
        return;
    }

    /**
     * @description: splits the list into two on the given position.
     */
    public LinkedList split(int pos) {

        LinkedList rest = new LinkedList();

        Node walker = this.head;

        int counter = 0;

        while (walker != null && counter < pos - 1) {
            walker = walker.next;
            counter++;
        }

        assert walker != null;

        rest.head = walker.next;
        walker.next = null;

        return rest;
    }

    public LinkedList mergeSort(LinkedList list, int length) {

        if (length < 2) {
            return list;
        }

        int half = length / 2;

        LinkedList left = list;
        LinkedList right = list.split(half);

        return mergeBySorting(
                mergeSort(left, half),
                mergeSort(right, length - half));

    }

    public LinkedList mergeBySorting(LinkedList left, LinkedList right) {

        LinkedList resault = new LinkedList(0);

        if (left.head.val <= right.head.val) {
            resault.update(0, left.shift().val);

        } else {
            resault.update(0, right.shift().val);
        }

        while (left.head != null && right.head != null) {

            if (left.head.val <= right.head.val) {
                resault.push(left.shift().val);
            } else {
                resault.push(right.shift().val);
            }

        }
        while (left.head != null || right.head != null) {
            if (left.head != null) {
                resault.push(left.shift().val);
            }
            if (right.head != null) {
                resault.push(right.shift().val);
            }
        }

        return resault;
    }

}

## Main.java
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.StandardOpenOption;
import java.util.ArrayList;

public class Main {

  public static void main(String[] args) {

    long startTime, endTime, duration;

    int elemCount = 10000;
    int valuesRange = 10000000;
    int elemToDeleteCount = 1000;
    int elemToInsertCount = 1000;

    int[] toInsert = new int[elemToInsertCount];
    int[] toDelete = new int[elemToDeleteCount];

    int j = 0;
    int k = 0;
    int key;

    Element root = new Element((int) (Math.random() * valuesRange), Math.random() * valuesRange);
    Tree tree = new Tree(root);

    LinkedList list = new LinkedList(root.getId());

    for (int i = 0; i < elemCount; i++) {

      key = (int) (Math.random() * valuesRange);
      tree.insert(new Element(key, Math.random() * valuesRange));
      list.unshift(key);

      if (Math.random() >= 0.6 && k < elemToDeleteCount) {
        toInsert[j] = key * (int) (Math.random() * valuesRange);
        toDelete[k] = key;
        k++;
        j++;
      }
    }

    // for the inserts on the binary tree
    startTime = System.nanoTime();

    for (int i = 0; i < toInsert.length; i++) {
      tree.insert(new Element(toInsert[i], 0.0));
    }

    endTime = System.nanoTime();

    duration = endTime - startTime;

    System.out.println("BinarySearchTree Insertions Done in " + duration / 1000 + "micro seconds");

    // for the inserts on the array list
    startTime = System.nanoTime();

    for (int i = 0; i < toInsert.length; i++) {
      list.unshift(toInsert[i]);
    }

    endTime = System.nanoTime();

    duration = endTime - startTime;

    System.out.println("LinkedList Insertions Done in " + duration / 1000 + "micro seconds");

    // for the deletions on the binary tree
    startTime = System.nanoTime();

    for (int i = 0; i < toDelete.length; i++) {
      tree.delete(toDelete[i], null);
    }

    endTime = System.nanoTime();

    duration = endTime - startTime;

    System.out.println("BinarySearchTree Deletion Done in " + duration / 1000 + "micro seconds");

    // for the deletions on the linkedlistsm
    startTime = System.nanoTime();

    for (int i = 0; i < toDelete.length; i++) {
      list.delete(toDelete[i]);
    }

    endTime = System.nanoTime();

    duration = endTime - startTime;

    System.out.println("LinkedLists Deletion Done in " + duration / 1000 + "micro seconds");


    /*** Uncomment this to see how the tree visualization works ***/

    // tree = new Tree(new Element(8, 1.5));

    // tree.insert(new Element(5, 9));
    // tree.insert(new Element(4, 8));
    // tree.insert(new Element(7, 12.32));
    // tree.insert(new Element(6, 102.11));
    // tree.insert(new Element(10, 46.72));
    // tree.insert(new Element(9, 80.9));
    // tree.insert(new Element(12, 499.72));

    // tree.delete(5, null);
    // tree.delete(8, null);
    // System.out.println("--------\n");

    // ArrayList<Tree> queue = new ArrayList<>();

    // tree.inOrder_listing(queue);
    // System.out.println(queue);

    // try {

    //   Files.writeString(Path.of("arbre.dot"), "digraph arbre {\n",
    //       StandardOpenOption.APPEND);
    //   tree.genXdotMarkup("arbre.dot");
    //   Files.writeString(Path.of("arbre.dot"), "}\n", StandardOpenOption.APPEND);

    // } catch (Exception e) {
    //   System.out.println("Error payload is set to " + e.getMessage());
    // }

  }
}

## Node.java
public class Node {
    public int val;
    public Node next;


    public Node(){
        this.val = (int) (Math.random() * 100);
        this.next = null;
    }

    public Node(int number) {
        this.val = number;
        this.next = null;
    }
}

## Tree.java
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.StandardOpenOption;
import java.util.ArrayList;

public class Tree {

  public Element val;
  public Tree left;
  public Tree right;

  public Tree(int root_key, double root_val) {

    assert root_key > 0;

    this.val = new Element(root_key, root_val);
    this.left = null;
    this.right = null;
  }

  public Tree(Element root) {
    this.val = root;
    this.left = null;
    this.right = null;
  }

  public int getLength() {

    if (this.isLeaf())
      return 1;
    return (1 + Math.max(this.left.getLength(), this.right.getLength()));
  }

  public void insert(Element newVal) {
    assert newVal != null;
    assert newVal.getId() > 0;

    if (this.val.getId() == newVal.getId())
      return;

    if (newVal.getId() < this.val.getId()) {

      if (this.left == null) {
        this.left = new Tree(new Element(newVal.getId(), newVal.getContent()));
      } else {
        this.left.insert(newVal);
      }

    } else {

      if (this.right == null) {
        this.right = new Tree(new Element(newVal.getId(), newVal.getContent()));
      } else {
        this.right.insert(newVal);
      }

    }
  }

  public boolean isLeaf() {
    return (this.left == null && this.right == null);
  }

  public void inOrder_print() {

    if (this.isLeaf()) {
      System.out.print(" " + this.val.toString() + " \n");
      return;
    }
    if (this.left != null) {
      this.left.inOrder_print();
    }

    System.out.print(" " + this.val.toString() + " \n");

    if (this.right != null) {
      this.right.inOrder_print();
    }
  }

  public void preOrder_print() {

    if (this.isLeaf()) {
      System.out.print(" " + this.val.toString() + " \n");
      return;
    }

    System.out.print(" " + this.val.toString() + " \n");

    if (this.left != null) {
      this.left.preOrder_print();
    }

    if (this.right != null) {
      this.right.preOrder_print();
    }
  }

  public void postOrder_print() {

    if (this.isLeaf()) {
      System.out.print(" " + this.val.toString() + " \n");
      return;
    }

    if (this.right != null) {
      this.right.postOrder_print();
    }

    System.out.print(" " + this.val.toString() + " \n");

    if (this.left != null) {
      this.left.postOrder_print();
    }
  }

  public Element search(int query) {
    assert query > 0;

    if (this.val.getId() == query) {
      return this.val;
    }
    if (this.isLeaf() && this.val.getId() != query) {
      return null;
    }

    if (query < this.val.getId()) {
      return this.left.search(query);
    } else {
      return this.right.search(query);
    }
  }

  public boolean search(Element query) {
    assert query != null;
    assert query.getId() > 0;

    if (this.val.getId() == query.getId()) {
      return true;
    }
    if (this.isLeaf() && this.val.getId() != query.getId()) {
      return false;
    }

    if (query.getId() < this.val.getId()) {
      return this.left.search(query);
    } else {
      return this.right.search(query);
    }
  }

  public void delete(int key, Tree parent) {
    assert key > 0;

    // check if the the current val is the the one to be deleted
    if (this.val.getId() == key) {

      // if this.isLeaf, then just remove it via its parent.
      if (this.isLeaf() && parent != null) {

        if (parent.left == this)
          parent.left = null;
        else
          parent.right = null;

        return;
      }

      // if this.isLeaf, and the parent is null, which means that the tree has only
      // the root as a node which is also a leaf.
      if (this.isLeaf() && parent == null) {
        // no deconstructors are defined so just make the content to null;
        this.val = null;
        return;
      }

      // if thereis only the rightSon, replace the current by its value
      if (this.left == null && this.right != null) {
        if (parent.left == this) {
          parent.left = this.right;
        } else {
          parent.right = this.right;
        }
        return;
      }

      // if thereis only the leftSon, replace the current by its value
      if (this.right == null && this.left != null) {
        if (parent.left == this) {
          parent.left = this.left;
        } else {
          parent.right = this.left;
        }
        return;
      }

      // if thereis both of them,
      if (this.left != null && this.right != null) {
        /*
         * find the next inorder successor, and replace the current val with its val
         * the next inorder successor will be the smallest element on the right sub tree
         * NOTE: the next successor can only be a leaf or have a right child
         */

        Tree nextInOrderSuccessor = this.right;
        Tree nextInOrderSuccessorParent = this;

        while (nextInOrderSuccessor.left != null) {
          nextInOrderSuccessorParent = nextInOrderSuccessor;
          nextInOrderSuccessor = nextInOrderSuccessor.left;
        }

        if (nextInOrderSuccessor.isLeaf()) {

          // if the next successor is a leaf and its the right son of the current
          // just copy its value to the current and then remove it
          if (this.right == nextInOrderSuccessor) {
            this.val = nextInOrderSuccessor.val;
            this.right = null;
            return;
          }

          // otherwise, the successor is not the current right son,
          // copy its value to the current, and remove it via its parent.
          if (this.right != nextInOrderSuccessor) {
            this.val = nextInOrderSuccessor.val;
            nextInOrderSuccessorParent.left = null;
            return;
          }
        }

        // if the successor is not a leaf, so it has a right son.
        // just replace it with its right son after copying its value to current
        if (nextInOrderSuccessor.right != null) {
          this.val = nextInOrderSuccessor.val;
          this.right = nextInOrderSuccessor.right;
          return;
        }
      }

      return;
    }

    // finally, if the value is on one of the sub trees, which are not currently
    // leaves, call the function recursively.
    if (key < this.val.getId() && this.left != null) {

      this.left.delete(key, this);

    } else if (key > this.val.getId() && this.right != null) {

      this.right.delete(key, this);

    }
  }

  public void inOrder_listing(ArrayList<Tree> queue) {

    if (this.isLeaf()) {
      queue.add(this);
      return;
    }

    if (this.left != null) {
      this.left.inOrder_listing(queue);
    }

    queue.add(this);

    if (this.right != null) {
      this.right.inOrder_listing(queue);
    }

  }

  public void preOrder_listing(ArrayList<Tree> queue) {

    if (this.isLeaf()) {
      queue.add(this);
      return;
    }

    queue.add(this);

    if (this.left != null) {
      this.left.preOrder_listing(queue);
    }

    if (this.right != null) {
      this.right.preOrder_listing(queue);
    }

  }

  public void genXdotMarkup(String filePath) {

    assert filePath != null && filePath != "";

    String markup = "";

    if (this.left != null)
      markup += "\t" + String.valueOf(val.getId()) + " -> " + String.valueOf(left.val.getId()) + ";\n";

    if (this.right != null)
      markup += "\t" + String.valueOf(val.getId()) + " -> " + String.valueOf(right.val.getId()) + ";\n";

    try {

      Files.writeString(Path.of(filePath), markup, StandardOpenOption.APPEND);

    } catch (Exception e) {
      System.out.println("Error payload is set to " + e.getMessage());
    }

    if (this.left != null)
      this.left.genXdotMarkup(filePath);

    if (this.right != null)
      this.right.genXdotMarkup(filePath);
  }

  @Override
  public String toString() {
    return this.val.toString();
  }

}
	public class Element {

	private int id;
	private double content;


	public Element(int id, double content) {
	assert id > 0;

	this.id = id;
	this.content = content;
	}

	public int getId() {
	return id;
	}

	public double getContent() {
	return content;
	}

	public void setId(int id) {
	this.id = id;
	}

	public void setContenu(double content) {
	this.content = content;
	}

	public String toString() {
	return ("ID : " + getId() + " Content : " + getContent() + "\n");
	}
	}
	public class LinkedList {
	public Node head;
	public Node tail;
	public int length;

	public LinkedList() {
	this.head = new Node();
	tail = head;
	this.length = 1;
	}

	public LinkedList(int val) {
	this.head = new Node(val);
	tail = head;
	this.length = 1;
	}

	public void readList() {
	Node temp = this.head;

	while (temp != null) {
	System.out.println(temp.val);
	temp = temp.next;
	}

	return;
	}

	/**
	* @description: adds a value to the end of the list
	*/
	public void push(int number) {

	if (head == null) {
	return;
	}

	tail.next = new Node(number);
	tail = tail.next;
	this.length++;
	return;
	}

	/**
	* @description: removes a value from the end of the list
	*/
	public Node pop() {
	Node temp = this.tail;

	if (this.length == 0) {
	return null;
	}
	if (this.length == 1) {
	head = null;
	tail = null;
	return temp;
	}

	Node walker = this.head;

	while (walker.next != tail) {
	walker = walker.next;
	}

	tail = walker;
	tail.next = null;

	this.length--;
	return temp;
	}

	/**
	* @description: removes a value from the head of the list
	*/
	public Node shift() {
	Node temp = head;

	if (this.length == 1) {
	this.head = null;
	this.tail = null;
	this.length--;
	return temp;
	}
	if (head == null \|\| this.length == 0) {
	return null;
	}

	head = head.next;
	this.length--;
	return temp;
	}

	/**
	* @description: add a value to the start of the list
	*/
	public void unshift(int number) {

	// if list empty make the item the first element of the list and the last one
	if (this.head == null && this.tail == null) {
	this.head = new Node(number);
	this.tail = head;
	return;
	}

	// otherwise, append to the beginning by attaching the item to the list
	// then, set the item as the new list head.
	Node temp = new Node(number);
	temp.next = head;
	head = temp;
	this.length++;
	return;
	}

	/**
	* @description: Checks whether if a value is in the list or not
	*/
	public boolean search(int query) {
	Node temp = head;

	while (temp != null && temp.val != query) {
	temp = temp.next;
	}
	if (temp == null)
	return false;

	return true;
	}

	/**
	* @description: removes a value from the list
	*/
	public void delete(int query) {

	if (head.val == query) {
	this.shift();
	return;
	}

	if (head.next == null && head.val != query) {
	return;
	}

	Node temp = head;

	while (temp.next != null && temp.next.val != query) {
	temp = temp.next;
	}

	if (temp.next.val == query) {
	temp.next = temp.next.next;
	this.length--;
	}
	return;
	}

	/**
	* @description: updates a value on the list knowing its position
	*/
	public void update(int pos, int newVal) {
	Node temp = head;
	int counter = 0;

	while (temp != null && counter < pos) {
	temp = temp.next;
	counter++;
	}

	if (temp == null \|\| counter != pos) {
	throw new Error("should not be equal to null");
	}

	temp.val = newVal;

	return;
	}

	/**
	* @description: inserts a val to a specific position of the list.
	*/
	public void insertAt(int pos, int val) {
	if (pos <= 0) {
	this.unshift(val);
	return;
	}
	if (pos >= this.length) {
	this.push(val);
	return;
	}

	// otherwise, insert into the pos

	// first travers all the list to the position.
	Node temp = head;
	int counter = 0;

	while (temp != null && counter < pos) {
	temp = temp.next;
	counter++;
	}

	// then insert the new item and pay attention to not lose the rest of the list.
	Node newItem = new Node(val);
	newItem.next = temp.next;
	temp.next = newItem;
	this.length++;
	return;
	}

	/**
	* @description: removes a part of the list.
	*/
	public void splice(int pos, int deleteCount) {

	if (deleteCount < 0) {
	return;
	}

	int counter;
	this.length -= deleteCount;

	if (pos <= 0) {
	counter = 0;

	while (counter < deleteCount) {
	this.shift();
	counter++;
	}
	return;
	}

	if (pos >= this.length) {
	counter = 0;

	while (counter < deleteCount) {
	this.pop();
	counter++;
	}
	return;
	}

	// otherwise, travers the list to the pos
	// then, start removing the elements and connect the two sides of the list after
	// the deletion.

	Node temp = head;
	counter = 0;

	while (temp != null && counter < pos) {
	temp = temp.next;
	counter++;
	}

	counter = 0;
	Node walker = temp;

	while (counter < deleteCount) { // we should free the memory but JAVA is garbage collected.
	walker = walker.next;
	counter++;
	}

	temp.next = walker.next;
	return;
	}

	/**
	* @description: splits the list into two on the given position.
	*/
	public LinkedList split(int pos) {

	LinkedList rest = new LinkedList();

	Node walker = this.head;

	int counter = 0;

	while (walker != null && counter < pos - 1) {
	walker = walker.next;
	counter++;
	}

	assert walker != null;

	rest.head = walker.next;
	walker.next = null;

	return rest;
	}

	public LinkedList mergeSort(LinkedList list, int length) {

	if (length < 2) {
	return list;
	}

	int half = length / 2;

	LinkedList left = list;
	LinkedList right = list.split(half);

	return mergeBySorting(
	mergeSort(left, half),
	mergeSort(right, length - half));

	}

	public LinkedList mergeBySorting(LinkedList left, LinkedList right) {

	LinkedList resault = new LinkedList(0);

	if (left.head.val <= right.head.val) {
	resault.update(0, left.shift().val);

	} else {
	resault.update(0, right.shift().val);
	}

	while (left.head != null && right.head != null) {

	if (left.head.val <= right.head.val) {
	resault.push(left.shift().val);
	} else {
	resault.push(right.shift().val);
	}

	}
	while (left.head != null \|\| right.head != null) {
	if (left.head != null) {
	resault.push(left.shift().val);
	}
	if (right.head != null) {
	resault.push(right.shift().val);
	}
	}

	return resault;
	}

	}
	import java.nio.file.Files;
	import java.nio.file.Path;
	import java.nio.file.StandardOpenOption;
	import java.util.ArrayList;

	public class Main {

	public static void main(String[] args) {

	long startTime, endTime, duration;

	int elemCount = 10000;
	int valuesRange = 10000000;
	int elemToDeleteCount = 1000;
	int elemToInsertCount = 1000;

	int[] toInsert = new int[elemToInsertCount];
	int[] toDelete = new int[elemToDeleteCount];

	int j = 0;
	int k = 0;
	int key;

	Element root = new Element((int) (Math.random() * valuesRange), Math.random() * valuesRange);
	Tree tree = new Tree(root);

	LinkedList list = new LinkedList(root.getId());

	for (int i = 0; i < elemCount; i++) {

	key = (int) (Math.random() * valuesRange);
	tree.insert(new Element(key, Math.random() * valuesRange));
	list.unshift(key);

	if (Math.random() >= 0.6 && k < elemToDeleteCount) {
	toInsert[j] = key * (int) (Math.random() * valuesRange);
	toDelete[k] = key;
	k++;
	j++;
	}
	}

	// for the inserts on the binary tree
	startTime = System.nanoTime();

	for (int i = 0; i < toInsert.length; i++) {
	tree.insert(new Element(toInsert[i], 0.0));
	}

	endTime = System.nanoTime();

	duration = endTime - startTime;

	System.out.println("BinarySearchTree Insertions Done in " + duration / 1000 + "micro seconds");

	// for the inserts on the array list
	startTime = System.nanoTime();

	for (int i = 0; i < toInsert.length; i++) {
	list.unshift(toInsert[i]);
	}

	endTime = System.nanoTime();

	duration = endTime - startTime;

	System.out.println("LinkedList Insertions Done in " + duration / 1000 + "micro seconds");

	// for the deletions on the binary tree
	startTime = System.nanoTime();

	for (int i = 0; i < toDelete.length; i++) {
	tree.delete(toDelete[i], null);
	}

	endTime = System.nanoTime();

	duration = endTime - startTime;

	System.out.println("BinarySearchTree Deletion Done in " + duration / 1000 + "micro seconds");

	// for the deletions on the linkedlistsm
	startTime = System.nanoTime();

	for (int i = 0; i < toDelete.length; i++) {
	list.delete(toDelete[i]);
	}

	endTime = System.nanoTime();

	duration = endTime - startTime;

	System.out.println("LinkedLists Deletion Done in " + duration / 1000 + "micro seconds");



	/* Uncomment this to see how the tree visualization works */

	// tree = new Tree(new Element(8, 1.5));

	// tree.insert(new Element(5, 9));
	// tree.insert(new Element(4, 8));
	// tree.insert(new Element(7, 12.32));
	// tree.insert(new Element(6, 102.11));
	// tree.insert(new Element(10, 46.72));
	// tree.insert(new Element(9, 80.9));
	// tree.insert(new Element(12, 499.72));

	// tree.delete(5, null);
	// tree.delete(8, null);
	// System.out.println("--------\n");

	// ArrayList<Tree> queue = new ArrayList<>();

	// tree.inOrder_listing(queue);
	// System.out.println(queue);

	// try {

	// Files.writeString(Path.of("arbre.dot"), "digraph arbre {\n",
	// StandardOpenOption.APPEND);
	// tree.genXdotMarkup("arbre.dot");
	// Files.writeString(Path.of("arbre.dot"), "}\n", StandardOpenOption.APPEND);

	// } catch (Exception e) {
	// System.out.println("Error payload is set to " + e.getMessage());
	// }

	}
	}
	public class Node {
	public int val;
	public Node next;


	public Node(){
	this.val = (int) (Math.random() * 100);
	this.next = null;
	}

	public Node(int number) {
	this.val = number;
	this.next = null;
	}
	}