FacundoCruz

Arbol de busqueda binaria

Nov 6th, 2020
179
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //
  2. // Created by Julio Tentor <jtentor@fi.unju.edu.ar>
  3. //
  4.  
  5. public class BinarySearchTree<ELEMENT extends Comparable<ELEMENT>> extends BinaryTree<ELEMENT> {
  6.  
  7.  
  8.     public BinarySearchTree() {
  9.         super();
  10.     }
  11.  
  12.  
  13.     public void add(ELEMENT item) {
  14.         if (this.root == null) {
  15.             this.root = new BTNode<ELEMENT>(item, null, null);
  16.         } else {
  17.             BTNode<ELEMENT> temp = this.root;
  18.             BTNode<ELEMENT> prev = null;
  19.             while (temp != null ) {
  20.                 prev = temp;
  21.                 if (item.compareTo(temp.item) < 0) {
  22.                     temp = temp.left;
  23.                 } else {
  24.                     temp = temp.right;
  25.                 }
  26.             }
  27.             temp = new BTNode<ELEMENT>(item, null, null);
  28.             if (item.compareTo(prev.item) < 0) {
  29.                 prev.left = temp;
  30.             } else {
  31.                 prev.right = temp;
  32.             }
  33.         }
  34.     }
  35.  
  36.  
  37.     public ELEMENT remove(ELEMENT item) {
  38.         return removeByCopy(item);
  39.         //return removeByFusion(item);
  40.     }
  41.  
  42.  
  43.     private ELEMENT removeByCopy(ELEMENT item) {
  44.         BTNode<ELEMENT> find = this.root;
  45.         BTNode<ELEMENT> prev = null;
  46.         while ((find != null) && (find.item.compareTo(item) != 0)) {
  47.             prev = find;
  48.             if (item.compareTo(find.item) < 0) {
  49.                 find = find.left;
  50.             } else {
  51.                 find = find.right;
  52.             }
  53.         }
  54.         if (find == null) {
  55.             throw new RuntimeException("No existe el elemento o el árbol está vacío");
  56.         } // find es el nodo con el valor a extraer y prev el padre de ese nodo
  57.         ELEMENT save = find.item;
  58.         BTNode<ELEMENT> node = find;
  59.         if (node.right == null) { // no hay subarbol derecho
  60.             node = node.left; // nodo con un descendiente u hoja
  61.         } else {
  62.             if (node.left == null) { // no hay subarbol izquierdo
  63.                 node = node.right; // nodo con un descendiente u hoja
  64.             } else { // dos descendientes
  65.                 BTNode<ELEMENT> last = node;
  66.                 BTNode<ELEMENT> temp = node.right; // a la derecha (mayores)
  67.                 while (temp.left != null) { // busca a la izquierda el menor
  68.                     last = temp;
  69.                     temp = temp.left;
  70.                 }
  71.                 // temp es el menor de los mayores
  72.                 node.item = temp.item; // hace la copia
  73.                 if (last == node) {
  74.                     last.right = temp.right;
  75.                 } else {
  76.                     last.left = temp.right;
  77.                 }
  78.                 temp.right = null;
  79.             }
  80.         }
  81.         // reajustar el arbol
  82.         if (find == this.root) {
  83.             this.root = node;
  84.         } else {
  85.             if (prev.left == find) {
  86.                 prev.left = node;
  87.             } else {
  88.                 prev.right = node;
  89.             }
  90.         }
  91.         return save;
  92.     }
  93.  
  94.  
  95.     private ELEMENT removeByFusion(ELEMENT item) {
  96.         BTNode<ELEMENT> find = this.root;
  97.         BTNode<ELEMENT> prev = null;
  98.         while ((find != null) && (find.item.compareTo(item) != 0)) {
  99.             prev = find;
  100.             if (item.compareTo(find.item) < 0) {
  101.                 find = find.left;
  102.             } else {
  103.                 find = find.right;
  104.             }
  105.         }
  106.         if (find == null) {
  107.             throw new RuntimeException("No existe el elemento o el árbol está vacío");
  108.         }
  109.         ELEMENT save = find.item;
  110.         BTNode<ELEMENT> node = find;
  111.         if (node.right == null) {
  112.             node = node.left;
  113.         } else {
  114.             if (node.left == null) {
  115.                 node = node.right;
  116.             } else {
  117.                 BTNode<ELEMENT> temp = node.right;
  118.                 while (temp.left != null) {
  119.                     temp = temp.left;
  120.                 }
  121.                 temp.left = node.left;
  122.                 node = node.right;
  123.             }
  124.         }
  125.         if (find == this.root) {
  126.             this.root = node;
  127.         } else {
  128.             if (prev.left == find) {
  129.                 prev.left = node;
  130.             } else {
  131.                 prev.right = node;
  132.             }
  133.         }
  134.         find.left = find.right = null;
  135.         return save;
  136.     }
  137.  
  138. }
  139.  
Add Comment
Please, Sign In to add comment