Advertisement
jtentor

DemoTree3 - AVLTree.java

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