Je veux mettre en œuvre un arbre AVL en Java, voici ce que j'ai jusqu'à présent :
public class AVLNode {
private int size; /** The size of the tree. */
private int height; /** The height of the tree. */
private Object key;/** The key of the current node. */
private Object data;/** The data of the current node. */
private Comparator comp;/** The {@link Comparator} used by the node. */
/* All the nodes pointed by the current node.*/
private AVLNode left,right,parent,succ,pred;
/* Instantiates a new AVL node.
*
* @param key the key of the node
* @param data the data that the node should keep
* @param comp the comparator to be used in the tree
*/
public AVLNode(Object key, Object data, Comparator comp) {
this(key,data,comp,null);
}
/* Instantiates a new AVL node.
*
* @param key the key of the node
* @param data the data that the node should keep
* @param comp the comparator to be used in the tree
* @param parent the parent of the created node
*/
public AVLNode(Object key, Object data, Comparator comp, AVLNode parent) {
this.data = data;
this.key = key;
this.comp = comp;
this.parent = parent;
this.left = null;
this.right = null;
this.succ = null;
this.pred = null;
this.size = 1;
this.height = 0;
}
/* Adds the given data to the tree.
*
* @param key the key
* @param data the data
* @return the root of the tree after insertion and rotations
* @author <b>students</b>
*/
public AVLNode add(Object key,Object data) {
return null;
}
/* Removes a Node which key is equal
* (by {@link Comparator}) to the given argument.
*
* @param key the key
* @return the root after deletion and rotations
* @author <b>students</b>
*/
public AVLNode remove(Object key) {
return null;
}Je dois mettre en œuvre les fonctions d'ajout et de suppression. Voici ce que j'ai jusqu'à présent, les deux devraient s'exécuter en O(log(n)) temps. Les deux devraient renvoyer la racine de l'arbre entier :
/* Adds a new Node into the tree.
* @param key the key of the new node
* @param data the data of the new node
*/
public void add(Object key,Object data){
if (isEmpty()){
this.root = new AVLNode(key,data,comp);
}
else{
root = this.root.add(key,data);
}
}
/**
* Removes a node n from the tree where
* n.key is equal (by {@link Comparator}) to the given key.
*
* @param key the key
*/
public void remove(Object key){
if (isEmpty()){
return;
}
else
root = this.root.remove(key);
}J'ai besoin d'aide pour créer les fonctions d'ajout et de suppression.
Existe-t-il un guide décrivant le fonctionnement des opérations d'ajout et de suppression ? Une bibliothèque à copier ou quelque chose où je peux comprendre comment/pourquoi les arbres AVL fonctionnent ?
