Advertisement
jtentor

DemoTree2 - BinarySearchTree.java

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