jtentor

Árbol - AVLTree.java

Nov 1st, 2020
806
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 15.31 KB | None | 0 0
  1. //
  2. // Created by Julio Tentor <jtentor@fi.unju.edu.ar>
  3. //
  4.  
  5. // Código basado en el capítulo 14 de
  6. // Joyanes Aguilar, Luis and Zahonero Martínez, Ignacio. 2008. Estructuras de datos en Java
  7. // https://drive.google.com/file/d/0B7lAHg81F3X_c2g5c2txQ1g5TTQ/view
  8.  
  9. public class AVLTree<ELEMENT extends Comparable<ELEMENT>> {
  10.  
  11.     protected class AVLNode<ELEMENT> {
  12.         public ELEMENT item;
  13.         public AVLNode<ELEMENT> left;
  14.         public AVLNode<ELEMENT> right;
  15.         public int balance;
  16.  
  17.         public AVLNode() {
  18.             this(null, null, null, 0);
  19.         }
  20.         public AVLNode(ELEMENT item) {
  21.             this(item, null, null, 0);
  22.         }
  23.         public AVLNode(ELEMENT item, AVLNode<ELEMENT> left, AVLNode<ELEMENT> right, int balance) {
  24.             this.item = item;
  25.             this.left = left;
  26.             this.right = right;
  27.             this.balance = balance;
  28.         }
  29.  
  30.         @Override
  31.         public String toString() {
  32.             return this.item.toString();
  33.         }
  34.  
  35.         // Método para propósitos académicos
  36.         public void Visit() {
  37.             System.out.printf("%s ", this.item.toString());
  38.         }
  39.     }
  40.  
  41.  
  42.  
  43.     protected AVLNode<ELEMENT> root;
  44.     // atributo para propositos académicos
  45.     protected boolean verbose;
  46.  
  47.     public AVLTree() {
  48.         this.root = null;
  49.         this.verbose = false;
  50.     }
  51.  
  52.     // método para propósitos académicos
  53.     public boolean setVerbose(boolean verbose) {
  54.         this.verbose = verbose;
  55.         return this.verbose;
  56.     }
  57.  
  58.  
  59.     @Override
  60.     public String toString() {
  61.         return toString(this.root);
  62.     }
  63.     protected String toString(AVLNode<ELEMENT> root) {
  64.         StringBuilder sb = new StringBuilder();
  65.         if (root != null) {
  66.             sb.append(root.item.toString());
  67.             //sb.append("[" + root.balance.toString() + "]");
  68.             sb.append((root.balance < 0) ? "[-]" : (root.balance == 0) ? "[.]" : "[+]" );
  69.             if (root.left != null) {
  70.                 sb.append("(" + toString(root.left));
  71.                 if (root.right != null) {
  72.                     sb.append(", " + toString(root.right));
  73.                 }
  74.                 sb.append(")");
  75.             } else {
  76.                 if (root.right != null) {
  77.                     sb.append("(, " + toString(root.right) + ")");
  78.                 }
  79.             }
  80.         }
  81.         return sb.toString();
  82.     }
  83.  
  84.  
  85.     //region Métodos para recorrer el árbol
  86.     public void PreOrder() {
  87.         PreOrder(this.root);
  88.     }
  89.     protected void PreOrder(AVLNode<ELEMENT> root) {
  90.         if (root != null) {
  91.             root.Visit();
  92.             PreOrder(root.left);
  93.             PreOrder(root.right);
  94.         }
  95.     }
  96.  
  97.     public void InOrder() {
  98.         InOrder(this.root);
  99.     }
  100.     protected void InOrder(AVLNode<ELEMENT> root) {
  101.         if (root != null) {
  102.             InOrder(root.left);
  103.             root.Visit();
  104.             InOrder(root.right);
  105.         }
  106.     }
  107.  
  108.     public void PostOrder() {
  109.         PostOrder(this.root);
  110.     }
  111.     protected void PostOrder(AVLNode<ELEMENT> root) {
  112.         if (root != null) {
  113.             PostOrder(root.left);
  114.             PostOrder(root.right);
  115.             root.Visit();
  116.         }
  117.     }
  118.  
  119.     public void DescendingOrder() {
  120.         DescendingOrder(this.root);
  121.     }
  122.     protected void DescendingOrder(AVLNode<ELEMENT> root) {
  123.         if (root != null) {
  124.             DescendingOrder(root.right);
  125.             root.Visit();
  126.             DescendingOrder(root.left);
  127.         }
  128.     }
  129.     //endregion
  130.  
  131.     //region Métodos para contar elementos del árbol
  132.     public int NodeCount() {
  133.         return NodeCount(this.root);
  134.     }
  135.     protected int NodeCount(AVLNode<ELEMENT> root) {
  136.         if (root != null) {
  137.             return 1 + NodeCount(root.left) + NodeCount(root.right);
  138.         }
  139.         return 0;
  140.     }
  141.  
  142.  
  143.     public int LeafCount() {
  144.         return LeafCount(this.root);
  145.     }
  146.     protected int LeafCount(AVLNode<ELEMENT> root) {
  147.         if (root != null) {
  148.             if ( (root.left == null) && (root.right == null) ) {
  149.                 return 1;
  150.             } else {
  151.                 return LeafCount(root.left) + LeafCount(root.right);
  152.             }
  153.         }
  154.         return 0;
  155.     }
  156.  
  157.  
  158.     public int InternalCount() {
  159.         return InternalCount(this.root);
  160.     }
  161.     protected int InternalCount(AVLNode<ELEMENT> root) {
  162.         if (root != null) {
  163.             if ( (root.left == null) && (root.right == null) ) {
  164.                 return 0;
  165.             } else {
  166.                 return 1 + InternalCount(root.left) + InternalCount(root.right);
  167.             }
  168.         }
  169.         return 0;
  170.     }
  171.  
  172.  
  173.     public int MaxLevel() {
  174.         return MaxLevel(this.root);
  175.     }
  176.     protected int MaxLevel(AVLNode<ELEMENT> root) {
  177.         if (root != null) {
  178.             if ( (root.left != null) || (root.right != null) ) {
  179.                 int leftLevel = MaxLevel(root.left);
  180.                 int rightLevel = MaxLevel(root.right);
  181.                 return 1 + Math.max(leftLevel, rightLevel);
  182.             }
  183.             return 0;
  184.         }
  185.         return -1;
  186.     }
  187.  
  188.     public int Height() {
  189.         return MaxLevel() + 1;
  190.     }
  191.     //endregion
  192.  
  193.     //region Métodos para buscar
  194.     public boolean contains(ELEMENT item) {
  195.         return contains(this.root, item);
  196.     }
  197.     private boolean contains(AVLNode<ELEMENT> root, ELEMENT item) {
  198.         if (root == null) {
  199.             return false;
  200.         }
  201.         if (item.compareTo(root.item) < 0) {
  202.             return contains(root.left, item);
  203.         }
  204.         if (item.compareTo(root.item) > 0) {
  205.             return contains(root.right, item);
  206.         }
  207.         return true;
  208.     }
  209.     //endregion
  210.  
  211.     //region Métodos para agregar elementos al árbol
  212.  
  213.     public void add(ELEMENT item) {
  214.         if (this.verbose) {
  215.             System.out.printf("Agrega %s", item.toString());
  216.         }
  217.  
  218.         boolean[] change = { false };
  219.         this.root = addAVL(this.root, item, change);
  220.  
  221.         if (this.verbose) {
  222.             System.out.printf("\t %s\n", this.toString());
  223.         }
  224.     }
  225.  
  226.     private AVLNode<ELEMENT> addAVL(AVLNode<ELEMENT> root, ELEMENT item, boolean[] change) {
  227.         AVLNode<ELEMENT> n1;
  228.  
  229.         if (root == null) {
  230.             root = new AVLNode<ELEMENT>(item);
  231.             change[0] = true; // cambia el balance
  232.             return root;
  233.         }
  234.  
  235.         if (item.compareTo(root.item) < 0) { // el nuevo elemento es menor
  236.             root.left = addAVL(root.left, item, change); // agrega por la izquierda
  237.             if (change[0]) { // cambió el balance?
  238.                 switch (root.balance) { // balance = hD - hI
  239.                     case 1: // antes izquierda < derecha
  240.                         root.balance = 0; // después izquierda == derecha
  241.                         change[0] = false; // balance ajustado
  242.                         break;
  243.                     case 0: // antes izquierda == derecha
  244.                         root.balance = -1; // después izquierda > derecha
  245.                         break;
  246.                     case -1: // antes izquierda > derecha
  247.                         n1 = root.left;
  248.                         if (n1.balance == -1) { // izquierda izquierda es mayor
  249.                             root = leftleftRotation(root, n1); // LR rotación doble
  250.                         } else {
  251.                             root = leftrightRotation(root, n1); // LL rotación simple
  252.                         }
  253.                         change[0] = false; // balance ajustado
  254.                         break;
  255.                 }
  256.             }
  257.             return root;
  258.         }
  259.  
  260.         if (item.compareTo(root.item) > 0) { // el nuevo elemento es mayor
  261.             root.right = addAVL(root.right, item, change); // agregar por la derecha
  262.             if (change[0]) { // cambió el balance?
  263.                 switch (root.balance) { // balance = hD - hI
  264.                     case -1: // antes izquierda > derecha
  265.                         root.balance = 0; // ahora izquierda == derecha
  266.                         change[0] = false; // balance ajustado
  267.                         break;
  268.                     case 0: // antes izquierda == derecha
  269.                         root.balance = 1; // ahora izquierda < derecha
  270.                         break;
  271.                     case 1: // antes izquierda < derecha
  272.                         n1 = root.right;
  273.                         if (n1.balance == 1) { // derecha derecha es mayor
  274.                             root = rightrightRotation(root, n1); // RR rotación simple
  275.                         } else {
  276.                             root = rightleftRotation(root, n1); // RL rotación doble
  277.                         }
  278.                         change[0] = false; // balance ajustado
  279.                         break;
  280.                 }
  281.             }
  282.             return root;
  283.         }
  284.         throw new RuntimeException("Claves repetidas");
  285.     }
  286.     //endregion
  287.  
  288.     //region Rotaciones LL LR RR RL
  289.     private AVLNode<ELEMENT> leftleftRotation(AVLNode<ELEMENT> n, AVLNode<ELEMENT> n1) {
  290.         if (this.verbose) {
  291.             System.out.print(" LL ");
  292.         }
  293.  
  294.         n.left = n1.right;
  295.         n1.right = n;
  296.         if (n1.balance == -1) {
  297.             n.balance = 0;
  298.             n1.balance = 0;
  299.         } else {
  300.             n.balance = -1;
  301.             n1.balance = 1;
  302.         }
  303.         return n1;
  304.     }
  305.  
  306.     private AVLNode<ELEMENT> leftrightRotation(AVLNode<ELEMENT> n, AVLNode<ELEMENT> n1) {
  307.         if (this.verbose) {
  308.             System.out.print(" LR ");
  309.         }
  310.  
  311.         AVLNode<ELEMENT> n2;
  312.         n2 = n1.right;
  313.         n.left = n2.right;
  314.         n2.right = n;
  315.         n1.right = n2.left;
  316.         n2.left = n1;
  317.         n1.balance = (n2.balance == 1) ? -1 : 0;
  318.         n.balance = (n2.balance == -1) ? 1 : 0;
  319.         n2.balance = 0;
  320.         return n2;
  321.     }
  322.  
  323.     private AVLNode<ELEMENT> rightrightRotation(AVLNode<ELEMENT> n, AVLNode<ELEMENT> n1) {
  324.         if (this.verbose) {
  325.             System.out.print(" RR ");
  326.         }
  327.  
  328.         n.right = n1.left;
  329.         n1.left = n;
  330.         if (n1.balance == 1) {
  331.             n.balance = 0;
  332.             n1.balance = 0;
  333.         } else {
  334.             n.balance = 1;
  335.             n1.balance = -1;
  336.         }
  337.         return n1;
  338.     }
  339.  
  340.  
  341.     private AVLNode<ELEMENT> rightleftRotation(AVLNode<ELEMENT> n, AVLNode<ELEMENT> n1) {
  342.         if (this.verbose) {
  343.             System.out.print(" RL ");
  344.         }
  345.  
  346.         AVLNode<ELEMENT> n2;
  347.         n2 = n1.left;
  348.         n.right = n2.left;
  349.         n2.left = n;
  350.         n1.left = n2.right;
  351.         n2.right = n1;
  352.         n.balance = (n2.balance == 1) ? -1: 0;
  353.         n1.balance = (n2.balance == -1) ? 1 : 0;
  354.         n2.balance = 0;
  355.         return n2;
  356.     }
  357.     //endregion
  358.  
  359.     //region Métodos para remover elementos
  360.  
  361.     public void remove(ELEMENT item) {
  362.         if (this.verbose) {
  363.             System.out.printf("Extrae %s", item.toString());
  364.         }
  365.  
  366.         boolean[] change = { false };
  367.         this.root = removeAVL(this.root, item, change);
  368.  
  369.         if (this.verbose) {
  370.             System.out.printf("\t %s\n", this.toString());
  371.         }
  372.     }
  373.     private AVLNode<ELEMENT> removeAVL(AVLNode<ELEMENT> root, ELEMENT item, boolean[] change) {
  374.  
  375.         if (root == null) {
  376.             throw new RuntimeException("No existe");
  377.         }
  378.  
  379.         if (item.compareTo(root.item) < 0) { // el elemento es menor
  380.             root.left = removeAVL(root.left, item, change); // borrar por la izquierda
  381.             if (change[0]) { // cambió el balance?
  382.                 root = leftBalance(root, change); // ajustar el balance izquierdo
  383.             }
  384.             return root;
  385.         }
  386.  
  387.         if (item.compareTo(root.item) > 0) { // el elemento es mayor
  388.             root.right = removeAVL(root.right, item, change); // borrar por la derecha
  389.             if (change[0]) { // cambió el balance?
  390.                 root = rightBalance(root, change); // ajustar el balance derecho
  391.             }
  392.             return root;
  393.         }
  394.  
  395.  
  396.         AVLNode<ELEMENT> q;
  397.         q = root;
  398.         if (q.left == null) { // no hay izquierda
  399.             root = q.right; // un descendiente por la derecha u hoja
  400.             change[0] = true; // cambia el balance
  401.         } else {
  402.             if (q.right == null) { // no hay derecha
  403.                 root = q.left; // un descendiente por la izquierda
  404.                 change[0] = true; // cambia el balance
  405.             } else { // dos descendientes !!!
  406.                 root.left = eldestOfMinors(root, root.left, change); // mayor de los menores
  407.                 if (change[0]) { // cambió el balance?
  408.                     root = leftBalance(root, change); // ajustar el balance izquierdo
  409.                 }
  410.                 q = null; // eliminar el nodo
  411.             }
  412.         }
  413.         return root;
  414.     }
  415.  
  416.     private AVLNode<ELEMENT> eldestOfMinors(AVLNode<ELEMENT> n, AVLNode<ELEMENT> eldest, boolean[] change) {
  417.         if (eldest.right != null) { // hay algo a la derecha
  418.             eldest.right = eldestOfMinors(n, eldest.right, change); // busca el mayor de los menores
  419.             if (change[0]) { // cambió el balance?
  420.                 eldest = rightBalance(eldest, change); // ajustar el balance derecho
  421.             }
  422.         } else {
  423.             n.item = eldest.item;
  424.             n = eldest;
  425.             eldest = eldest.left;
  426.             n = null;
  427.             change[0] = true;
  428.         }
  429.         return eldest;
  430.     }
  431.  
  432.     private AVLNode<ELEMENT> leftBalance(AVLNode<ELEMENT> n, boolean[] change) {
  433.         AVLNode<ELEMENT> n1;
  434.         switch (n.balance) { // balance = hD - hI
  435.             case -1 : // antes izquierda > derecha
  436.                 n.balance = 0; // ahora izquierda == derecha
  437.                 break;
  438.             case 0 : // antes izquierda == derecha
  439.                 n.balance = 1; // ahora izquierda < derecha
  440.                 change[0] = false; // balance ajustado
  441.                 break;
  442.             case 1 : // antes izquierda < derecha
  443.                 n1 = n.right;
  444.                 if (n1.balance >= 0) {
  445.                     if (n1.balance == 0) {
  446.                         change[0] = false; // balance ajustado
  447.                     }
  448.                     n = rightrightRotation(n, n1);
  449.                 } else {
  450.                     n = rightleftRotation(n, n1);
  451.                 }
  452.                 break;
  453.         }
  454.         return n;
  455.     }
  456.  
  457.     private AVLNode<ELEMENT> rightBalance(AVLNode<ELEMENT> n, boolean[] change) {
  458.         AVLNode<ELEMENT> n1;
  459.         switch (n.balance) { // balance = hD - hI
  460.             case -1 : // antes izquiera > derecha
  461.                 n1 = n.left;
  462.                 if (n1.balance <= 0) {
  463.                     if (n1.balance == 0) {
  464.                         change[0] = false; // balance ajustado
  465.                     }
  466.                     n = leftleftRotation(n, n1);
  467.                 } else {
  468.                     n = leftrightRotation(n, n1);
  469.                 }
  470.                 break;
  471.             case 0 : // antes izquierda == derecha
  472.                 n.balance = -1; // ahora izquierda > derecha
  473.                 change[0] = false; // balance ajustado
  474.                 break;
  475.             case 1 : // antes izquierda < derecha
  476.                 n.balance = 0;
  477.                 break;
  478.         }
  479.         return n;
  480.     }
  481.     //endregion
  482.  
  483. }
  484.  
Add Comment
Please, Sign In to add comment