/* * Ο κώδικας που ακολουθεί αποτελεί συνοδευτικό υλικό του βιβλίου "Δομές Δεδομένων", 3η Έκδοση, Παναγιώτης Δ. Μποζάνης, * © 2022 Εκδόσεις Τζιόλα, ISBN 978-960-418-986-1 και μπορεί να χρησιμοποιηθεί ελεύθερα για εκπαιδευτικούς λόγους με * αποκλειστική ευθύνη των χρηστών. */ /////////////// Κεφάλαιο 3 --- Βασικές Δομές Δεδομένων ///////////////////// /* Ορισμός κόμβου απλής λίστας */ class SNode{ // η κλάση που περιγράφει το βασικό δομικό στοιχείο μίας λίστας private SNode next; // ο κόμβος μετά private Object element; // το αποθηκευμένο στοιχείο // Constructor public SNode(SNode nodeNext, Object nodeElement){ next = nodeNext; element = nodeElement; } // Πρόσβαση στην Πληροφορία // επιστροφή του στοιχείου public Object getElement() { return element; } // επιστροφή του δείκτη public SNode getNext() { return next; } // Αλλαγή Πληροφορίας // ορισμός του στοιχείου public void setElement(Object newElement) { element = newElement; } // ορισμός του δείκτη public void setNext(SNode newNext) { next = newNext; } }// Τέλος Snode /* Απλή γραμμική λίστα */ public class SinglyNodeList { protected int nofElements; // πλήθος αποθηκευμένων στοιχείων, κόμβων protected SNode head, tail; // δείκτες προς κεφαλή και ουρά // Constructor: χρόνος $Ο(1)$ public SinglyNodeList() { // δημιουργεί μία κενή ουρά nofElements = 0; head = tail = null; // δημιουργία κεφαλής και ουράς } // Απλοί μέθοδοι αντλήσεως πληροφορίας... public int size() { // χρόνος $O(1)$ return nofElements; } public boolean isEmpty() { // χρόνος $O(1)$ return (nofElements < 1); } public boolean isFirst(SNode v) { // εξετάζει εάν ο $v$ είναι ο πρώτος κόμβος return v == head; // χρόνος $O(1)$ } public SNode first() { // επιστρέφει τον πρώτο κόμβο if (isEmpty()) // χρόνος $O(1)$ System.out.println("Η λίστα είναι άδεια..."); return head; } public SNode last(){ // επιστρέφει τον τελευταίο κόμβο if (isEmpty()) // χρόνος $O(1)$ System.out.println("Η λίστα είναι άδεια..."); return tail; } }// Τέλος SinglyNodeList /* Ένθεση μετά από ένα στοιχείο, δοθέντος του δείκτη του $p$ */ public SNode insertAfter(SNode p, Object element){ // χρόνος $O(1)$ if (isEmpty()){ System.out.println("Ανεπίτρεπτη η εφαρμογή σε άδεια λίστα"); return null; } nofElements++; SNode q = new SNode(p.getNext(), element); if (p.getNext() == null) // θέλουμε να προσθέσουμε έναν κόμβο στο τέλος tail = q; p.setNext(q); return q; } /* Ένθεση νέου πρώτου στοιχείου */ public SNode insertFirst(Object element){ // χρόνος $O(1)$ SNode q = new SNode(head, element); head = q; if (++nofElements == 1) tail = head; return q; } /* Απόσβεση επόμενου στοιχείου */ public Object deleteAfter(SNode p){ // Χρόνος $O(1)$ if (p == tail) { System.out.println ("Αδύνατη η απόσβεση στο τέλος"); return null; } SNode pNext = p.getNext(); // Βοηθητικός δείκτης στον επόμενο του $p$ nofElements--; p.setNext(pNext.getNext()); if (pNext == tail) // Σβήσιμο του τελευταίου κόμβου tail = p; // Πρέπει να ενημερωθεί η ουρά pNext.setNext(null); // Απομόνωση με ((γείωση)) του δείκτη του $p$ return pNext.getElement(); // Το αποθηκευμένο στοιχείο του κόμβου } /* Συνένωση με άλλη λίστα. Στην γενική περίπτωση, η παλιά ουρά θα δείχνει στο πρώτο στοιχείο της $s$ ενώ νέα ουρά θα γίνει η ουρά της $s$. Εάν η λίστα μας είναι άδεια, τότε παίρνει τα περιεχόμενα της $s$ */ public void catenate(SinglyNodeList s){ if (s.isEmpty()) return; if (tail== null) tail = s.first(); else tail.setNext(s.first()); if (isEmpty()) head = tail; tail = s.last(); nofElements += s.size(); s.setEmpty(); // άδειασμα της $s$ } // άδειασμα μίας λίστας public void setEmpty(){ head = tail = null; nofElements = 0; } /* Ορισμός κόμβου διπλής λίστας */ class DNode{ private DNode prev, next; // οι κόμβοι πριν και μετά private Object element; // το αποθηκευμένο στοιχείο // Constructor public DNode(DNode nodePrev, DNode nodeNext, Object nodeElement){ prev = nodePrev; next = nodeNext; element = nodeElement; } // Πρόσβαση στην Πληροφορία // επιστροφή του στοιχείου public Object getElement() { return element; } // επιστροφή του προηγούμενου κόμβου public DNode getPrev() { return prev; } // επιστροφή του επόμενου κόμβου public DNode getNext() { return next; } // Αλλαγή Πληροφορίας // ορισμός στοιχείου public void setElement(Object newElement) { element = newElement; } // ορισμός προηγούμενου δείκτη public void setPrev(DNode newPrev) { prev = newPrev; } // ορισμός επόμενου δείκτη public void setNext(DNode newNext) { next = newNext; } }// Τέλος Dnode /* Ορισμός διπλής λίστας */ public class DoublyNodeList { protected int nofElements; // πλήθος αποθηκευμένων στοιχείων, κόμβων protected DNode head, tail; // δείκτες προς κεφαλή και ουρά // Constructor ---χρόνος $Ο(1)$ public NodeList() { nofElements = 0; head = new DNode(null, null, null); // δημιουργία κεφαλής tail = new DNode(head, null, null); // δημιουργία ουράς head.setNext(tail); // στην αρχή η κεφαλή δείχνει την ουρά } // Απλοί Μέθοδοι Αντλήσεως Πληροφορίας // μέγεθος public int size() { // χρόνος $O(1)$ return nofElements; } // κενότητα public boolean isEmpty() { // χρόνος $O(1)$ return (nofElements < 1); } // πρωτιά κόμβου public boolean isFirst(DNode v) { // χρόνος $O(1)$ return (v.getPrev() == head); } // επιστροφή του πρώτου κόμβου σε χρόνο $O(1)$ public DNode first() { if (isEmpty()) { System.out.println("Η λίστα είναι άδεια..."); return head; } else return head.getNext(); } // επιστροφή του τελευταίου κόμβου σε χρόνο $O(1)$ public DNode last(){ if (isEmpty()){ System.out.println ("Η λίστα είναι άδεια..."); return tail; } else return tail.getPrev(); } // Τέλος DoublyNodeList /* Ένθεση πριν σε διπλή λίστα */ public DNode insertBefore(DNode p, Object element){ // χρόνος $O(1)$ nofElements++; if (p == head) { // χρειάζεται λίγο παραπάνω προσοχή, καθώς ο $q$ θα γίνει // ο νέος πρώτος κόμβος DNode q = new DNode(head, head.getNext(), element); head.getNext().setPrev(q); head.setNext(q); } else { DNode q = new DNode(p.getPrev(), p, element); p.getPrev().setNext(q); p.setPrev(q); } return q; } /* Ένθεση μετά σε διπλή λίστα */ public DNode insertAfter(DNode p, Object element){ // χρόνος $O(1)$ nofElements++; if (p == tail) { // χρειάζεται λίγο παραπάνω προσοχή DNode q = new DNode(tail.getPrev(), tail, element); tail.getPrev().setNext(q); tail.setPrev(q); } else { DNode q = new DNode(p, p.getNext(), element); p.getNext().setPrev(q); p.setNext(q); } return q; } /* Απόσβεση σε διπλή λίστα */ public Object delete(DNode p){ // χρόνος $O(1)$ if (p == head)||(p == tail) { System.out.println ("Αδύνατη η απόσβεση κεφαλής ή ουράς"); return null; } nofElements--; DNode pPrev = p.getPrev(); // βοηθητικός δείκτης στον προηγούμενο του $p$ DNode pNext = p.getNext(); // βοηθητικός δείκτης στον επόμενο του $p$ pPrev.setNext(pNext); pNext.setPrev(pPrev); p.element(); // το αποθηκευμένο στοιχείο του κόμβου // ((γείωση)) των δεικτών του $p$, ώστε να απομονωθεί... p.setNext(null); p.setPrev(null); return p.getElement(); // το αποθηκευμένο στοιχείο του κόμβου } /* Υλοποίηση στοίβας με την βοήθεια πίνακα */ public class ArrayStack { public static final int defaultCapacity = 1000; // η ερήμην χωρητικότητα private int capacity; // η χωρητικότητα της στοίβας private Object STACK[]; // ο πίνακας που θα ((στεγάσει)) τα στοιχεία private int top = -1; // η κορυφαία θέση, $-1$ όταν η στοίβα είναι άδεια public ArrayStack() { // αρχικοποίηση με την ερήμην χωρητικότητα this(defaultCapacity); // επομένως η στοίβα μας μπορεί να φιλοξενήσει μέχρι } // $defaultCapacity$ αντικείμενα public ArrayStack(int cap) { // αρχικοποίηση με την επιθυμητή χωρητικότητα $cap$ capacity = cap; // επομένως η στοίβα μας μπορεί να φιλοξενήσει STACK = new Object[cap]; // μέχρι $cap$ αντικείμενα } public int size() { return (top + 1); } public boolean isEmpty() { return (top < 0); } public void push(Object obj) { if (size() == capacity){ System.out.println("Υπερχείλιση στοίβας"); return; } STACK[++top] = obj; } public Object top(){ if (isEmpty()){ System.out.println("Άδεια στοίβα"); return; } return STACK[top]; } public Object pop(){ Object elem; if (isEmpty()){ System.out.println("Άδεια στοίβα"); return; } elem = STACK[top]; STACK[top--] = null; // ((γείωση)) του παλαιού κορυφαίου στοιχείου return elem; } }// Τέλος ArrayStack /* Υλοποίηση στοίβας με απλή λίστα */ public class LinkedStack{ private SNode top; // αναφορά προς τον κορυφαίο κόμβο private int size; // πλήθος στοιχείων της στοίβας public LinkedStack() { // αρχικοποιεί μία άδεια στοίβα top = null; size = 0; } public int size() { return size; } public boolean isEmpty() { return (size < 1); } public void push(Object elem) { // χρόνος $Ο(1)$ SNode x = new SNode(top, elem); // δημιουργία του νέου κόμβου top = x; size++; } public Object pop(){ // χρόνος $Ο(1)$ Snode oldtop; if (isEmpty()){ System.out.println("Η στοίβα είναι άδεια..."); return null; } oldtop = top; top = top.getNext(); // το νέο στοιχείο oldtop.setNext(null); // γείωση size--; return oldtop.getElement(); // επιστροφή στοιχείου της παλιάς κορυφής } public Object top(){ // χρόνος $Ο(1)$ if (isEmpty()){ System.out.println("Η στοίβα είναι άδεια..."); return null; } return top.getElement(); } }// Τέλος της LinkedStack /* Υλοποίηση FIFO με λίστα */ public class FIFO { protected int nofElements; // πλήθος αποθηκευμένων στοιχείων,κόμβων protected SNode head, rear; // δείκτες προς κεφαλή και ουρά // Constructor: χρόνος $Ο(1)$ public FiFo() { nofElements = 0; head =null // δημιουργία κεφαλής rear = null; // δημιουργία ουράς } // Απλοί μέθοδοι αντλήσεως πληροφορίας public int size() { // χρόνος $O(1)$ return nofElements; } public boolean isEmpty() { // χρόνος $O(1)$ return (nofElements < 1); } public void enqueue(Object obj) { // προσθήκη στο τέλος ενός νέου κόμβου SNode x = new SNode(null, obj); if (isEmpty()) // η ουρά μας είναι αρχικώς άδεια head = x; else // ο νέος κόμβος θα προστεθεί στο τέλος rear.setNext(x); rear = x; // ενημέρωση της νέας ουράς size++; // προσαρμογή μεγέθους } public Object dequeue(){ // αφαίρεση του πρώτου κόμβου SNode temp; if (isEmpty()){ System.out.println("Η ουρά είναι άδεια..."); return; } temp = head; head = head.getNext(); temp.setNext(null); size--; if (size == 0) rear = null; // η ουρά είναι πλέον άδεια return temp.getElement(); } // επιστροφή του κορυφαίου στοιχείου δίχως αφαίρεσή του public SNode first() { if (isEmpty()) // χρόνος $O(1)$ System.out.println("Η λίστα είναι άδεια..."); return head.getElement(); } }// Τέλος FIFO /* Υλοποίηση dequeue */ public class Dequeue { DNode head, rear; // οι γνωστοί κόμβοι-οριοθέτες int size; // πλήθος στοιχείων public Dequeue() { // αρχικοποίηση head = new DNode(null, null, null); // οι γνωστές αρχικοποιήσεις rear = new DNode(head, null,null); // ώστε το τέλος να δείχνει την κορυφή head.setNext(rear); // και αντιστρόφως size = 0; } public Boolean isEmpty(){ return (size < 1); } public Object pop(){ if (isEmpty()){ System.out.println("H διπλοουρά είναι κενή"); return; } DNode first = head.getNext(); // ο πρώτος κόμβος DNode second = first.getNext(); // ο δεύτερος head.setNext(second); // ο οποίος γίνεται πρώτος second.setPrev(head); first.setNext(null); first.setPrev(null); // γείωση size--; // προσαρμογή του μεγέθους return first.getElement(); // επιστροφή του στοιχείου της παλιάς κεφαλής } public void push(Object o) { DNode second = head.getNext(); // ο κορυφαίος που θα γίνει δεύτερος DNode first = new DNode(head, second, o); // ο νέος κορυφαίος second.setPrev(first); // ο νέος δεύτερος προς τον νέο πρώτο head.setNext(first); // η κορυφή προς τον πρώτο size++; } public Object eject(){ if (isEmpty()){ System.out.println("H διπλοουρά είναι κενή"); return; } DNode last = rear.getPrev(); // ο τελευταίος κόμβος DNode secondtolast = last.getPrev(); // ο δεύτερος πριν το τέλος rear.setPrev(secondtolast); // ο οποίος γίνεται τελευταίος secondtolast.setNext(rear); last.setPrev(null); last.setNext(null); // γείωση size--; // προσαρμογή του μεγέθους return last.getElement(); // επιστροφή του στοιχείου του παλιού τέλους } public void inject(Object o) { DNode secondtolast = rear.getPrev(); // ο τελευταίος που θα γίνει προτελευταίος DNode last = new DNode(rear, secondtolast, o); // ο νέος τελευταίος secondtolast.setNext(last); // ο νέος προτελευταίος προς τον νέο τελευταίο rear.setPrev(last); // η ουρά προς τον νέο τελευταίο size++; // προσαρμογή του μεγέθους } public Object first(){ // ανάκτηση, δίχως αφαίρεση, του κορυφαίου στοιχείου if (isEmpty()){ System.out.println("H διπλοουρά είναι κενή"); return; } return head.getNext().getElement(); } public Object last(){ // ανάκτηση, δίχως αφαίρεση, του τελευταίου στοιχείου if (isEmpty()){ System.out.println("H διπλοουρά είναι κενή"); return; } return rear.getPrev().getElement(); } }// Τέλος Dequeue /* Ορισμός κόμβου δυαδικού δένδρου */ public class BTNode{ private Object element; // το στεγαζόμενο στοιχείο private BTNode left, right, parent; // οι τρεις δείκτες public BTNode() { } // απλός $constructor$ // σύνθετος constructor με πλήρη καθορισμό των περιεχομένων του νέου κόμβου public BTNode(Object o, BTNode u, BTNode v, BTNode w) { setElement(o); setParent(u); setLeft(v); setRight(w); } public Object element() { // επιστρέφει το στοιχείο return element; } public void setElement(Object o) { // θέτει το αποθηκευμένο στοιχείο element=o; } public BTNode getLeft() { // επιστρέφει τον δείκτη προς το αριστερό παιδί return left; } public void setLeft(BTNode v) { // θέτει τον δείκτη προς το αριστερό παιδί left=v; } public BTNode getRight() { // επιστρέφει τον δείκτη προς το δεξιό παιδί return right; } public void setRight(BTNode v) { // θέτει τον δείκτη προς το δεξιό παιδί right=v; } public BTNode getParent() { // επιστρέφει τον δείκτη προς τον πατέρα return parent; } public void setParent(BTNode v) { // θέτει τον δείκτη προς τον πατέρα parent=v; } }// Τέλος BTNode /* Δυαδικό διασυνδεδεμένο δένδρο */ public class LinkedBinaryTree { private BTNode Root; // η ρίζα του δένδρου private int size; // πλήθος κόμβων static boolean Left = true; // ορισμός του αριστερού static boolean Right = false; // ορισμός του δεξιού public LinkedBinaryTree(){ // constructor #1 Root=null; size=0; } public LinkedBinaryTree(BTNode o){ // constructor #2 Root=o; } public LinkedBinaryTree(Object o){ // constructor #3 Root=new BTNode(o, null, null, null); size=1; } public int size() { // επιστρέφει το μέγεθος του δένδρου return size; } public void setSize(int s){ size=s; } public BTNode root() { // επιστρέφει την ρίζα του δένδρου return Root; } public void setRoot(BTNode v){ Root=v; } public boolean isRoot(BTNode v) { // εξετάζει εάν ο κόμβος $v$ είναι ρίζα return (v == Root); } public boolean isLeft(BTNode v) { // εξετάζει εάν ο κόμβος $v$ είναι αριστερό παιδί if (v == Root) { System.out.println("Είσαι στην ρίζα"); return false; } return (v == v.getParent().getLeft()); } public boolean isRight(BTNode v) { // εξετάζει εάν ο κόμβος $v$ είναι δεξιό παιδί if (v == Root) { System.out.println("Είσαι στην ρίζα"); return false; } return (v == v.getParent().getRight()); } // ανταλλάσσει τα περιεχόμενα των κόμβων $v, w$ public void exchangeElements(BTNode v, BTNode w){ Object temp=v.getElement(); v.setElement(w.getElement()); w.setElement(temp); } public BTNode getSibling(BTNode v){ // επιστρέφει τον αδελφό του $v$, εάν υπάρχει if ((v==null) || isRoot(v)){ System.out.println("Δεν υπάρχει αδελφός..."); return null; } if (isRight(v)) return v.getParent().getLeft(); else return v.getParent().getRight(); } }// Τέλος LinkedBinaryTree /* Ορισμός κόμβου $k$-ικού δένδρου */ public class TNode{ private Object element; private TNode parent; private TNode[] sons; private int nofSons; public TNode() { } // απλός constructor public TNode(Object o, TNode p, int nofsons) {// σύνθετος setElement(o); setParent(p); sons = new Tnode[nofsons]; nofSons = nofsons; } public Object element() { // επιστρέφει το αποθηκευμένο στοιχείο return element; } public void setElement(Object o) { // θέτει το αποθηκευμένο στοιχείο element = o; } public TNode getSon(int i) { // επιστρέφει τον δείκτη προς το $i$-στο παιδί if (i > nofsons-1) { System.out.println("Δεν υπάρχει τέτοιος γιος..."); return null; } return sons[i]; } // θέτει τον δείκτη προς το $i$-στο παιδί ίσο με $v$ public boolean setSon(int i, TNode v) { if (i > nofsons-1) { System.out.println("Δεν υπάρχει τέτοιος γιος..."); return false; } sons[i] = v; return true; } public TNode getParent() { // επιστρέφει τον δείκτη προς τον πατέρα return parent; } public void setParent(TNode v) { // θέτει τον δείκτη προς τον πατέρα ίσο με $v$ parent = v; } } // Τέλος TNode /* Προσθήκη παιδιού σε δυναμικό δυαδικό δένδρο */ public void addLeaf(BTNode v, boolean kindofson) { if (kindofson == Left) { // ένθεση στον $v$ αριστερού παιδιού if (v.getLeft() != null) { // υπάρχει ήδη μη κενό αριστερό παιδί System.out.println("Υπάρχει τέτοιο παιδί!"); return; } v.setLeft(new BTNode(null, v, null, null)); // ένθεση του νέου κόμβου } else { // αιτείται ένθεση δεξιού παιδιού if (v.getRight() != null) { // Υπάρχει τέτοιο παιδί System.out.println("Υπάρχει τέτοιο παιδί!"); return; } v.setRight(new BTNode(null, v, null, null)) // ένθεση του νέου κόμβου } size++; // ενημέρωση του μεγέθους του δένδρου } /* Διαγραφή κόμβου σε δυναμικό δυαδικό δένδρο */ public void deleteNode(BTNode v) { if ((v.getLeft() != null) && (v.getRight() != null) { // αδύνατη η απόσβεση System.out.println("Δεν γίνεται απόσβεση"); // υπάρχουν δύο παιδιά return; } if (isRoot(v)) { // χρειάζεται λιγάκι προσοχή BTNode notNullSonofv = (v.getLeft()!=null ? v.getLeft() : v.getRight()); Root = NotNullSonofv; // θα γίνει η νέα ρίζα if (Root != null) Root.setParent(null); // οπότε δεν έχει πατέρα! } else { // δεν είναι ρίζα... BTNode parentΟfv = v.getParent(); // οπότε έχει πατέρα... BTNode notNullSonofv = (v.getLeft()!=null ? v.getLeft() : v.getRight()); if (isLeft(v)) // ο $v$ είναι αριστερός γιος parentOfv.setLeft(notNullSonofv); else // ο $v$ είναι δεξιός γιος parentOfv.setRight(notNullSonofv); if (notNullSonofv != null) notNullSonofv.setParent(parentOfv); // αλλαγή πατρός... } size--; // ενημέρωση μεγέθους δένδρου v.setLeft(null); v.setRight(null); v.setParent(null); // γείωση του $v$ lastDeletedElement = v.getElement(); // αποθήκευση του σβησμένου στοιχείου } // για τυχούσα χρήση... /////////////// Κεφάλαιο 4 --- Εισαγωγή στην Ταξινόμηση /////////////////////// /* Μη αναδρομικό δυαδικό ψάξιμο */ static int binarySearch(Object a[], Object o, comparator c) { int left = 0; // αριστερό όριο int right = a.length-1; // δεξιό όριο while (right >= left) { // όσο δεν ταυτίστηκαν τα όρια int middle = (left+right)/2; // το μεσαίο όριο if (c.equal(o,a[middle])) // το βρήκαμε... return middle; // επιστρέφουμε την θέση του αντικειμένου if (c.less(o,a[middle])) // θα ψάξουμε στο αριστερό τμήμα, right = middle-1; // οπότε προσαρμόζουμε το δεξιό όριο else // θα ψάξουμε στο δεξιό τμήμα, left = middle+1; // οπότε προσαρμόζουμε το αριστερό όριο } return -1; // το αντικείμενό μας δεν βρέθηκε } /* Κλάση συγκριτή για ακεραίους */ static class comparator { boolean less(Object i,Object j){ return (((Integer) i).intValue() < ((Integer) j).intValue()); } boolean equal(Object i, Object j ){ return (((Integer) i).intValue() == ((Integer) j).intValue()); } } ///////////// Κεφάλαιο 5 --- Συγκριτικοί Αλγόριθμοι Ταξινομήσεως /////////////////// /* Ταξινόμηση εισαγωγής: ταξινομεί τον πίνακα μεταξύ του $left$ και $right$, χρησιμοποιώντας την κλάση $c$ για τις συγκρίσεις */ static void insertionSort(Object a[], int left, int right, comparator c){ for (int i = right; i > left; i--) // κάθοδος του μικρότερου στοιχείου if (c.less(a[i],a[i-1])) { // στην αριστερότερη θέση με ανταλλαγές Object temp = a[i]; a[i] = a[i-1]; a[i-1] = temp; } for (int i = left+2; i <= right; i++){ // το στοιχείο $i$ πρέπει να μπει στην int j = i; // σωστή θέση στα αριστερά του Object v = a[i]; // το $i$-στο στοιχείο while (c.less(v,a[j-1])){ // αναζήτηση πού πρέπει να μπει a[j] = a[j-1]; j--; } a[j] = v; // τοποθέτηση στην σωστή θέση } }// Τέλος insertionsort /* Ταξινόμηση επιλογής: ταξινομεί τον πίνακα μεταξύ του $left$ και $right$, χρησιμοποιώντας την κλάση $c$ για τις συγκρίσεις */ static void selectionSort(Object[] a, int left, int right, comparator c) { Object temp; for (int unorderedleft = left; unorderedleft < right; unorderedleft++){ int min = unorderdedleft; for (int j = unorderedleft+1; j <= right; j++) // εύρεση του ελαχίστου if (c.less(a[j], a[min])) min = j; temp = a[unorderedleft]; // ανταλλαγή του ελαχίστου με το αριστερό a[unorderedleft] = a[min]; // όριο του αταξινόμητου τμήματος a[min] = temp; } }// Τέλος selectionsort /* Ταξινόμηση φυσσαλίδας: ταξινομεί τον πίνακα μεταξύ του $left$ και $right$, χρησιμοποιώντας την κλάση $c$ για τις συγκρίσεις */ static void bubbleSort(Object a[], int left, int right, comparator c){ Object temp; for (int i = left; i < right; i++) // η θέση $i$ αποτελεί το αριστερό όριο του for (int j = right; j > i; j--) // αταξινόμητου τμήματος if (c.less(a[j],a[j-1])){ // είναι εκτός διατάξεως, temp = a[j-1]; // οπότε τα ανταλλάσσουμε... a[j-1] = a[j]; a[j] = temp; } }// Τέλος bubblesort /* Ταξινόμηση αναμικτήρα: ταξινομεί τον πίνακα μεταξύ του $left$ και $right$ χρησιμοποιώντας την κλάση $c$ για τις συγκρίσεις. Χρησιμοποιεί την απλή εκδοχή του bubble sort */ static void shakerSort(Object a[], int left, int right, comparator c){ Object temp; boolean leftdirection = true; // σημαία κατευθύνσεως αλγορίθμου while (left < right){ // όσο ο πίνακας δεν έχει // διαταχθεί πλήρως if (leftdirection){ // ((ανάμειξη)) προς τα αριστερά leftdirection = !leftdirection; // αλλαγή της σημαίας for (int j = right; j > left; j--) // $bubblesort$ προς τα αριστερά if (c.less(a[j],a[j-1])){ temp = a[j-1]; a[j-1] = a[j]; a[j] = temp; } left++; // ενημέρωση του αριστερού ορίου } else { // ((ανάμειξη)) προς τα δεξιά... leftdirection = !leftdirection; // αλλαγή της σημαίας for (int j = left; j < right; j++) // $bubblesort$ προς τα δεξιά if (c.less(a[j+1],a[j])){ temp = a[j+1]; a[j+1] = a[j]; a[j] = temp; } right--; // ενημέρωση του δεξιού ορίου } } }// Τέλος shakerSort /* Ταχεία Ταξινόμηση -αναδρομική υλοποίηση: ταξινομεί τον πίνακα μεταξύ του $left$ και $right$, χρησιμοποιώντας την κλάση $c$ για τις συγκρίσεις */ static void quickSort(Object a[], int left, int right, comparator c){ int i = left-1, j = right; Object temp, o = a[right]; // το στοιχείο διαχωρισμού while (true){ // εύρεση της θέσεως $i$ όπου θα εντεθεί το στοιχείο διαχωρισμού while (c.less(a[++i], o)) // ανεβαίνει ο δείκτης $i$; θα σταματήσει είτε όταν ; // ανακαλύψει στοιχείο μεγαλύτερο του $a[right]$ είτε // όταν φθάσει στην θέση $right$ while (c.less(o,a[--j])) // κατεβαίνει ο δείκτης $j$; θα σταματήσει είτε όταν if (j == left) // ανακαλύψει στοιχείο μεγαλύτερο του $a[right]$ break; // είτε όταν φθάσει στην θέση $left$ if (i >= j) // οι δείκτες συναντήθηκαν ή πέρασαν στο άλλο τμήμα break; temp = a[i]; // ανταλλαγή των αντικειμένων στις θέσεις $i,j$ a[i] = a[j]; a[j] = temp; } temp = a[i]; // το στοιχείο διαχωρισμού $a[right]$ μεταφέρεται a[i] = a[right]; // στην θέση $i$ a[right] = temp; // αναδρομική ταξινόμηση των δύο τμημάτων εκατέρωθεν του $i$ if (left < i-1) // έχει νόημα η κλήση quickSort(a, left, i-1, c); if (i+1< right) // έχει νόημα η κλήση quickSort(a, i+1, right, c); } /* Ταχεία Ταξινόμηση -μη αναδρομική υλοποίηση με χρήση στοίβας: ταξινομεί τον πίνακα μεταξύ του $left$ και $right$ χρησιμοποιώντας την κλάση $c$ για τις συγκρίσεις ---μη αναδρομική υλοποίηση με χρήση στοίβας */ static void stackQuickSort(Object a[], int left, int right, comparator c){ LinkedStack MyStack=new LinkedStack(); int i = left-1, j = right; Object o = a[right], temp; MyStack.push(new Integer(right)); MyStack.push(new Integer(left)); while (!MyStack.isEmpty()){ left = ((Integer) MyStack.pop()).intValue(); //το αριστερό και right = ((Integer) MyStack.pop()).intValue(); //το δεξιό όριο του τμήματος if (right <= left) // μηδενικό μήκος τμήματος να διατάξουμε... continue; // προχωρούμε στο επόμενο // ο γνωστός κώδικας τοποθετήσεως του στοιχείου διαμερισμού while (true){ // εύρεση θέσεως $i$ όπου θα τοποθετηθεί το στοιχείο διαχωρισμού while (c.less(a[++i],o)) ; // ανεβαίνει ο δείκτης $i$ while (c.less(o,a[--j])) // κατεβαίνει ο δείκτης $j$ if (j == left) break; if (i >= j) // οι δείκτες συναντήθηκαν ή προσπεράστηκαν break; temp = a[i]; // ανταλλαγή των στοιχείων στις θέσεις $i,j$ a[i] = a[j]; a[j] = temp; } temp = a[i]; // το στοιχείο διαχωρισμού $a[right]$ μεταφέρεται a[i] = a[right]; a[right] = temp; // βάζουμε στην στοίβα τα δύο τμήματα για ταξινόμηση, ανάλογα με το μέγεθός τους // το μεγαλύτερο μπαίνει πρώτο, ώστε πάντοτε να εξυπηρετείται πιο μπροστά το μικρότερο if (i-left > right-i) { // το αριστερό τμήμα είναι το μεγαλύτερο // τα όρια εισάγονται με αντίθετη σειρά από αυτή που θα εξαχθούν MyStack.push(new Integer(i-1)); MyStack.push(new Integer(left)); MyStack.push(new Integer(right)); MyStack.push(new Integer(i+1)); } else{ // το δεξιό τμήμα είναι το μεγαλύτερο // τα όρια εισάγονται με αντίθετη σειρά από αυτή που θα εξαχθούν MyStack.push(new Integer(right)); MyStack.push(new Integer(i+1)); MyStack.push(new Integer(i-1)); MyStack.push(new Integer(left)); } } }// Τέλος stackQuickSort /* Ταξινόμηση Σωρού: ταξινομεί τον πίνακα μεταξύ του $left$ και $right$, χρησιμοποιώντας την κλάση $c$ για προς συγκρίσεις */ // η $makeHeap$ επανορθώνει την δομή σωρού, βυθίζοντας το στοιχείο της θέσης $k$ όσο // χρειάζεται. Στο τέλος, οι θέσεις $k$ έως $Ν$ ικανοποιούν την σταθερά συνθήκη μεγίστου. static void makeHeap(Object a[], int k, int N, comparator c){ while (2*k+1 <= N ) { int maxson = 2*k+1; // o αριστερός γιος του $k$ Object temp; if (maxson < N && c.less(a[maxson],a[maxson+1])) // ο δεξιός γιος είναι maxson++; // μεγαλύτερος if (c.less(a[maxson],a[k])) // δεν μπορεί να βυθιστεί break; // άλλο temp = a[k]; // διαφορετικά, βυθίζεται... a[k]= a[maxson]; a[maxson]=temp; k = maxson; } }// Τέλος makeHeap // η ουσιαστική μέθοδος ταξινομήσεως, η οποία κάνει χρήση της ανωτέρω μεθόδου static void heapSort(Object a[], int left, int right, comparator c) { int N = right-left, k=(N % 2==0 ? N/2-1 : N/2); // η αρχική θέση Object temp; // χτισίματος σωρού for (; k >= 0; k--) // φάση δομήσεως σωρού makeHeap(a, k, right, c); while (right > 0) { // φάση επιλογής, διαδοχικά παίρνουμε τα temp=a[left]; // στοιχεία από το μεγαλύτερο προς a[left]=a[right]; // το μικρότερο a[right]=temp; makeHeap(a, left,--right, c); // εφ' όσον απομακρύνθηκε το μεγαλύτερο, πρέπει } // να ξαναγίνει σωρός το υπολειπόμενο τμήμα }// Τέλος Heapsort /* Ταξινόμηση Συγχωνεύσεως: ταξινομεί τον πίνακα μεταξύ του $left$ και $right$, χρησιμοποιώντας την κλάση $c$ για τις συγκρίσεις. Χρησιμοποιείται ένας βοηθητικός πίνακας $b$ για την συγχώνευση */ static void mergeSort(Object a[], int left, int right, Object b[], comparator c){ int l, r; int middle = (right+left)/2; // Διαίρει και βασίλευε if (left < middle) // αναδρομική ταξινόμηση του αριστερού μέρους, εάν mergeSort(a, left, middle, b, c); // υφίσταται if (middle+1 -1; curDigit--){ while (!list.isEmpty()){ // κατανομή ως προς το $curDigit$ ψηφίο String temp=(String)list.removeFirst(); // αφαίρεση από την λίστα Bucket[a.getDigit(temp,curDigit)].insertLast(temp); // προσθήκη στον } // κατάλληλο κάδο ως προς το ψηφίο $curDigit$ for (int k = 0; k < Radix; k++) // συνένωση των μη κενών κάδων if (!Bucket[k].isEmpty()){ list.catenate(Bucket[k]); Bucket[k].setEmpty(); // άδειασμα του κάδου για επαναχρησιμοποίηση } } }// Τέλος radixLSD ////////////////// Κεφάλαιο 7 --- Επιλογή (Στατιστικά Τάξεως) //////////////////// /* Απλοϊκή επιλογή: Μεταξύ των θέσεων $left$ και $right$ του πίνακα $a$, βρίσκει το $k$-στό μεγαλύτερο στοιχείο. Επιπροσθέτως, για τις συγκρίσεις η $comparator$, για τον διαχωρισμό η $partition$ */ static Object select(Object a[], int left, int right, int k, comparator c){ if (left>=right) return a[right]; // βάση της αναδρομής int i = partition(a, left, right, c); // εύρεση θέσεως στοιχείου διαχωρισμού if ((k-1 < (i-left))) // το αριστερό σύνολο έχει περισσότερα από $k-1$ return select(a, left, i-1, k, c); // στοιχεία, οπότε θα ψάξουμε εκεί if (i-left == k-1) // το στοιχείο διαχωρισμού είναι return a[i]; // το $k-1$-στό στοιχείο if ((i-left) < k-1) // διαφορετικά, θα ψάξουμε στο δεξιό τμήμα return select(a, i+1, right, k-(i-left+1),c); return null; } /* Η βοηθητική αυτή μέθοδος, βρίσκει την θέση στον υποπίνακα $a[left, right]$ του στοιχείου $a[left]$. Παρατηρήστε πως είναι ίδια ουσιαστικά με το αντίστοιχο τμήμα του $Quicksort$ */ static int partition(Object[] a, int left, int right, comparator c){ int i = left, j = right+1; Object o = a[left], temp; while (true){ // στοιχείο διαχωρισμού το $a[left]$ while (c.less(a[++i], o)) if (i == right) // ανεβαίνει ο δείκτης $i$ break; while (c.less(o,a[--j])) // κατεβαίνει ο δείκτης $j$ ; if (i >= j) // οι δείκτες διασταυρώθηκαν break; temp = a[i]; // ανταλλαγή των στοιχείων στις θέσεις $i,j$ a[i] = a[j]; a[j] = temp; } temp = a[j]; // μεταφορά του στοιχείου $a[left]$ στην θέση $j$ a[j] =a [left]; a[left] = temp; return j; // επιστροφή της θέσεως του στοιχείου διαχωρισμού } /////////////////// Κεφάλαιο 8 --- Δένδρα Αναζητήσεως ////////////////////// /* Ορισμός στοιχείου λεξικού: η νέα μας κλάση, στιγμιότυπα της οποίας θα αποθηκεύονται στις διάφορες δομές που θα συναντήσουμε στην συνέχεια */ public class Item { private Object key, info; // το κλειδί και η πληροφορία αντίστοιχα protected Item(Object k, Object i){ // ο $constructor$ key = k; info = i; } // επιστρέφει το κλειδί του αντικειμένου public Object getKey(){ return key; } // επιστρέφει την πληροφορία του αντικειμένου public Object getInfo(){ return info; } // θέτει το κλειδί του αντικειμένου public void setKey(Object k){ key = k; } // θέτει την πληροφορία του αντικειμένου public void setInfo(Object i){ info = i; } }// Τέλος Item /* Απλοϊκή δομή λεξικού */ public class DictionaryNodeList extends SinglyNodeList { comparator c; public SearchNodeList(comparator com){ // $constructor$ super(); c = com; } /* Επιστρέφει: α) $null$, εάν υπάρχει $item$ με κλειδί $itemKey$ στην κεφαλή της λίστας, β) δείκτη προς τον δεξιότερο κόμβο $v$ με κλειδί μικρότερο του $itemKey$, γ) αλλιώς την ουρά. Η υλοποίηση επηρεάζεται από την ύπαρξη μονού δείκτη σε κάθε κόμβο */ private SNode findNode(Object itemKey){ SNode cursor = first(), precursor = null; // βοηθητικοί δείκτες, ο $precursor$ // είναι πάντοτε έναν κόμβο πριν τον $cursor$ while (cursor != null) // όσο δεν φθάσαμε στην γείωση της ουράς if (!c.less(((Item)cursor.getElement()).getKey(), itemKey)) break; // εντοπισμός μεγαλύτερου ή ίσο κλειδιού else { precursor = cursor; cursor = cursor.getNext(); } return precursor; } /* Επιστρέφει την πληροφορία στην λίστα με κλειδί $key$, εφ' όσον υπάρχει τέτοιο $item$ στην δομή μας. Διαφορετικά, $null$ */ public Object findInfo(Object key){ SNode found = findNode(key); Item checkItem; if (found == null) checkItem = (Item) first().getElement(); else if (found == tail) checkItem = (Item) found.getElement(); else checkItem = (Item) found.getNext().getElement(); return (c.equal(checkItem.getKey(),key) ? checkItem : null); } /* Ενθέτει το $item$ στην δομή μας, εφ' όσον δεν υπάρχει άλλο με ίδιο κλειδί, επιστρέφοντας $true$. Διαφορετικά, επιστρέφει $false$*/ public boolean insertItem(Item item){ if (isEmpty()){ // θα γίνει το πρώτο μας στοιχείο insertFirst(item); return true; } Object key = item.getKey(); SNode found = findNode(key); Item checkItem; if (found == null) // καθορισμός του εμπλεκομένου $Item$ checkItem = (Item) first().getElement(); else if (found == tail) checkItem = (Item) found.getElement(); else checkItem = (Item) found.getNext().getElement(); if (c.equal(checkItem.getKey(),key)) // υπάρχει ήδη return false; if (found == null) insertFirst(item); // θα τοποθετηθεί στην κεφαλή else // διαφορετικά, θα εισαχθεί μετά τον insertAfter(found, item); // κόμβο που έχει το δεξιότερο μικρότερο // κλειδί εν σχέσει με αυτό του $item$ return true; } /* Διαγράφει το $item$ με κλειδί $key$ από την δομή μας, εφ' όσον υπάρχει τέτοιο, επιστρέφοντας $true$. Διαφορετικά, επιστρέφει $false$ */ public boolean deleteItem(Object key){ SNode found = findNode(key); Item checkItem; if (found == null) checkItem = (Item) first().getElement(); else if (found == tail) checkItem = (Item) found.getElement(); else checkItem = (Item) found.getNext().getElement(); if (!c.equal(checkItem.getKey(),key)) return false; // δεν υπάρχει if (found == null) removeFirst(); // είναι στην κορυφή else removeAfter(found); // διαφορετικά, είναι μετά τον $found$ return true; } }// Τέλος DictionaryNodeList /* Αζύγιστα δυναμικά δυαδικά δένδρα αναζητήσεως: η κλάση $BinarySearchTree$ αποτελεί επέκταση της $LinkedBinaryTree$ (δυαδικά δένδρα). Χρησιμοποιεί μία κλάση $comparator$, η οποία εξαρτάται κάθε φορά από το είδος του κλειδιού */ public class BinarySearchTree extends LinkedBinaryTree { comparator c; BinarySearchTree(comparator com){ // $constructor \#1$ super(); c = com; } BinarySearchTree(Item item, comparator com){ // $constructor \#2$ super(item); c = com; } /* επιστρέφει τον κόμβο, εάν υπάρχει τέτοιος, που έχει αποθηκευμένο ένα $item$ με κλειδί $key$, περιορίζοντας την αναζήτηση στο υποδένδρο $Τ_v$ με ρίζα τον κόμβο $v$. Χρόνος $Ο$(ύψους) στην χειρότερη περίπτωση*/ public BTNode findNode(Object key, BTNode v){ Object nodeKey = ((Item) v.getElement()).getKey(); if (c.less(key, nodeKey)){ if (v.getLeft() == null) return v; else return findNode(key,v.getLeft()); } else if (c.equal(key, nodeKey)) return v; else { if (v.getRight() == null) return v; else return findNode(key,v.getRight()); } } /* επιστρέφει την πληροφορία του $item$ με κλειδί $key$, εάν υπάρχει τέτοιο, περιορίζοντας την αναζήτηση στο υποδένδρο $Τ_v$ με ρίζα τον κόμβο $v$. Χρόνος Ο(ύψους) στην χειρότερη περίπτωση */ public Object findInfo(Object key, BTNode v){ BTNode node = findNode(key, v); if (((Item) node.getElement()).getKey() == key) return ((Item)node.getElement()).getInfo(); else return null; } /* ενθέτει ένα νέο $item$ στο δένδρο, επιστρέφοντας τον $BTNode$ που το αποθηκεύει, εφ' όσον δεν υπάρχει άλλο $item$ με ίδιο κλειδί. Εάν υπάρχει, δεν κάνει τίποτε και επιστρέφει $null$. Χρόνος Ο(ύψους) στην χειρότερη περίπτωση */ public BTNode insertItem(Item i){ if (size() == 0){ setRoot(new BTNode(i, null, null, null)); setSize(1); return root(); } BTNode insNode = findNode(i.getKey(), root()); // αναζήτηση βάσει κλειδιού Object keyNode = ((Item) insNode.getElement()).getKey(); // τι βρέθηκε if (c.equal(keyNode, i.getKey())) // υπάρχει ήδη τέτοιο κλειδί return null; else { // δεν υπάρχει, οπότε θα τοποθετηθεί είτε ως αριστερό είτε ως δεξιό παιδί if (c.less(i.getKey(), keyNode)) { // είναι μικρότερο, addLeaf(insNode, Left); // πρέπει να μπει αριστερά insNode.getLeft().setElement(i); return insNode.getLeft(); } else { // είναι μεγαλύτερο, πρέπει να μπει δεξιά addLeaf(insNode, Right); insNode.getRight().setElement(i); return insNode.getRight(); } } } /* αποσβένει, εφ' όσον υπάρχει τέτοιο, το $item$ του δένδρου με κλειδί $key$, επιστρέφοντας τον εναπομείναντα εμπλεκόμενο κόμβο. Εάν δεν υπάρχει, δεν κάνει τίποτε επιστρέφοντας $null$. Χρόνος Ο(ύψους) στην χειρότερη περίπτωση */ public BTNode deleteItem(Object key){ if (size() == 0) return null; BTNode delNode = findNode(key, root()); // αναζήτηση βάσει κλειδιού Object keyNode = ((Item)delNode.getElement()).getKey(); // τι βρέθηκε if (!c.equal(keyNode, key)) // δεν υπάρχει τέτοιο $item$ return null; else { // υπάρχει BTNode returnNode; if ((delNode.getLeft() == null) || (delNode.getRight() == null)){ // έχει γιο $null$ returnNode = (delNode.getLeft() != null ? delNode.getLeft(): delNode.getRight() != null ? delNode.getRight() : delNode.getParent()); deleteNode(delNode); return returnNode; } else{ // και τα δύο του παιδιά είναι κανονικοί κόμβοι, οπότε πρέπει να // βρούμε τον κόμβο του αριστερού υποδένδρου με το μικρότερο κλειδί BTNode cursor = delNode.getRight(), temp, parentDelNode; while((temp = cursor.getLeft()) != null) cursor = temp; exchangeElements(cursor, delNode); // ανταλλαγή περιεχομένων parentDelNode = cursor.getParent(); deleteNode(cursor); // και απόσβεση return parentDelNode; } } }// Τέλος BinarySearchTree ////////////////////// Κεφάλαιο 9 --- Δένδρα AVL ///////////////////// /* Ορισμός στοιχείου δένδρου AVL}: η κλάση των στοιχείων που αποθηκεύει ένας κόμβος ενός δένδρου AVL */ public class avlItem extends Item { private int height; // το ύψος του στοιχείου // $constructor$ protected avlItem(Object k, Object i) { super(k,i); height = 1; } // επιστρέφει το ύψος public int getHeight(){ return height; } // θέτει το ύψος public void setHeight(int h){ height = h; } }// Τέλος avlItem /* Δένδρα AVL */ public class AvlTree extends BinarySearchTree{ AvlTree(comparator com) { // $constructor \#1$ super(com); } AvlTree(avlItem item, comparator com) { // $constructor \#2$ super(item, com); } private int getRightSonHeight(BTNode v) { // επιστρέφει το ύψος του δεξιού γιου if (v == null) { System.out.println("Κενός κόμβος! Δεν υπάρχει δεξιός γιος!"); return -1; } return (v.getRight() != null ? ((avlItem) v.getRight().getElement()).getHeight() : 0); } private int getLeftSonHeight(BTNode v){ // επιστρέφει το ύψος του αριστερού γιου if (v == null) { System.out.println("Κενός κόμβος! Δεν υπάρχει αριστερός γιος! "); return -1; } return (v.getLeft() != null ? ((avlItem) v.getLeft().getElement()).getHeight() : 0); } private void remedyHeight(BTNode v) { // διορθώνει το ύψος ενός κόμβου βάσει if (v == null) { // του ύψους των παιδιών System.out.println("Αδύνατη η διόρθωση κενού κόμβου!"); return; } avlItem vItem = (avlItem) v.getElement(); vItem.setHeight(1+Math.max(getRightSonHeight(v),getLeftSo nHeight(v))); } private boolean isBalanced(BTNode v) { // βρίσκει εάν ο κόμβος είναι ισοζυγισμένος if (v == null) { System.out.println("Κενός κόμβος! Δεν έχει ζύγισμα!"); return false; } int balance = getLeftSonHeight(v)- getRightSonHeight(v); return ((-1 <= balance) && (balance <= 1)); } private BTNode heigherSon(BTNode v) { // βρίσκει το υψηλότερο παιδί if (v == null) { System.out.println("Κενός κόμβος! Δεν έχει παιδιά!"); return null; } if (getLeftSonHeight(v) >= getRightSonHeight(v)) return v.getLeft(); else return v.getRight(); } private void rebalance(BTNode v) { // επαναζυγίζει το δένδρο, από κάτω προς τα // επάνω, ξεκινώντας από τον κόμβο $v$ if (v == null) { System.out.println("Αδύνατη η επαναζύγιση κενού κόμβου!"); return ; } BTNode u, w; while (v != null) { // όσο δεν ξεπεράσαμε την ρίζα... remedyHeight(v); // διορθώνουμε το ύψος του $v$ if (!isBalanced(v)) { // εάν είναι εκτός ισορροπίας w = heigherSon(v); // ο γιος u = heigherSon(w); // και ο εγγονός που θα συμμετάσχουν v = reconstruct(v, w, u); // δομική αλλαγή remedyHeight(v.getLeft()); // διόρθωση υψών των εμπλεκομένων κόμβων remedyHeight(v.getRight()); remedyHeight(v); } v = v.getParent(); // ανεβαίνουμε στον πατέρα } } /* αναδομεί τοπικά το δένδρο, κάνοντας απλή ή διπλή περιστροφή. Επιστρέφει τον υψηλότερο κόμβο μετά την περιστροφή. Στις πράξεις, ο $v$ μπορεί να είναι είτε δεξιός γιος είτε αριστερός γιος είτε ρίζα. Επίσης, πρέπει να προσέξουμε μήπως κάποιο από τα εμπλεκόμενα υποδένδρα είναι $null$ */ private BTNode reconstruct(BTNode v, BTNode w, BTNode u){ if (isLeft(w)&& isLeft(u)){ // Δεξιά απλή περιστροφή ($Rot$) if (!isRoot(v)){ // εάν ο $v$ έχει πατέρα if (isLeft(v)) v.getParent().setLeft(w); else v.getParent().setRight(w); w.setParent(v.getParent()); } v.setLeft(w.getRight()); if (w.getRight() != null) w.getRight().setParent(v); w.setRight(v); v.setParent(w); if (isRoot(v)) { setRoot(w); w.setParent(null); } return w; } else if (isRight(w)&& isRight(u)){ // αριστερή απλή περιστροφή ($rot$), // συμμετρική με την δεξιά if (!isRoot(v)){ if (isRight(v)) v.getParent().setRight(w); else v.getParent().setLeft(w); w.setParent(v.getParent()); } v.setRight(w.getLeft()); if (w.getLeft() != null) w.getLeft().setParent(v); w.setLeft(v); v.setParent(w); if (isRoot(v)) { setRoot(w); w.setParent(null); } return w; } else if (isLeft(u)){ // αριστερή διπλή περιστροφή ($Drot$) v.setRight(u.getLeft()); if (u.getLeft() != null) u.getLeft().setParent(v); w.setLeft(u.getRight()); if (u.getRight()!= null) u.getRight().setParent(w); if (!isRoot(v)){ if (isRight(v)) v.getParent().setRight(u); else v.getParent().setLeft(u); u.setParent(v.getParent()); } v.setParent(u); w.setParent(u); u.setLeft(v); u.setRight(w); if (isRoot(v)) { setRoot(u); u.setParent(null); } return u; } else { // δεξιά διπλή περιστροφή ($Drot$) v.setLeft(u.getRight()); if (u.getRight()!= null) u.getRight().setParent(v); w.setRight(u.getLeft()); if (u.getLeft()!= null) u.getLeft().setParent(w); if (!isRoot(v)) { if (isLeft(v)) v.getParent().setLeft(u); else v.getParent().setRight(u); u.setParent(v.getParent()); } v.setParent(u); w.setParent(u); u.setLeft(w); u.setRight(v); if (isRoot(v)) { setRoot(u); u.setParent(null); } return u; } } // επιστρέφει την πληροφορία του $item$ με κλειδί $key$, εάν υπάρχει τέτοιο public Object findInfo(Object key){ return super.findInfo(key, root()) } /* ένθεση του $i$, χρησιμοποιώντας την ομώνυμη κληρονομημένη μέθοδο από τα δυαδικά δένδρα αναζητήσεως ($BinarySearchTree$) */ public BTNode insertItem(Item i){ BTNode insNode=super.insertItem(i); // χρήση της ομώνυμης μεθόδου if (insNode==null) return null; // δεν έγινε ένθεση γιατί ήδη υπάρχει rebalance(insNode); // επαναζύγιση, ξεκινώντας από τον νέο κόμβο return insNode; // επιστροφή του νέου κόμβου ενθέσεως } /* απόσβεση του στοιχείου με κλειδί $key$, χρησιμοποιώντας την ομώνυμη κληρονομημένη μέθοδο από τα δένδρα αναζητήσεως ($BinarySearchTree$) */ public BTNode deleteItem(Object key) { BTNode delNode = super.deleteItem(key); // χρήση της ομώνυμης μεθόδου if (delNode == null) return null; // δεν έγινε απόσβεση γιατί δεν υπάρχει rebalance(delNode); // επαναζύγιση, ξεκινώντας από τον κόμβο που απώλεσε γιο return delNode; // επιστροφή του κόμβου } }// Τέλος AvlTree ////////////////// Κεφάλαιο 10 --- Δένδρα-($a,b$) //////////////////// /* Ορισμός κόμβου δένδρου-($a,b$) */ public class abTNode extends TNode{ private int curnofSons; // τρέχον πλήθος γιων public abTNode(Item[] items, abTNode parent, int nofsons){ // $constructor$ super(items, parent, nofsons); // χρήση του $TNode$ curnofSons = 1; } public boolean overflow(int b){ // επιστρέφει εάν υπάρχει υπερχείλιση ή όχι return (curnofSons == (b+1)); } public boolean underflow(int a){ // επιστρέφει εάν υπάρχει υπάρχει έλλειμμα ή όχι return (curnofSons==(a-1)); } public boolean canBorrow(int a){ // υπάρχει δυνατότητα δανεισμού γιου? return (curnofSons > a); } public int getCurnofSons(){ // τρέχον πλήθος γιων return curnofSons; } public void setCurnofSons(int s){ // θέτει το τρέχον πλήθος γιων curnofSons = s; } public Object getKey(int i){ // επιστρέφει το $i$-στό κλειδί return ((Item[])element())[i].getKey(); } // εύρεση της θέσεως του $key$ public int findPositionItem(Object key, comparator c){ if (curnofSons == 1) return 0; int j = 0; while ((j < curnofSons-1) && ( c.less(getKey(j),key))) j++; return j; } // τοποθέτηση του $item$ στην $i$-στή θέση protected void setItem(int i, Item item){ ((Item[])element())[i] = item; } // επιστρέφει το $i$-στό $item$ protected Item getItem(int i){ return ((Item[])element())[i]; } // αύξηση κατά ένα του πλήθος των γιων protected void incCurnofSons(){ curnofSons = (curnofSons+1 <= nofSons ? curnofSons+1 : curnofSons); } // μείωση κατά ένα του πλήθος των γιων protected void decCurnofSons(){ curnofSons = (curnofSons-1 >= 0 ? curnofSons-1 : curnofSons); } // αναζήτηση στοιχείου με κλειδί $key$ public Item findItem(Object key, comparator c){ int itemPos = findPositionItem(key,c); if (itemPos < 0) // δεν υπάρχει return null; return (c.equal(getKey(itemPos),key) ? getItem(itemPos) : null); } // επιστροφή και διαγραφή του $i$-στού στοιχείου public Item deleteItem(int i){ if ((i < 0) || (i > curnofSons-1)){ System.out.println("Εκτός ορίων!"); return null; } Item temp = ((Item[])element())[i]; for (; i < curnofSons-2; i++) ((Item[])element())[i] = ((Item[])element())[i+1]; decCurnofSons(); return temp; } // διαγραφή του στοιχείου με κλειδί $key$ και επιστροφή της θέσεώς του public int deleteItem(Object key, comparator c){ int itemPos = findPositionItem(key,c); if (itemPos < 0) // δεν υπάρχει return -1; for (int i = itemPos; i < curnofSons-2; i++) ((Item[])element())[i] = ((Item[])element())[i+1]; decCurnofSons(); return itemPos; } // ένθεση του στοιχείου $item$ και επιστροφή της θέσεώς του public int insertItem(Item item, comparator c){ int itemPos = findPositionItem(item.getKey(),c); if (itemPos < 0) // δεν υπάρχει return -1; if (itemPos < curnofSons) for (int i = curnofSons-2; i >= itemPos; i--) ((Item[])element())[i+1] = ((Item[])element())[i]; ((Item[])element())[itemPos] = item; incCurnofSons(); return itemPos; } // εάν υπάρχει το $key$ επιστροφή της θέσεώς του public int keyExists(Object key, comparator c){ int itemPos = findPositionItem(key,c); if ((itemPos < 0) || (itemPos == curnofSons-1)) return -1; if (c.equal(key,getKey(itemPos))) return itemPos; else return -1; } // διάσπαση του κόμβου και μεταφορά των μισών μεγαλύτερων στοιχείων σε νέο κόμβο public abTNode split(){ // νέος κόμβος "φιλαράκι" abTNode buddy = new abTNode(new Item[nofSons-1], (abTNode)this.getParent(), nofSons); int middle = nofSons/2; for (int j = 0; j < nofSons-1-middle; j++){ // διαδοχική μεταφορά buddy.setItem(j, deleteItem(middle)); buddy.setSon(j, deleteSon(middle)); if (buddy.getSon(j) != null) buddy.getSon(j).setParent(buddy); } buddy.setSon(nofSons-1-middle, deleteSon(middle)); if (buddy.getSon(nofSons-1-middle) != null) buddy.getSon(nofSons-1-middle).setParent(buddy); buddy.setCurnofSons((nofSons-1)/2+1); return buddy; } public boolean hasLeftSibling(){ // υπάρχει αριστερός αδελφός? return (getIndex() > 0); } public boolean hasRightSibling(){ // υπάρχει δεξιός αδελφός? int temp = getIndex(); return((temp < curnofSons) && (temp >= 0)); } // βοηθητικές μέθοδοι εκτυπώσεως των περιεχομένων του κόμβου public void showNode(){ System.out.print("<"); for (int i = 0; i < curnofSons-1; i++) System.out.print(" "+((Item[])element())[i].getKey()); System.out.println(">"); } public void showNodeWithInfo(){ System.out.print("<"); for (int i = 0; i < curnofSons-1; i++) System.out.print(" "+((Item[])element())[i].getKey()+":"+((Item[])element())[i].getInfo()); System.out.println(">"); } } // Τέλος abTNode /* Δένδρα-($a,b$) */ public class abTree extends LinkedGeneralTree{ private int a,b; // το άνω και κάτω όριο της χωρητικότητας private static comparator c; // $comparator$ για τις συγκρίσεις public abTree(int min, int max, comparator com){ // $constructor$ setRoot(null); setSize(0); a = min; b = max; c = com; } /* επιστρέφει τον κόμβο, εάν υπάρχει τέτοιος, που έχει αποθηκευμένο ένα $item$ με κλειδί $key$, περιορίζοντας την αναζήτηση στο υποδένδρο $Τ_v$ με ρίζα τον κόμβο $v$. Χρόνος $Ο$(ύψους) στην χειρότερη περίπτωση */ public abTNode findNode(Object key, abTNode v){ int itemPos = v.findPositionItem(key,c); // εύρεση της θέσεως του κλειδιού if ((itemPos < v.getCurnofSons()-1) && (c.equal(key,v.getKey(itemPos)))) return v; // βρέθηκε else if (v.getSon(itemPos) == null) return v; else return findNode(key,(abTNode)v.getSon(itemPos)); // κάθοδος στον γιο } // επιστρέφει την πληροφορία του $item$ με κλειδί $key$, εάν υπάρχει τέτοιο public Object findInfo(Object key){ abTNode node = findNode(key, (abTNode)root()); return node.findItem(key,c).getKey(); } /* ενθέτει ένα νέο $item$ στο δένδρο, εφ' όσον δεν υπάρχει άλλο $item$ με ίδιο κλειδί. Εάν υπάρχει, δεν κάνει τίποτε και επιστρέφει $false$. Χρόνος Ο(ύψους) στην χειρότερη περίπτωση */ public boolean insertItem(Item i){ if (size() == 0){ // αρχικοποίηση του δένδρου setRoot(new abTNode(new Item[b], null, b+1)); ((abTNode)root()).setItem(0,i); ((abTNode)root()).setCurnofSons(2); setSize(1); return true; } abTNode insNode = findNode(i.getKey(), (abTNode)root()); // αναζήτηση if (insNode.keyExists(i.getKey(),c) >= 0) { // υπάρχει ήδη System.out.println("Το κλειδί ήδη υπάρχει"); return false; } insNode.insertItem(i,c); if (!insNode.overflow(b)) // εισαγωγή δίχως υπερχείλιση return true; else balanceOverflow(insNode); // εισαγωγή με υπερχείλιση --θα γίνει επαναζύγιση return true; } /* αποσβένει, εφ' όσον υπάρχει τέτοιο, το $item$ του δένδρου με κλειδί $key$. Εάν δεν υπάρχει, δεν κάνει τίποτε επιστρέφοντας $false$. Χρόνος Ο(ύψους) στην χειρότερη περίπτωση. */ public boolean deleteItem(Object key){ if (size() == 0) return false; // κενό δένδρο int itemPos; abTNode delNode = findNode(key, (abTNode)root()), v = delNode; // αναζήτηση if ((itemPos = ((abTNode)delNode).keyExists(key,c)) < 0) // δεν υπάρχει return false; delNode = ((abTNode)delNode.getSon(0) != null ? (abTNode)delNode.getSon(itemPos) : delNode); // εντοπισμός του δεξιότερου στοιχείου του αριστερού υποδένδρου while (delNode.getSon(0) != null) delNode = (abTNode)delNode.getSon(delNode.getCurnofSons()-1); // ανταλλαγή με το δεξιότερο στοιχείο του αριστερού υποδένδρου if (v != delNode) v.setItem(itemPos, delNode.deleteItem(delNode.getCurnofSons()-2)); else v.deleteItem(itemPos); if (!delNode.underflow(a)) // απόσβεση δίχως έλλειμμα return true; else balanceUnderflow(delNode); // απόσβεση με έλλειμμα --χρειάζεται επαναζύγιση return true; } // επιδιόρθωση υπερχείλισης private void balanceOverflow(abTNode v){ int pos = 0; // διάσπαση κόμβου, όσο υπάρχει υπερχείλιση και δεν φθάσαμε στην ρίζα while ((v.overflow(b)) && (!isRoot(v))){ abTNode buddy = v.split(); Item splitItem = v.getItem((b+1)/2-1); v.setItem((b+1)/2-1,null); v.decCurnofSons(); v = (abTNode)v.getParent(); pos = v.insertItem(splitItem, c); v.insertSon(pos+1, buddy); } // υπερχείλιση ρίζας --δημιουργία νέας με δύο παιδιά if ((v == root()) && v.overflow(b)) { abTNode buddy = v.split(); Item splitItem = v.getItem((b+1)/2-1); v.setItem((b+1)/2-1,null); v.decCurnofSons(); setRoot(new abTNode(new Item[b], null, b+1)); root().setSon(0,v); v.setParent(root()); ((abTNode) root()).setItem(0,splitItem); root().setSon(1,buddy); buddy.setParent(root()); ((abTNode)root()).setCurnofSons(2); } } // επιδιόρθωση ελλείμματος private void balanceUnderflow(abTNode v){ boolean underflow = true, leftFuse = false; abTNode sibling; TNode temp; if (v == root()) return; // δεν χρειάζεται να γίνει τίποτε while (underflow){ // όσο υπάρχει έλλειμμα... if ((leftFuse = v.hasLeftSibling()) && (sibling = (abTNode)v.getLeftSibling()).canBorrow(a)){ // δυνατός δανεισμός από τον αριστερό αδελφό v.insertSon(0,temp = sibling.deleteSon(sibling.getCurnofSons()-1)); v.insertItem(((abTNode)v.getParent()).getItem(sibling.getIndex()),c); ((abTNode)v.getParent()).setItem(sibling.getIndex(),sibling.deleteItem(sibling.getCurnofSons()-2)); underflow = false; if (temp != null) temp.setParent(v); } else if (v.hasRightSibling() && (sibling = (abTNode)v.getRightSibling()).canBorrow(a)){ // δυνατός δανεισμός από τον δεξιό αδελφό v.insertSon(v.getCurnofSons(), temp = sibling.deleteSon(0)); v.insertItem(((abTNode)sibling.getParent()).getItem(v.getIndex()),c); ((abTNode)sibling.getParent()).setItem(v.getIndex(),sibling.deleteItem(0)); underflow = false; if (temp != null) temp.setParent(v); } else { // συγχώνευση if (leftFuse){ // δυνατή συγχώνευση με τον αριστερό αδελφό sibling = (abTNode)v.getLeftSibling(); sibling.setItem(a-1,((abTNode)v.getParent()).deleteItem(sibling.getIndex())); // μεταφορά στοιχείων και δεικτών στον αδελφό for (int j = 0;j < a-1; j++){ sibling.insertSon(a+j, v.deleteSon(0)); sibling.setItem(a+j, v.deleteItem(0)); if (sibling.getSon(a+j) != null) sibling.getSon(a+j).setParent(sibling); } if (v.getCurnofSons() > 0) sibling.insertSon(2*a-2,v.deleteSon(0)); if (sibling.getSon(2*a-2) != null) sibling.getSon(2*a-2).setParent(sibling); sibling.setCurnofSons(2*a-1); if (v.getParent() != null){ v.getParent().deleteSon(v); v.setParent(null); v = (abTNode)sibling.getParent(); underflow = v.underflow(a); } } else{ //δυνατή συγχώνευση με τον δεξιό αδελφό sibling = (abTNode)v.getRightSibling(); v.setItem(a-2,((abTNode)v.getParent()).deleteItem(v.getIndex())); // δανεισμός στοιχείων και δεικτών από τον αδελφό for (int j = 0;j < a-1; j++){ v.insertSon(a-1+j,sibling.deleteSon(0)); v.setItem(a-1+j, sibling.deleteItem(0)); if (v.getSon(a-1+j) != null) v.getSon(a-1+j).setParent(v); } if (sibling.getCurnofSons() > 0) v.insertSon(2*a-2,sibling.deleteSon(0)); if (v.getSon(2*a-2) != null) v.getSon(2*a-2).setParent(v); v.setCurnofSons(2*a-1); if (sibling.getParent() != null){ sibling.getParent().deleteSon(sibling); sibling.setParent(null); v = (abTNode)v.getParent(); underflow = v.underflow(a); } } } if ((isRoot(v)) && (v.getCurnofSons() == 1)){ // φθάσαμε στην ρίζα και το πρόβλημα παραμένει --διαγραφή της ρίζας setRoot(v.getSon(0)); v.setSon(0,null); root().setParent(null); underflow = false; } } } } // Τέλος abTree ////////////////////// Κεφάλαιο 11 --- Ερυθρόμαυρα Δένδρα //////////////////////// /* Ερυθρόμαυρα δένδρα */ public class RedBlackTree extends BinarySearchTree{ static final boolean black = true; static final boolean red = false; RedBlackTree(comparator com){ // constructor $\#1$ super(com); } RedBlackTree(RedBlackItem item, comparator com){ // constructor $\#2$ super(item, com); } // παρακάμπτει την ομώνυμη κληρονομουμένη μέθοδο, ώστε να μην ανταλλάσσεται και το χρώμα public void exchangeElements(BTNode v, BTNode w){ boolean colorv = ((RedBlackItem) v.getElement()).getColor(); boolean colorw = ((RedBlackItem) w.getElement()).getColor(); ((RedBlackItem) v.getElement()).setColor(colorw); ((RedBlackItem) w.getElement()).setColor(colorv); super.exchangeElements(v, w); } private boolean setBlack(BTNode v){ // μαυρίζει τον $v$ if (v == null) { System.out.println("Κενός κόμβος δεν μαυρίζει!"); return false; } ((RedBlackItem) v.getElement()).setColor(black); return true; } private boolean setRed(BTNode v){ // κοκκινίζει τον $v$ if (v == null) { System.out.println("Κενός κόμβος δεν κοκκινίζει!"); return false; } ((RedBlackItem) v.getElement()).setColor(red); return true; } private boolean isBlack(BTNode v){ // εξετάζει εάν ο $v$ είναι μαύρος if (v == null) // είναι μαύρος εξ ορισμού return true; return (((RedBlackItem) v.getElement()).getColor() == black); } private boolean isRed(BTNode v){ // εξετάζει εάν ο $v$ είναι κόκκινος if (v == null) return false; return (((RedBlackItem) v.getElement()).getColor() == red); } private boolean getColor(BTNode v){ // επιστρέφει το χρώμα του $v$ if (v == null) // είναι μαύρος εξ ορισμού return true; return (((RedBlackItem) v.getElement()).getColor()); } // εξετάζει εάν ο v έχει ακριβώς έναν κόκκινο γιο private boolean hasOneRedSon(BTNode v){ if (v == null) { System.out.println("Ο κενός κόμβος δεν έχει παιδιά!"); return false; } return ((isRed(v.getLeft()) && isBlack(v.getRight())) || (isRed(v.getRight()) && isBlack(v.getLeft()))); } private BTNode getRedSon(BTNode v){ // επιστρέφει τον κόκκινο γιο if (v == null){ System.out.println("Ο κενός κόμβος δεν έχει παιδιά!"); return null; } return (isRed(v.getLeft()) ? v.getLeft() : v.getRight()); } // επαναζυγίζει το δένδρο μετά από μία ένθεση private void insertionRebalance(BTNode v){ if (v == null) { System.out.println("Επαναζύγιση ενθέσεως επί κενού κόμβου!"); return ; } BTNode u = null, w = v; v = v.getParent(); while (isRed(v)) { // όσο ο εξεταζόμενος κόμβος είναι κόκκινος ανεβαίνουμε if (isBlack(getSibling(v))) { // περιστροφή απλή ή διπλή u = w; w = v; v = v.getParent(); v = reconstruct(v,w,u); setRed(v.getLeft()); setRed(v.getRight()); setBlack(v); } else { // εναλλαγή χρώματος ($color flip$) setBlack(v); setBlack(getSibling(v)); v = v.getParent(); if (isRoot(v)) break; setRed(v); u = w; w = v; v = v.getParent(); } } } // επαναζυγίζει το δένδρο μετά από μία ένθεση private void deletionRebalance(BTNode y){ if (y == null){ System.out.println("Επαναζύγιση αποσβέσεως επί κενού κόμβου!"); return; } BTNode sibling =(y.getLeft()!= null ? y.getLeft() : y.getRight()); BTNode childofSibling; while(y != null) { // ανεβαίνουμε, όσο δεν υπερβαίνουμε την ρίζα if (isBlack(sibling)) { boolean parentColor=getColor(y); if (hasOneRedSon(sibling)){ // $C1$ (περιστροφή απλή ή διπλή) y = reconstruct(y,sibling,getRedSon(sibling)); setBlack(y.getLeft()); setBlack(y.getRight()); if (parentColor == black) setBlack(y); else setRed(y); return; } setBlack(y); if (sibling != null) // $C2x, x\in\{a,b\}$ setRed(sibling);`\vskip-15pt` if (parentColor == red) // $C2a$ return; else { // $C2b$ if (isRoot(y)) return; sibling = getSibling(y); y = y.getParent(); } } else { // $C3$ BTNode newSibling; if (isLeft(sibling)) { newSibling = sibling.getRight(); childofSibling = sibling.getLeft(); } else { newSibling = sibling.getLeft(); childofSibling = sibling.getRight(); } setBlack(reconstruct(y,sibling,childofSibling)); setRed(getSibling(childofSibling)); sibling = newSibling; } } } private BTNode reconstruct(BTNode v, BTNode w, BTNode u){ // Ίδια με την ομώνυμη του $AvlTree$ } // ένθεση του στοιχείου $i$, κάνοντας χρήση της ομώνυμης μεθόδου του $BinarySearchTree$ public BTNode insertItem(Item i) { BTNode insNode = super.insertItem(i); if (insNode == null) return null; if (isRoot(insNode)) // εξ ορισμού setBlack(insNode); else // διόρθωση ((ισοζυγίου)) insertionRebalance(insNode); return insNode; } // απόσβεση στοιχείου με κλειδί $key$, κάνοντας χρήση της ομώνυμης μεθόδου του $BinarySearchTree$ public BTNode deleteItem(Object key) { BTNode delNode = super.deleteItem(key); if (delNode == null) return null; if (isRed(delNode) && isRed(delNode.getParent())) setBlack(delNode); // απορρόφηση else if ((((RedBlackItem)lastDeletedElement).getColor() == red) ||isRoot(delNode)) ; // μην κάνεις τίποτα εφ' όσον διαγράφηκε κόκκινος κόμβος else // ανάγκη διόρθωσης ισοζυγίου deletionRebalance(delNode); return delNode; } // επιστρέφει την πληροφορία του $item$ με κλειδί $key$, εάν υπάρχει τέτοιο public Object findInfo(Object key){ return super.findInfo(key,root()) } }// Τέλος RedBlackTree /////////////////// Κεφάλαιο 12 --- Βασικές Έννοιες στον Κατακερματισμό /////////////////////// /* Κατακερματισμός με αλυσίδες */ public class hashingWithChaining{ private int n; // πλήθος στοιχείων που έχουν εισαχθεί στην δομή private int m; // το μέγεθος του πίνακα κατακερματισμού private DictionaryNodeList[] H; // ο πίνακας κατακερματισμού private hashOperator h; // αντικείμενο-συνάρτηση κατακερματισμού public hashingWithChaining(int size, hashOperator hs){ // $constructor \#1$ h = hs; n = 0; H = new DictionaryNodeList[m = size]; // δημιουργία πίνακα κατακερματισμού // $m$ θέσεων for (int i = 0; i < size; i++) // αρχικοποίηση με κενές λίστες H[i] = new DictionaryNodeList(new comparator()); } public hashingWithChaining(hashOperator hs){ // $constructor \#2$ m = 101; // το ερήμην (default) μέγεθος... h = hs; n = 0; H = new DictionaryNodeList[m]; for (int i = 0;i < m; i++) H[i] = new DictionaryNodeList(new comparator()); } // Αναζήτηση στοιχείου με κλειδί $key$. Επιστρέφει $null$, εάν δεν υπάρχει τέτοιο $item$ public Item findItem(Object key){ return H[h.hashTo(key)].findItem(key); } // ένθεση ενός $item$, εφ' όσον δεν υπάρχει ήδη άλλο στοιχείο με το ίδιο κλειδί public boolean insertItem(Item item){ return (H[h.hashTo(item.getKey())].insertItem(item)? ++n > 0 : false); } // απόσβεση του $item$ με κλειδί $key$, εφ' όσον υπάρχει public boolean deleteItem(Object key){ return (H[h.hashTo(key)].deleteItem(key) ? -n >= 0 : false); } }// Τέλος hashingWithChaining /* Κλάση υπολογισμού συναρτήσεως κατακερματισμού */ public class hashOperator{ private int m; public hashOperator(int divisor){ // $constructor$ m = divisor; } public int hashTo(Object k){ // η συνάρτηση κατακερματισμού return ((Integer) k).intValue()%m; } }// Τέλος HashOperator /////////////////// Κεφάλαιο 13 --- Κατακερματισμός με Ανοιχτή ή Ελεύθερη Διευθυνσιοδότηση /* Κατακερματισμός με γραμμική δοκιμή */ public class hashingWithLinearProbing{ private int n; // πλήθος αποθηκευμένων στοιχείων private int m; // μέγεθος του πίνακα κατακερματισμού private Item[] H; // ο πίνακας κατακερματισμού private hashOperator h; // αντικείμενο που προσφέρει την συνάρτηση // κατακερματισμού και $comparator$ για τις συγκρίσεις private static final Item tombStone = new Item(null,null); // ...η ταφόπλακα public hashingWithLinearProbing(int size, hashOperator hs){ // $constructor \#1$ h = hs; n = 0; H = new Item[m = size]; } public hashingWithLinearProbing(hashOperator hs){ // $constructor \#2$ h = hs; n = 0; H = new Item[m = 101]; // η ερήμην χωρητικότητα } public int getnofItems(){ // επιστρέφει το πλήθος των αποθηκευμένων στοιχείων return n; } public boolean isNull(int i){ // εξετάζει εάν η θέση $i$ του πίνακα είναι κενή return (H[i] == null); } public boolean isTombStone(int i){ // εξετάζει εάν η $i$-στή θέση έχει εκκενωθεί return(H[i] == tombStone); } /* Βοηθητική μέθοδος για την εύρεση της θέσεως ενός $item$ με κλειδί $key$. Επιστρέφει την θέση, εάν υπάρχει. Διαφορετικά, επιστρέφει $-1$ */ private int findPositionItem(Object key){ int i, startPosition = i = h.hashTo(key);// η αρχική θέση do { if (isNull(i)) // η θέση είναι κενή, το στοιχείο δεν υπάρχει return -1; if (isTombStone(i)) // κενωθείσα θέση, πηγαίνουμε παρακάτω i = (i + 1) % m; else if (h.Comparator().equal(H[i].getKey(),key)) // το βρήκαμε return i; else i = (i + 1) % m; // συνεχίζουμε να ψάχνουμε... } while (i != startPosition) // εξετάζουμε τις θέσεις μέχρι να // επιστρέψουμε στην αρχική return -1; // δεν υπάρχει } /* Η μέθοδος αναζητήσεως στοιχείου με κλειδί $key$. Επιστρέφει το $item$, εάν υπάρχει. Διαφορετικά, $null$ */ public Item findItem(Object key){ int position = findPositionItem(key); if (position == -1) return null; else return H[position]; } /* Ενθέτει το $item$, επιστρέφοντας $true$, εάν δεν υπάρχει άλλο με ίδιο κλειδί. Διαφορετικά, επιστρέφει $false$ */ public boolean insertItem(Item item){ Object itemKey = item.getKey(); int i = h.hashTo(itemKey); // η αρχική θέση int startPosition = i; do { if (isNull(i) || isTombStone(i)) { // διαθέσιμη θέση είτε κενή είτε κενωθείσα H[i] = item; n++; // ενημέρωση του μεγέθους return true; } else if (h.Comparator().equal(itemKey, H[i].getKey())) {// υπάρχει ήδη System.out.println("Υπάρχει ήδη στοιχείο με ίδιο κλειδί!"); return false; } i = (i + 1) % m; // διαφορετικά, μεταβαίνουμε στην επόμενη θέση } while (i != startPosition) // εξετάζουμε τις θέσεις μέχρι επιστροφής ; // στην αρχική System.out.println("Ο πίνακας κατακερματισμού είναι πλήρης!"); return false; // έχουμε εξετάσει κυκλικά όλες τις θέσεις } // και δεν βρέθηκε καμμία διαθέσιμη public boolean deleteItem(Object key){ int i = findPositionItem(key); // η εξεταζόμενη θέση if (i < 0) return false; // δεν βρέθηκε στοιχείο με κλειδί $key$ H[i] = tombStone; // βρέθηκε και τοποθετούμε στην θέση αυτή ταφόπλακα n--; // ενημέρωση του μεγέθους return true; } }// Τέλος HashingWithLinearProbing /////////////// Κεφάλαιο 14 --- Κατακερματισμός Σταθερού Χειρότερου Χρόνου Αναζητήσεως ///////////// /* Δυναμικός Τέλειος Κατακερματισμός */ public class dynamicPerfectHashing { private int count; // άνω όριο στο $\#$ στοιχείων: // αρχικά $\#$ στοιχείων, εν συνεχεία $\#$ πράξεων private int M; // μέγιστη χωρητικότητα του πίνακα πρώτου επιπέδου private int s_M; // μέγεθος πίνακα 1ου επιπέδου $(round(S\_{CONST}*M))$ private int degeneracyLimit; // παράγων εκφυλισμού; αναδιοργάνωση εάν // το $\sum s_j$ τον ξεπερνά private int S; // τρέχον $\sum s_j$, $\leq degeneracyLimit$ private perfectHashTable[] H; // ο πίνακας κατακερματισμού 1ου επιπέδου private hashOperator h; // η συνάρτηση κατακερματισμού double C = 0.5; // ο παράγων ((οκνηρότητας)) double S_CONST = 2.921186973; // $=8\sqrt{30}/15$ public dynamicPerfectHashing(Item item, comparator c){ // $constructor$ M = s_M = 1; count = 0; H = new perfectHashTable[1]; h = new hashOperator(2, c); H[0] = new perfectHashTable(2, new hashOperator(4, c)); globalRebuilding(item); } // ολική αναδόμηση της δομής, με προσθήκη του νέου στοιχείου $item$ void globalRebuilding(Item item) { int j,i; Item[] L = new Item[++count]; // βοηθητική λίστα μη κενών στοιχείων int[] b; // βοηθητικοί μετρητές στοιχείων ανά θέση πίνακα count = 0; // μηδενισμός ολικού μετρητή for (j = 0; j < s_M; j++) // συλλογή μη κενών στοιχείων for (i = 0; i < H[j].getHashTableSize(); i++) // προσοχή για κενό στοιχείο ή την ταφόπλακα! if ((H[j].getItem(i) != null) && (H[j].getItem(i).getKey() != null)) L[count++] = H[j].getItem(i); if (item != null) // έλεγχος του επιπλέον στοιχείου L[count++] = item; // υπολογισμός νέων παραμέτρων του πίνακα M = (int)((1.0+C)*(count < 4 ? 2 : count)); s_M = (int)(S_CONST*M); Item[][] Laux = new Item[s_M][]; // βοηθητικός πίνακας για την κατανομή // των μη κενών στοιχείων b = new int[s_M]; degeneracyLimit = (int) (32.0*M/S_CONST+4.0*M); H = new perfectHashTable[s_M]; // ο νέος πίνακας πρώτου επιπέδου S = degeneracyLimit+1; /* εντοπισμός της κατάλληλης συναρτήσεως κατακερματισμού με καταμέτρηση στοιχείων ανά θέση πίνακα */ while (S > degeneracyLimit) S = h.select1LevelHashFunction(b,L); for (j = 0; j < s_M; j++){ Laux[j] = new Item[(b[j]==0?1:b[j])]; // αρχικοποίηση b[j] = 0; } for (i = 0; i < count; i++) { // κατανομή των στοιχείων j = h.hashTo(L[i].getKey()); Laux[j][b[j]++] = L[i]; } for (j = 0; j < s_M; j++) { // χτίσιμο των πινάκων 2ου επιπέδου // αφήνουμε χώρο και για τους (προσωρινά) κενούς int size = (b[j] == 0 ? 2 : 2*b[j]); H[j] = new perfectHashTable(size, new hashOperator(size,new comparator()),Laux[j]); } } // αναζήτηση στοιχείου βάσει κλειδιού $key$ Item findItem(Object key) { return H[h.hashTo(key)].findItem(key); } // αναζήτηση συσχετιζόμενης πληροφορίας βάσει κλειδιού $key$ Object findInfo(Object key){ Item item; if ((item = H[h.hashTo(key)].findItem(key)) != null) return item.getInfo(); else return null; } // διαγραφή στοιχείου βάσει κλειδιού $key$ public boolean deleteItem(Object key){ boolean flag; count++; // ενημέρωση μετρητού flag = H[h.hashTo(key)].deleteItem(key); if (count >= M) // ανάγκη για ολική αναδόμηση globalRebuilding(null); return flag; } // ένθεση του στοιχείου $item$ βάσει κλειδιού public int insertItem(Item item){ Object itemKey = item.getKey(); // το κλειδί της αναζήτησης count++; // ενημέρωση μετρητού switch (H[h.hashTo(itemKey)].insertItem(item, this)){ case 0: return 0; // υπάρχει ήδη τέτοιο κλειδί! case 1: return 1; // άμεση ένθεση case 20: return 20; // ένθεση μετά από τοπικό ανακατακερματισμό case 21: return 21; // ένθεση μετά από τοπική επέκταση // και ανακατακερματισμό case 3: globalRebuilding(item); // ολικός ανακατακερματισμός return 3; } return 4; // void! } // οι επόμενες δύο μέθοδοι επιστρέφουν εάν υπάρχει ανάγκη ανακατακερματισμού public boolean needsGlobalRebuilding(int s){ return (S > degeneracyLimit); } public boolean needsGlobalRebuilding(){ return (S > degeneracyLimit); } public int getS(){ return S; } public void setS(int s){ S = s; } }// Τέλος dynamicPerfectHashing /* Πίνακες Τέλειου Κατακερματισμού Δευτέρου Επιπέδου */ public class perfectHashTable{ protected int n; // πλήθος στοιχείων protected int m; // άνω όριο για το πλήθος στοιχείων protected int s; // μέγεθος του πίνακα protected Item[] H; // ο πίνακας κατακερματισμού protected hashOperator h; // η ((τοπική)) συνάρτηση κατακερματισμού protected static final Item tombStone = new Item(null,null);// ταφόπλακα public perfectHashTable(int size, hashOperator hs){ // $constructor \# 1$ h = hs; n = 0; m = size; s = (size == 0 ? 2 : 2*m*(m-1)); H = new Item[s]; } // $constructor \#2$: χτίζει τον πίνακα, βάσει των στοιχείων του πίνακα $L$ public perfectHashTable(int size, hashOperator hs, Item[] L){ n = L.length; m = size; H = new Item[s = 2*m*(m-1)]; hs.selectHashFunction(s,L); h = hs; for (int i = 0; i < n; i++) // κατανομή των στοιχείων του $L$ if (L[i] == null) continue; else H[h.hashTo(L[i].getKey())] = L[i]; } public Item findItem(Object key){ // αναζήτηση στοιχείου σε χρόνο $O(1)$ Item item = H[h.hashTo(key)]; if ((item == null) || (item == tombStone)) return null; else return (h.equal(item.getKey(),key) ? item: null); } /* ένθεση του στοιχείου $item$ βάσει κλειδιού και πληροφορίας από τον πίνακα πρώτου επιπέδου */ public int insertItem(Item item, dynamicPerfectHashing PH){ Object itemKey = item.getKey(); // το κλειδί του αντικειμένου int i = h.hashTo(itemKey); // θέση που αντιστοιχεί if ((H[i]!=null) && (H[i] != tombStone) && (h.equal(H[i].getKey(),itemKey)))// υπάρχει! return 0; if (++n <= m){ // ο τρέχων πίνακας δύναται να το στεγάσει δίχως επέκταση if ((H[i] == tombStone) || (H[i] == null)){ // κενωθείσα ή κενή θέση H[i] = item; return 1; // επιτυχής εισαγωγή } else // διαφορετικά, υπάρχει σύγκρουση και ανάγκη ανακατακερματισμού localRebuilding(item); return 20; } else{ // ο τρέχων πίνακας πρέπει να επεκταθεί προκειμένου να το στεγάσει int old_s = s; int new_m = (m > 1 ? 2*m : 2); // διπλασιασμός μέγιστης χωρητικότητας int new_s = 2*new_m*(new_m-1); // το αντίστοιχο μέγεθος πίνακα int new_S = PH.getS() + new_s - old_s; if (!PH.needsGlobalRebuilding()) {// αρκεί τοπικός ανακατακερματισμός m = new_m; s = new_s; PH.setS(new_S); localRebuilding(item); return 21; } else // ανάγκη ολικού ανακατακερματισμού return 3; } } // διαγραφή στοιχείου βάσει κλειδιού $key$ public Object deleteItem(Object key){ int i = h.hashTo(key); // θέση που αντιστοιχεί Object itemInfo; if ( (H[i] == null) || (H[i] == tombStone)) // τίποτε για διαγραφή! return null; itemInfo = H[i].getInfo(); H[i] = tombStone; // τοποθέτηση ταφόπλακας --n; // ενημέρωση πλήθους στοιχείων return itemInfo; } // τοπικός ανακατακερματισμός με στέγαση του επιπλέον στοιχείου $item$ private void localRebuilding(Item item){ Item[] L = new Item[s]; // βοηθητικός πίνακας για την συγκέντρωση int new_n = 0, i, j; // των στοιχείων for (i = 0; i < H.length; i++) // αντιγραφή μη κενών στοιχείων if ((H[i] != tombStone) && (H[i] != null)) L[new_n++] = H[i]; L[new_n] = item; // αντιγραφή του επιπλέον στοιχείου // εύρεση της νέας συναρτήσεως τέλειου κατακερματισμού h.selectHashFunction(s,L); n = new_n+1; H = new Item[s]; // νέος πίνακας for (i = 0; i < s; i++) // αρχικοποίηση H[i] = null; for (i = 0; i < n; i++) // κατανομή των στοιχείων H[h.hashTo(L[i].getKey()] = L[i]; } public int getHashTableSize(){ return s; } public Item getItem(int i){ return H[i]; } }// Τέλος perfectHashTable /* Συνάρτηση Καθολικού Κατακερματισμού */ public class hashOperator{ private int m1, m2; // οι τυχαίες σταθερές συναρτήσεως private int p = 65537; // ο πρώτος αριθμός private int s; // μέγεθος πίνακα κατακερματισμού private comparator c; // $comparator$ private static Random ran = new Random(230870); // γεννήτρια // $constructor \#1$ public hashOperator(int S, comparator comp){ s = m1 = m2 = S; c = comp; } // $constructor \#2$ public hashOperator(int k, int S){ m1 = m2 = k; s = S; } // $constructor \#3$ public hashOperator(int k, int S, comparator comp){ m1 = m2 = k; s = S; c = comp; } // $constructor \#4$ public hashOperator(int k, int S, int Pi, comparator com){ m1 = k; s = S; p = Pi; c = com; } // επιστροφή ενός τυχαίου κλειδιού private int randomKey(){ return (1+(ran.nextInt(32001) % (p-1))); } // συνάρτηση υπολογισμού θέσεως κλειδιού $k$ public int hashTo(Object k){ return (((((((Integer)k).intValue() & 0x0000ffff)*m1)+m2)% p) % s); } // συνάρτηση υπολογισμού θέσεως κλειδιού $k$ με εξωτερικές παραμέτρους public int hashTo(Object k, int M1, int M2, int S){ return (((((((Integer)k).intValue() & 0x0000ffff)*M1)+M2) % p) % S); } public comparator Comparator(){ return c; } public boolean equal(Object x,Object y){ return c.equal(x,y); } /* επιλέγει μία τέλεια συνάρτηση κατακερματισμού για τα στοιχεία του πίνακα $L$, τα οποία θα κατανεμηθούν σε πίνακα μεγέθους $S$ */ public void selectHashFunction(int S, Item[] L) { boolean [] test = new boolean[S]; // βοηθητικός πίνακας καταμέτρησης int i, j, M1, M2; // κατανεμημένων στοιχείων ανά θέση while (true){ newkey: { for (i = 0; i < S; i++) // αρχικοποίηση πίνακα test[i] = false; M1 = randomKey(); // επιλογή τυχαίων συντελεστών M2 = randomKey()-1; for (i = 0; i < L.length; i++){ if (L[i]!= null){ j = hashTo(L[i].getKey(), M1, M2, S); if (test[j]) break newkey; // βρέθηκε σύγκρουση!!! else test[j] = true; } } break; } } m1 = M1; // καταγραφή των παραμέτρων που βρέθηκαν m2 = M2; s = S; } /* επιλέγει μία καθολική συνάρτηση κατακερματισμού πρώτου επιπέδου για τα στοιχεία του πίνακα $L$ */ public int select1LevelHashFunction(int[] b, Item[] L) { int i, S = 0, j; m1 = randomKey(); // επιλογή των τυχαίων συντελεστών m2 = randomKey()-1; for (i = 0; i < b.length; i++) // αρχικοποίηση b[i] = 0; for (i = 0; i < L.length; i++) // κατανομή και καταγραφή $\#$ στοιχείων if (L[i] == null) // ανά θέση πίνακα continue; else b[hashTo(L[i].getKey(), m1, m2, b.length)]++; for (i = 0; i < b.length; i++){ // υπολογισμός του νέου $S=\sum s_j$ j = (b[i] == 0 ? 2 : 2*b[i]); S += 2*j*(j-1); } s = b.length; return S; } public int getM1(){ return m1; } public int getM2(){ return m2; } }// Τέλος hashOperator /* Κατακερματισμός Κούκκου */ public class cuckooHashing{ Item[][] CT; // πίνακας κατακερματισμού int m; // μήκος πίνακα int n; // πλήθος στεγασμένων στοιχείων int maxnofIter; // άνω όριο επαναλήψεων ένθεσης int nofIns; // πλήθος ενθέσεων από την τελευταία επιλογή συναρτήσεων hashOperator[] h; // οι συναρτήσεις κατακερματισμού comparator c; final static float aUpper = (float) 5/12; // άνω όριο παράγοντα φόρτου final static float aLower = (float) 2/10; // κάτω όριο παράγοντα φόρτου public cuckooHashing(int size, int iters, hashOperator h1, hashOperator h2, comparator comp){ m = size; n = 0; maxnofIter = iters; CT = new Item[2][m]; h = new hashOperator[2]; h[0] = h1; h[1] = h2; c = comp; } public cuckooHashing(int size, comparator comp){ m = size; n = 0; maxnofIter = (int)(6*Math.log(m) / Math.log(2)); CT = new Item[2][m]; h = new hashOperator[2]; h[0] = new hashOperator(m); // τυχαίες συναρτήσεις h[1] = new hashOperator(m); c = comp; } int getSize(){ return m; } void setSize(int size){ m = size; } Item[][] getTable(){ return CT; } void setTable(Item[][] t){ CT=t; } hashOperator getHash0(){ return h[0]; } hashOperator getHash1(){ return h[1]; } void setHash0(hashOperator hash){ h[0] = hash; } void setHash1(hashOperator hash){ h[1] = hash; } comparator getComparator(){ return c; } int FindPositionItem(Object key, Item[][] T){ int size = T[0].length; // εναλλακτικές θέσεις int p0 = getHash0().hashTo(key), p1= getHash1().hashTo(key); // τα κλειδιά των δύο θέσεων Object k0 = (T[0][p0] != null ? T[0][p0].getKey() : null); Object k1 = (T[1][p1] != null ? T[1][p1].getKey() : null); if (getComparator().equal(k0,key)) // βρέθηκε στον πρώτο πίνακα return p0; else if (getComparator().equal(k1,key)) // βρέθηκε στον δεύτερο πίνακα return size+p1; else return -1; // δεν υπάρχει } int InsertItem(Item i){ return InsertItem(i, getTable()); } int InsertItem(Item i, Item [][]T){ Object key; Item temp0, temp1; cuckooHashing t; if (FindPositionItem(key = i.getKey(), T) != -1) // υπάρχει ήδη return -1; ++n; // προσαρμογή $\#$ στεγασμένων στοιχείων ++nofIns; // προσαρμογή $\#$ ενθέσεων από την τελευταία ανακατασκευή if (n > aUpper*2*m){ // υπέρβαση άνω ορίου φόρτου t = doubleTables(T); // ανακατακερματισμός σε διπλάσιο πίνακα T = t.getTable(); setTable(T); setHash0(t.getHash0()); setHash1(t.getHash1()); setSize(t.getSize()); } if (nofIns == m*m){ // υπέρβαση άνω ορίου χρήσης συναρτήσεων $h1,h2$ t = rehash(T); // επανένθεση στεγασμένων στοιχείων με νέες $h1,h2$ T = t.getTable(); setTable(T); setHash0(t.getHash0()); setHash1(t.getHash1()); setSize(t.getSize()); nofIns = 1; // προσαρμογή μετρητή επιτυχημένων ενθέσεων } Item x = i; int nofIter= 0; // αριθμός επαναλήψεων βρόχου while // η θέση στον πρώτο πίνακα όπου θα τοποθετηθεί το $i$ int pos = getHash0().hashTo(key); while (++nofIter <= maxnofIter){ // δεν ξεπεράσαμε το άνω όριο temp0 = T[0][getHash0().hashTo(key)]; T[0][getHash0().hashTo(key)] = x; if (temp0 == null) // η θέση ήταν άδεια, ολοκλήρωση εισαγωγής return pos; // επιστροφή της θέσεως του $i$ temp1 = T[1][getHash1().hashTo(temp0.getKey())]; // στέγαση του εκδιωχθέντος στοιχείου του $T[0]$ T[1][getHash1().hashTo(temp0.getKey())] = temp0; if (temp1 == null) // η θέση ήταν άδεια, ολοκλήρωση εισαγωγής return pos; // επιστροφή της θέσεως του $i$ x = temp1; // διαφορετικά, θα πρέπει να στεγάσουμε key = x.getKey(); // το εκδιωχθέν στοιχείο του $T[1]$ } t = rehash(T); // επανένθεση στεγασμένων στοιχείων με νέες $h1,h2$ T = t.getTable(); setTable(T); setHash0(t.getHash0()); setHash1(t.getHash1()); setSize(t.getSize()); nofIns = 0; // μηδενισμός μετρητή επιτυχημένων ενθέσεων --n; // επαναφορά σωστού πλήθους στοιχείων return InsertItem(i,T);// νέα προσπάθεια εισαγωγής του $i$ } Object DeleteItem(Object key){ int x, p; p = FindPositionItem(key, CT); cuckooHashing t; if (p == -1) // δεν υπάρχει return null; if (p < getSize()){ // υπάρχει στον πρώτο πίνακα x = 0; } else{ // υπάρχει στον δεύτερο πίνακα x = 1; p -= getSize(); } Item i = CT[x][p]; // το στοιχείο CT[x][p] = null; n--; // προσαρμογή πλήθους στοιχείων if (n < aLower*2*m){ // παραβίαση κάτω ορίου φόρτου t = halveTables(CT); // υποδιπλασιασμός πινάκων setTable(t.getTable()); setSize(t.getSize()); setHash0(t.getHash0()); // ανακατακερματισμός setHash1(t.getHash1()); } return i; } cuckooHashing rehash(Item [][]T){ int size = T[0].length; cuckooHashing temp = new cuckooHashing(size, getComparator()); // εισαγωγή σε νέα προσωρινή δομή με νέες τυχαίες συναρτήσεις for (int i = 0; i < size; i++){ if (T[0][i] != null) temp.InsertItem(T[0][i]); if (T[1][i] != null) temp.InsertItem(T[1][i]); } return temp; } cuckooHashing doubleTables(Item [][]T){ int size = T[0].length; cuckooHashing temp = new cuckooHashing(2*size, getComparator()); // εισαγωγή σε νέα προσωρινή δομή με νέες τυχαίες συναρτήσεις for (int i = 0; i < size; i++){ if (T[0][i] != null) temp.InsertItem(T[0][i]); if (T[1][i] != null) temp.InsertItem(T[1][i]); } return temp; } cuckooHashing halveTables(Item [][]T){ int size = T[0].length; cuckooHashing temp = new cuckooHashing(size/2, getComparator()); // εισαγωγή σε νέα προσωρινή δομή με νέες τυχαίες συναρτήσεις for (int i = 0; i < size; i++){ if (T[0][i] != null) temp.InsertItem(T[0][i]); if (T[1][i] != null) temp.InsertItem(T[1][i]); } return temp; } }// Τέλος cuckooHashing // Ενδεικτική κλάση κατακερματισμού public class hashOperator{ private int a, b; // παράμετροι private int m; // μέγεθος πίνακα private static Random ran = new Random(230870); hashOperator(int x, int y, int size){ a = x; b = y; m = size; } hashOperator(int size){ a = 1+(ran.nextInt(32001)); b = ran.nextInt(32001); m = size; } int getm(){ return m; } int hashTo(Object x){ return (((Integer)x).intValue()*a+b)%m; } }// Τέλος hashOperator /////////////// Κεφάλαιο 15 --- Επεκτάσιμος Κατακερματισμός ///////////// // η κλάση που εξομοιώνει μία σελίδα public class page{ private int nofItems; private int b; // μέγεθος σελίδας+1 private Item p[]; // ο χώρος για την αποθήκευση των στοιχείων private int ld; // το τοπικό βάθος της σελίδας private static comparator c; // για τις συγκρίσεις public page(int size, comparator com){ // $constructor \#1$ p = new Item[b = size]; c = com; nofItems = 0; } public page(int size){ // $constructor \#2$ p = new Item[b = size]; nofItems = 0; } public boolean overflow(){ // επιστρέφει $true$, εάν η σελίδα υπερχείλισε return (nofItems == b); } public boolean empty(){ // επιστρέφει $true$, εάν η σελίδα άδειασε return (nofItems == 0); } public int getnofItems(){ // επιστρέφει πλήθος αποθηκευμένων στοιχείων return nofItems; } public void setnofItems(int s){ // θέτει το πλήθος των στοιχείων nofItems = s; } // επιστρέφει την θέση του αντικειμένου με κλειδί $k$, εάν υπάρχει. Διαφορετικά, -$1$ private int findPositionItem(Object key){ if (nofItems == 0) return -1; for (int j = 0; j < nofItems; j++) if (c.equal(key,p[j].getKey())) return j; return -1; } // τοποθετεί το $item$ στην θέση $i$ protected void setItem(int i, Item item){ p[i] = item; } protected Item getItem(int i){ // επιστρέφει το $i$-στο $item$ return p[i]; } public int getLocalDepth(){ // επιστρέφει το τοπικό βάθος return ld; } protected void setLocalDepth(int i){ // θέτει το τοπικό βάθος ld = (i <= b ? i : ld); } protected void incLocalDepth(){ // αυξάνει κατά ένα το τοπικό βάθος ld = (ld+1 < b ? ld+1 : ld); } protected void decLocalDepth(){ // μειώνει κατά ένα το τοπικό βάθος ld = (ld-1 >= 0 ? ld-1 : ld); } public Item findItem(Object key){ // βρίσκει το στοιχείο με κλειδί $key$ int itemPos = findPositionItem(key); if (itemPos < 0) return null; return p[itemPos]; } // αποσβένει το στοιχείο με κλειδί $key$ public boolean deleteItem(Object key){ int itemPos = findPositionItem(key); if (itemPos < 0) return false; for (; itemPos < nofItems; itemPos++) // σύμπτυξη του πίνακα p[itemPos] = p[itemPos+1]; nofItems--; // ενημέρωση του πλήθους return true; } // ενθέτει το $item$, εάν δεν υπάρχει ήδη, στο τέλος public boolean insertItem(Item item){ int itemPos = findPositionItem(item.getKey()); if (itemPos >= 0) return false; p[nofItems++] = item; return true; } // αδειάζει την σελίδα, επιστρέφοντας τα στοιχεία public Item[] emptyPage(){ Item[] t = p; p = null; return t; } } // Τέλος page /* Εξαγωγή προθεμάτων */ public class bitOperator{ private int MASK1; // δυαδική μάσκα, όλο άσσους private int MASK2; // δυαδική μάσκα με ένα ψηφίο θεμένο private int keyLength; // μέγιστο μήκος κλειδιών (σε πλήθος ψηφίων) public bitOperator(int l){ // $constructor$ keyLength = l; MASK1 = (1 << l)-1; MASK2 = 1 << (l-1); } // επιστρέφει το πρόθεμα μήκους $nofbits$, όταν το κλειδί έχει μήκος $gd$ public int getBits(Object key, int nofbits, int gd){ if (nofbits == 0) return 0; int mask = (MASK1 << (keyLength-nofbits)); return (((((Integer)key).intValue() << (keyLength-gd))&mask) >> (keyLength-nofbits)); } // επιστρέφει το πρόθεμα μήκους $nofbits$ του $key$ public int getBits(Object key, int nofbits){ if (nofbits == 0) return 0; int mask = (MASK1 << (keyLength-nofbits)); return ((((Integer)key).intValue()&mask) >> (keyLength-nofbits)); } /* επιστρέφει $true$ εάν το $d$-οστό ψηφίο του $key$ είναι θεμένο στην τιμή \ytib{1} ---διαφορετικά $false$ */ public boolean getBit(Object key, int d){ return((((Integer)key).intValue() & (MASK2 >> (d-1))) == 0 ? false : true); } }// Τέλος bitOperator /* Επεκτάσιμος κατακερματισμός */ public class extendibleHashing{ // η κυρίως κλάση private int gd; // ολικό βάθος private int nofItems; // πλήθος αποθηκευμένων $item$ private int sizeofDir; // το μέγεθος του πίνακα-καταλόγου private page Dir[]; // ο κατάλογος private int b; // μέγεθος{}+$1$ των σελίδων private bitOperator bO; // η κλάση για τον χειρισμό των κλειδιών public extendibleHashing(int pagesize, comparator c, bitOperator o){ // $constructor$ nofItems = 0; gd = 0; Dir = new page[sizeofDir = 1]; Dir[0] = new page(b = pagesize, c); bO = o; } /* Διασπά μία υπερχειλισμένη σελίδα, επιστρέφοντας την νέα σελίδα-φιλαράκι που δημιουργείται */ private page split(page p){ page buddy = new page(b); // η νέα σελίδα - φιλαράκι int pk = 0, bk = 0, pld = p.getLocalDepth()+1; for (int j = 0; j < b; j++) if (!bO.getBit(p.getItem(j).getKey(), pld)) // το $j$-στό στοιχείο πρέπει p.setItem(pk++, p.getItem( j)); // να παραμείνει στην $p$ else buddy.setItem(bk++, p.getItem( j)); // πρέπει να πάει στο φιλαράκι p.incLocalDepth(); buddy.setLocalDepth(p.getLocalDepth() ); p.setnofItems(pk); buddy.setnofItems(bk); insertDir(buddy, (buddy.empty()?((Item)p.getItem(0)).getKey(): ((Item)buddy.getItem(0)).getKey())); return buddy; } /* ενθέτει την σελίδα $p$ στον κατάλογο βάσει του κλειδιού $key$ και του τοπικού βάθους της */ private void insertDir(page p, Object key){ int i, m = 1, dp = p.getLocalDepth(); // υπολογισμός της θέσεως όπου ανήκει int pos = (p.empty() ? bO.getBits(key,dp)^1 : bO.getBits(key, dp)); if (gd < dp){ // διπλασιασμός του καταλόγου με συγχώνευση ενός αντιγράφου page[] oldDir = Dir; gd++; // αύξηση του ολικού βάθους κατά ένα sizeofDir += sizeofDir; // διπλασιασμός του καταλόγου Dir = new page[sizeofDir]; for (i = 0; i 1) // σβήστηκε και ελέγχουμε για δυνατότητα συγχώνευσης merge(Dir[i], i); nofItems--; // ενημέρωση του πλήθους των αποθηκευμένων αντικειμένων return true; } /* συγχωνεύει την σελίδα $p$ της $i$-στης θέσεως του καταλόγου με το φιλαράκι της, εάν γίνεται */ private void merge(page p, int i){ int bi, dp = p.getLocalDepth(), maxld; page buddy = Dir[bi = (bO.getBits(new Integer(i),dp, gd)^1)]; // το φιλαράκι Item[] el; // βοηθητική μεταβλητή για την συγχώνευση int bn = buddy.getnofItems(), pn = p.getnofItems(); if ((bn+pn < b)&&(bi != i)){ // υπάρχει φιλαράκι αρκετά άδειο, // ώστε να γίνει η συγχώνευση int min = (i < bi ? i: bi), max = (i > bi ? i: bi); int maxElems = Dir[max].getnofItems(); el = Dir[max].emptyPage(); // αδειάζουμε την σελίδα με την μεγαλύτερη θέση καταλόγου for (int j = 0; j < maxElems; j++) // μεταφορά των στοιχείων Dir[min].insertItem(el[j]); for (i = 0; i < gd-dp+1; i++) // ενημέρωση των θέσεων που δείχνουν την κενωθείσα Dir[(bO.getBits(new Integer(max),dp, gd ) << (gd-dp)) + i] = Dir[min]; Dir[min].decLocalDepth(); // ενημέρωση του τοπικού βάθους } maxld = Dir[0].getLocalDepth(); do { // αντιμετώπιση ενδεχόμενων διαδοχικών συμπτύξεων for (int j = 0; j < sizeofDir;j++) // υπολογισμός του μέγιστου maxld=Math.max(maxld, Dir[j].getLocalDepth()); // τοπικού βάθους if (gd > maxld){ // αναγκαία η σύμπτυξη του καταλόγου με υποδιπλασιασμό page[] oldDir = Dir; gd--; sizeofDir = sizeofDir / 2; Dir = new page[sizeofDir]; for (int j = 0; j < sizeofDir ; j++) Dir[j] = oldDir[j*2]; } } // όσο το ολικό βάθος παραμένει αδικαιολόγητα μεγάλο while(gd > maxld); } }// Τέλος extendibleHashing /////////////////// Κεφάλαιο 16 --- Ψηφιακά Δένδρα /////////////// /* Δομή Trie */ public class Trie extends LinkedBinaryTree { private int depth; // βοηθητική μεταβλητή-βάθος του τελευταίου ψαξίματος private comparator c; // $comparator$ για δυαδικό αλφάβητο Trie(comparator com) { // $constructor$ super(); c = com; } /* Βρίσκει τον κόμβο $w$, όπου πρέπει να τοποθετηθεί ένα στοιχείο με κλειδί $key$. Επίσης, ενημερώνει και την μεταβλητή $depth$ με το βάθος τού $w$ */ public BTNode findNode(BTNode v, Object key){ if (v.getElement()!= null) // φθάσαμε σε φύλλο return v; else if (c.isDigit0(depth,key)) { // πρέπει να πάμε αριστερά, if (v.getLeft() == null) // εφ' όσον μπορούμε return v; depth++; return findNode(v.getLeft(),key); } else { // πρέπει να πάμε δεξιά if (v.getRight() == null) // εφ' όσον μπορούμε return v; depth++; return findNode(v.getRight(), key); } } /* Ενθέτει ένα στοιχείο στην κατάλληλη θέση, εφ' όσον δεν υπάρχει ήδη, επιστρέφοντας $true$. Διαφορετικά, επιστρέφει $false$. */ public boolean insertItem(Item item){ depth = 0; if (size() == 0){ // η δομή μας είναι άδεια, οπότε το setRoot(new BTNode(item, null, null, null)); // $item$ θα γίνει το πρώτο στοιχείο setSize(1); return true; } Object itemKey = item.getKey(); // το κλειδί του στοιχείου. BTNode insNode = findNode(root(),itemKey); if (insNode.getElement() == null){ // η αναζήτηση κατέληξε σε εσωτερικό κόμβο if (insNode.getLeft() == null) // με έναν γιο $null$, ο οποίος θα δεχθεί το $item$ insNode.setLeft(new BTNode(item, insNode, null, null)); else insNode.setRight(new BTNode(item, insNode, null, null)); } else{ // η αναζήτηση καταλήγει σε φύλλο, οπότε πρέπει να γίνει επέκταση // μονοπατιού για να βρεθεί το ψηφίο διαχωρισμού boolean expand = true; // παραμένει $true$ όσο χρειάζεται να γίνει επέκταση Object insNodeKey = ((Item) insNode.getElement()).getKey(); if (c.equal(itemKey, insNodeKey)) // υπάρχει ήδη... return false; Object insItem = insNode.getElement(); insNode.setElement(null); // το φύλλο γίνεται εσωτερικός κόμβος while (expand){ boolean itemDigit = c.getDigit(depth, itemKey); boolean insNodeKeyDigit = c.getDigit(depth, insNodeKey); if (!(itemDigit^insNodeKeyDigit)){ // επέκταση, αφού και τα δύο είναι όμοια if (itemDigit){ // εάν το κοινό ψηφίο είναι $1$, επέκταση προς τα δεξιά insNode.setRight(new BTNode(null, insNode, null, null)); insNode = insNode.getRight(); } else{ // διαφορετικά, το κοινό ψηφίο είναι $0$ ---επέκταση προς τα αριστερά insNode.setLeft(new BTNode(null, insNode, null, null)); insNode = insNode.getLeft(); } depth++; // κατεβαίνουμε βαθύτερα στο δένδρο } else{ // βρέθηκε ο κόμβος για την προσθήκη των δύο νέων φύλλων που θα // στεγάζουν τα στοιχεία μας insNode.setRight((itemDigit ? new BTNode(item, insNode, null, null) : new BTNode(insItem, insNode, null, null)) ); insNode.setLeft( (itemDigit ? new BTNode(insItem, insNode, null, null): new BTNode(item, insNode, null, null)) ); expand = false; } } } return true; } // επιστρέφει το $item$ που με κλειδί $key$, εάν υπάρχει public Object findInfo(Object key){ BTNode insNode = findNode(root(),key); if (insNode.getElement() == null) return null; else if (c.equal(key,((Item)insNode.getElement()).getKey();)) return insNode.getElement(); } } // Τέλος Trie /* Κλάση για τα στοιχεία ενός Patricia Trie: αποτελεί επέκταση της γνωστής κλάσεως $Item$. Περιέχει, επιπροσθέτως, το ψηφίο-ετικέττα */ public class PatItem extends Item{ private int checkDigit; // το ψηφίο-ετικέττα PatItem( Object key, Object info, int d){ // $constructor$ super(key,info); checkDigit = d; } public int getCheckDigit(){ // επιστρέφει το ψηφίο return checkDigit; } public void setCheckDigit(int d){ // θέτει το ψηφίο checkDigit = d; } }// Τέλος PatItem /* Δομή Patricia Trie: Η κλάση αποτελεί επέκταση των δυαδικών δένδρων */ public class Patricia extends LinkedBinaryTree{ private comparator c; public Patricia(comparator com){ // $constructor$ super(); c = com; } /* Επιστρέφει τον κόμβο όπου θα πρέπει να βρίσκεται ένα $Item$ με κλειδί $key$. Αρχική τιμή του $digit$ ίση με -$1$, κατόπιν ίση με το τελευταίο ψηφίο ελέγχου που εξετάσαμε */ public BTNode findNode(BTNode v, Object key, int digit){ if (v == null) return null; int vChkDigit = ((PatItem) v.getElement()).getCheckDigit(); if (vChkDigit <= digit) // ακολουθήσαμε δείκτη προς τα επάνω return v; if (c.isDigit0(vChkDigit,key)) // το ψηφίο-ετικέττα είναι $0$, πηγαίνουμε αριστερά return findNode(v.getLeft(),key,vChkDigit); else // το ψηφίο-ετικέττα είναι $1$, πηγαίνουμε δεξιά return findNode(v.getRight(), key, vChkDigit); } /* Ενθέτει, εάν δεν υπάρχει άλλο $PatItem$ με ίδιο κλειδί, το $item$ επιστρέφοντας $true$. Διαφορετικά, επιστρέφει $false$ */ public boolean insertItem(PatItem item){ int firstDifDigit = 0; // κρατά την πρώτη θέση, όπου το κλειδί του $item$ και // το αντίστοιχο του στοιχείου του δένδρου διαφέρουν Object itemKey = item.getKey(); // το κλειδί του $item$ if (size() == 0){ // το δένδρο μας είναι άδειο BTNode v; int i = 0; while(c.isDigit0(i, itemKey)) // βρίσκει την πρώτη θέση με \ytib{1} i++; item.setCheckDigit(i); setRoot(v = new BTNode(item, null, null, null)); v.setRight(v); setSize(1); return true; } BTNode insNode = findNode(root(), itemKey, -1); PatItem insItem; Object insNodeKey = null; if (insNode == null) // φθάσαμε στον ακραίο αριστερό κόμβο του δένδρου while (c.isDigit0(firstDifDigit,itemKey) && (firstDifDigit= N) // εκτός ορίων! return null; int succ; if (T == null) // κενή η δομή $veb$ return null; if ((succ = T.findSuccessor(i,nofbits)) == -1) // δεν υπάρχει return null; else // υπάρχει και το αναζητάμε στο λεξικό return D.findItem(new Integer(succ)); } // εύρεση του μεγαλύτερου κλειδιού (προηγούμενου) που είναι μικρότερο ή ίσο // του $i$ public Item findPredeccessor(int i){ if (i >= N) // εκτός ορίων! return null; int pred; if (T == null) // κενή η δομή $veb$ return null; if ((pred = T.findPredecessor(i,nofbits)) == -1) // δεν υπάρχει return null; else // υπάρχει και το αναζητάμε στο λεξικό return D.findItem(new Integer(pred)); } // εισαγωγή του στοιχείου $item$ στην δομή public int insertItem(Item item){ Object itemKey = item.getKey(); // το κλειδί Object itemInfo = item.getInfo(); // η συσχετιζόμενη πληροφορία DNode itemNode; int i = ((Integer)itemKey).intValue(); if (i >= N) // εκτός ορίων! return 0; else if (D.findItem(itemKey) != null) // υπάρχει ήδη! return 1; int pred = i, succ = i; if (T == null) // άδεια δομή $Veb$ --πρέπει να αρχικοποιηθεί T = new vebTreeRecursive(nofbits,i); else { // υφίσταται δομή if ((pred = T.findPredecessor(i, nofbits)) == -1){ succ = T.getMin(); if (!T.insertItem(i,nofbits)) return 1; // υπάρχει ήδη το κλειδί } if (pred < i) { // υπάρχει προηγούμενος --θα συνδεθεί με το νέο στοιχείο DNode preDNode = (pred!=-1 ?(DNode)D.findInfo(new Integer(pred)):null); itemNode = new DNode(preDNode,(preDNode != null? preDNode.getNext(): null),itemInfo); } else if (i < succ) { // υπάρχει επόμενος --θα συνδεθεί με το νέο στοιχείο DNode succDNode = (DNode)D.findInfo(new Integer(succ)); itemNode = new DNode((succDNode != null ? succDNode.getPrev() : null),succDNode,itemInfo); } else // το στοιχείο είναι μόνο του itemNode = new DNode(null,null,itemInfo); // ένταξη του στοιχείου στην διπλή λίστα if (itemNode.getNext() != null) itemNode.getNext().setPrev(itemNode); if (itemNode.getPrev() != null) itemNode.getPrev().setNext(itemNode); D.insertItem(new Item(itemKey,itemNode)); // ένταξη στο βοηθητικό λεξικό return 2; // όλα εντάξει! } // διαγραφή του στοιχείου με κλειδί $key$, εάν υπάρχει public Object deleteItem(Object key){ DNode itemNode; Object itemInfo; int i = ((Integer)key).intValue(); if (i >= N) // εκτός ορίων! return null; else if ((itemNode = (DNode)D.findInfo(key)) == null) // υπάρχει ήδη! return null; if (T == null) // άδεια δομή $Veb$ return null; if (T.deleteItem(i,nofbits) == false) return null; // αφαίρεση του στοιχείου από την διπλή λίστα if (itemNode.getNext() != null) itemNode.getNext().setPrev(itemNode.getPrev()); if (itemNode.getPrev() != null) itemNode.getPrev().setNext(itemNode.getNext()); // απόσβεση του στοιχείου από το βοηθητικό λεξικό return D.deleteItem(key); } // υπολογισμός του δυαδικού λογαρίθμου private int log2(int n){ return ((int)(Math.log(n)/Math.log(2.0))); } public int getNofbits(){ return nofbits; } }// Τέλος vebTree /* Κεντρική Αναδρομική Δομή veb */ public class vebTreeRecursive{ protected int size; // πλήθος αποθηκευμένων στοιχείων protected int max; // μέγιστο κλειδί protected int min; // ελάχιστο κλειδί // βοηθητικές σταθερές protected static final int noItem = 0; // δεν υπάρχει στοιχείο protected static final int singleItem = 1;// υπάρχει ένα μοναδικό στοιχείο protected static final int Tree = 2; // υπάρχει δένδρο protected vebTreeRecursive top; // αναδρομικό άνω δένδρο dynamicPerfectHashing bottom; // λεξικό για τα κάτω δένδρα int bitmap = 0; // $bitmap$ για την ομαδοποίηση $\# \log\!\log N$ στοιχείων protected static final int wordlength = 32; // μήκος λέξεως $w$ protected static final int microlength = 3; // $O(\log\!\log w)$ // επιστρέφει τα μισά λιγότερο σημαντικά μπιτ του $x$ public static int lowerHalf(int x, int halfmask){ return x & halfmask; } // επιστρέφει τα μισά περισσότερο σημαντικά μπιτ του $x$ public static int upperHalf(int x, int halfbits){ return x >> halfbits; } // συνενώνει τα $x,y$ σε έναν αριθμό, διπλάσιου μήκους public static int catenate(int x, int y, int halfbits){ return ((x << halfbits) | (y)); } public vebTreeRecursive(int nofbits, int single) { // $constructor$ int mask = (1 << nofbits)-1; size = 1; min = max = single; // αποθήκευση του $single$ bottom = new dynamicPerfectHashing(null, new comparator()); top = null; bitmap = ((nofbits <= microlength) ? 1 << (single & mask) : 0); } // αναδρομική εισαγωγή του $i$, μήκους $nofbits$, στην δομή public boolean insertItem(int i, int nofbits){ if (nofbits <= microlength){ // πρέπει να σταματήσει η αναδρομή int bitI = 1 << i; // η θέση του $i$ στο $bitmap$ if ((bitI & bitmap) != 0) // υπάρχει ήδη return false; bitmap |= bitI; // ένθεση με ((άναμμα)) του μπιτ if (i > max) max = i; if (i < min) min = i; size++; // ενημέρωση μεγέθους return true; } else if ((i == min) || (i == max)) // υπάρχει ήδη return false; else { // κανονική ένθεση vebTreeRecursive bot; int halfbits = nofbits >> 1; int halfmask = (1 << halfbits) - 1, a; if (bottom == null) // αρχικοποίηση κενής κάτω δομής bottom = new dynamicPerfectHashing(null,new comparator()); size++; // ενημέρωση μεγέθους if (i > max) // ενημέρωση μεγίστου στοιχείου max = i; if (i < min) { // το $i$ νέο ελάχιστο --ανταλλαγή ρόλων int newmin = i; // με το παλιό i = min; min = newmin; } a = upperHalf(i,halfbits); // τα μισά σημαντικότερα μπιτ // αναζήτηση αντιστοίχου γκρουπ Item item = (Item) bottom.findInfo(new Integer(a)); if (item == null){ // δεν υπάρχει γκρουπ if (top == null) // και δεν υπάρχει πάνω δομή top = new vebTreeRecursive(halfbits,a); // αρχικοποίηση // και εισαγωγή else // εισαγωγή στην υπάρχουσα πάνω δομή top.insertItem(a,halfbits); // δημιουργία αντίστοιχου {\bf μη αναδρομικού} στοιχειώδους // γκρουπ-στοιχείου bottom.insertItem(new Item(new Integer(a),new Item(new Integer(singleItem), new Integer(lowerHalf(i,halfmask))))); return true; } else{ // αλλιώς δημιουργία και εισαγωγή νέου δένδρου-γκρουπ if (((Integer)item.getKey()).intValue() == singleItem){ // υπήρχε {\bf μη αναδρομικό} στοιχειώδες γκρουπ-στοιχείο, το οποίο // θα αντικατασταθεί από αναδρομική δομή bot = new vebTreeRecursive(halfbits,((Integer)item.getInfo()).intValue()); // η αντικατάσταση bottom.deleteItem(new Integer(a)); bottom.insertItem(new Item(new Integer(a),new Item(new Integer(Tree),bot))); // εισαγωγή των μισών λιγότερο σημαντικών μπιτ στην νέα δομή bot.insertItem(lowerHalf(i,halfmask), halfbits); } else { // υπάρχει ήδη δομή-γκρουπ κάτω επιπέδου bot = (vebTreeRecursive) item.getInfo(); // η δομή // εισαγωγή των μισών λιγότερο σημαντικών μπιτ bot.insertItem(lowerHalf(i,halfmask), halfbits); return true; } } } return true; } // αναδρομική διαγραφή του $i$, μήκους $nofbits$, από την δομή public boolean deleteItem(int i, int nofbits){ if (nofbits <= microlength){ // πρέπει να σταματήσει η αναδρομή int bitI = 1 << i; // η θέση του $i$ στο $bitmap$ if ((bitI & bitmap) == 0) // δεν υπάρχει το κλειδί! return false; bitmap &= (~bitI); // διαγραφή με ((σβήσιμο)) του μπιτ size--; // ενημέρωση μεγέθους if (size > 0){ // ενημέρωση μεγίστου και ελαχίστου max = msb(bitmap); min = lsb(bitmap); } return true; } if (size <= 1) { // μόνο εάν είμαστε στην ρίζα κορυφαίου δένδρου size--; bottom = null; // άδειασμα της κάτω δομής return true; } else { // διαγραφή από ((κανονική)) δομή int halfbits = nofbits >> 1; int halfmask = (1 << halfbits) - 1, a; vebTreeRecursive bot; if (i == min) { // εύρεση και αντικατάσταση από το νέο $min$ a = top.getMin(); // υπάρχει η πληροφορία στην πάνω δομή // ανάκτηση του αντίστοιχου γκρουπ της κάτω δομής, ώστε να // διαγραφεί το ελάχιστό της και να αποθηκευτεί ως $min$ Item item = (Item) bottom.findInfo(new Integer(a)); int typeofItem = ((Integer)item.getKey()).intValue(); // η κάτω δομή αποτελείται από ένα μόνο στοιχείο if (typeofItem == singleItem){ // διαγραφή και από τα δύο επίπεδα bottom.deleteItem(new Integer(a)); top.deleteItem(a, halfbits); // το νέο ελάχιστο min = catenate(a,((Integer)item.getInfo()).intValue(),halfbits); } else{ // κανονική αναδρομική κάτω δομή bot = (vebTreeRecursive)(item.getInfo()); min = catenate(a,bot.getMin(),halfbits); // το νέο $min$ i = min; bot.deleteItem(lowerHalf(i,halfmask), halfbits); // διαγραφή του if (bot.getSize() == 1) // αντικατάσταση από // μοναδικό στοιχείο-γκρουπ bottom.insertItem(new Item(new Integer(a),new Item(new Integer(singleItem), new Integer(bot.getMin())))); } } else{ // ((κανονική)) αναδρομική διαγραφή a = upperHalf(i,halfbits); Item item = (Item)bottom.findInfo(new Integer(a)); int typeofItem = ((Integer)item.getKey()).intValue(); if (typeofItem == singleItem) { // συναντήσαμε στοιχείο-γκρουπ bottom.deleteItem(new Integer(a));// διαγραφή και από τα 2 επίπεδα top.deleteItem(a,halfbits); if (i == max) { // σβήσαμε το μέγιστο: πρέπει να // το αντικαταστήσουμε if (size == 2) // εύκολη περίπτωση max = min; else { // πρέπει να βρούμε το μέγιστο a = top.getMax(); Item itm = (Item)bottom.findInfo(new Integer(a)); int typeofItm = ((Integer)itm.getKey()).intValue(); if (typeofItm == singleItem) max = catenate(a,((Integer) itm.getInfo()).intValue(), halfbits); else { bot = (vebTreeRecursive)(itm.getInfo()); max = catenate(a, bot.getMax(),halfbits); } } } } else { // συναντήσαμε ((κανονική)) κάτω δομή-δένδρο bot = (vebTreeRecursive) item.getInfo(); bot.deleteItem(lowerHalf(i,halfmask), halfbits); // διαγραφή if (i == max) max = catenate(a, bot.getMax(),halfbits); // νέο $max$ if (bot.getSize() == 1) // αποθήκευση ως στοιχείο-γκρουπ bottom.insertItem(new Item(new Integer(a),new Item(new Integer(singleItem), new Integer(bot.getMin())))); } } size--; // ενημέρωση μεγέθους if (size <= 1) bottom = null; // αποδέσμευση κάτω δομής return true; } } /* εύρεση του μεγαλύτερου κλειδιού (προηγούμενου) που είναι μικρότερο ή ίσο του $i$, μήκους $nofbits$ μπιτ */ public int findPredecessor(int i, int nofbits){ if (size == 0) // άδεια δομή return -1; else if (max <= i) // εύκολες περιπτώσεις return max; else if (min > i) return -1; else if (nofbits <= microlength){ // πρέπει να σταματήσει η αναδρομή int bitI = 1 << i; if ((bitI & bitmap) != 0) // βρέθηκε return i; else // αλλιώς, ο προηγούμενος ως το πιο σημαντικό αναμμένο μπιτ return msb((bitI - 1) & bitmap); } else { // $0> 1; int halfmask = (1 << halfbits) - 1; int j = min; boolean predFound = false; int a = upperHalf(i,halfbits); // τα μισά σημαντικότερα στοιχεία Item item = (Item) bottom.findInfo(new Integer(a)); // το γκρουπ int typeofItem = 0; if (item!=null) // υπάρχει γκρουπ typeofItem = ((Integer)item.getKey()).intValue(); if (typeofItem == noItem) // δεν υπάρχει ; else if (typeofItem == singleItem){ // μοναδικό στοιχείο - γκρουπ // έλεγχος εάν είναι προηγούμενος if (((Integer)item.getInfo()).intValue() <= lowerHalf(i,halfmask)) { // ο προηγούμενος προκύπτει από την συνένωση j = catenate(a,((Integer)item.getInfo()).intValue(),halfbits); predFound = true; } } else { // κανονική δομή - γκρουπ vebTreeRecursive bot = (vebTreeRecursive) item.getInfo();// δένδρο if (bot.getMin() <= lowerHalf(i,halfmask)) { // βρέθηκε! // ο προηγούμενος προκύπτει από την συνένωση j = catenate(a,bot.findPredecessor(lowerHalf(i,halfmask),halfbits),halfbits); predFound = true; } } if ((!predFound) && (a > 0)) { // το $i$ δεν ανήκει, θα ψάξουμε την πάνω δομή για το προηγούμενο γκρουπ int d = top.findPredecessor(a-1,halfbits); if (d >= 0){ // υπάρχει προηγούμενο γκρουπ item = (Item)bottom.findInfo(new Integer(d)); typeofItem = ((Integer)item.getKey()).intValue(); if (typeofItem == singleItem) // εντοπίσαμε γκρουπ-στοιχείο // ο προηγούμενος προκύπτει από την συνένωση j = catenate(d,((Integer)item.getInfo()).intValue(),halfbits); else { // εντοπίσαμε γκρουπ-κανονική δομή vebTreeRecursive bot = (vebTreeRecursive)item.getInfo(); // ο προηγούμενος προκύπτει από την συνένωση j = catenate(d, bot.getMax(),halfbits); } predFound = true; } } return (!predFound ? min : j); } } /* εύρεση του μικρότερου κλειδιού (επόμενου) που είναι μεγαλύτερο ή ίσο του $i$, μήκους $nofbits$ μπιτ */ public int findSuccessor(int i, int nofbits){ if (size == 0) // άδεια δομή return -1; else if (min >= i) // εύκολες περιπτώσεις return min; else if (max == i) return max; else if (max < i) return -1; else if (nofbits <= microlength){ // πρέπει να σταματήσει η αναδρομή int bitI = 1 << i; if ((bitI & bitmap)!=0) // βρέθηκε return i; else // αλλιώς, ο προηγούμενος ως το λιγότερο σημαντικό αναμμένο μπιτ return lsb(~((bitI << 1) - 1) & bitmap); } else { // $0> 1; int halfmask = (1 << halfbits) - 1; int j = max, c; boolean succFound = false; int a = upperHalf(i,halfbits); // τα μισά σημαντικότερα στοιχεία Item item = (Item) bottom.findInfo(new Integer(a)); // το γκρουπ int typeofItem=0; if (item!=null) // υπάρχει γκρουπ typeofItem = ((Integer)item.getKey()).intValue(); if (typeofItem == noItem) // δεν υπάρχει ; else if (typeofItem == singleItem){ // μοναδικό στοιχείο - γκρουπ // έλεγχος εάν είναι ακόλουθο στοιχείο if ( (c = ((Integer)item.getInfo()).intValue()) >= lowerHalf(i,halfmask)) { // ο ακόλουθος προκύπτει από την συνένωση j = catenate(a,c,halfbits); succFound = true; } } else { // κανονική δομή - γκρουπ vebTreeRecursive bot = (vebTreeRecursive) item.getInfo();// δένδρο if (bot.getMax() >= lowerHalf(i,halfmask)){ // βρέθηκε! // ο ακόλουθος προκύπτει από την συνένωση j = catenate(a,bot.findSuccessor(lowerHalf(i,halfmask),halfbits),halfbits); succFound = true; } } if ((!succFound) && (a < halfmask)) { // το $i$ δεν ανήκει, θα ψάξουμε την πάνω δομή για το επόμενο γκρουπ int d = top.findSuccessor(a+1,halfbits); if (d >= 0){ // υπάρχει επόμενο γκρουπ item = (Item) bottom.findInfo(new Integer(d)); typeofItem = ((Integer)item.getKey()).intValue(); if (typeofItem == singleItem) // εντοπίσαμε γκρουπ-στοιχείο // ο ακόλουθος προκύπτει από την συνένωση j = catenate(d,((Integer)item.getInfo()).intValue(),halfbits); else { // εντοπίσαμε γκρουπ-κανονική δομή vebTreeRecursive bot = (vebTreeRecursive)item.getInfo(); // ο ακόλουθος προκύπτει από την συνένωση j = catenate(d, bot.getMin(),halfbits); } succFound = true; } } return j; } } // απλές μέθοδοι αντλήσεως πληροφορίας public int getSize(){ return size; } public int getMax(){ return max; } public int getMin(){ return min; } // επιστροφή του πιο σημαντικού, θεμένου στην τιμή 1, μπιτ του $n$ public static int msb(int n) { int top = 32; // $8*IntLength()$ int bot = 0; while (top-bot>1){ int mid = (top+bot) >> 1; if (n >= (1 << mid)) bot = mid; else top = mid; } return bot; } // επιστροφή του λιγότερου σημαντικού, θεμένου στην τιμή 1, μπιτ του $n$ public static int lsb(int n){ int wordsize = 32; // $8*IntLength()$ int res = wordsize >> 1; int delta = res >> 1; while (delta > 0){ res += ((n << res)!=0 ? delta : -delta); delta = delta >> 1; } res += ((n<= level){ System.out.println("Δεν υπάρχει γείτονας επιπέδου "+l); return null; } return next[l]; } // θέτει τον δείκτη επιπέδου $l$ να δείχνει στον $v$ public void setNextNode(int l, skipListNode v) { if (l >= level){ System.out.println("Αδύνατη η τοποθέτηση δείκτη σε επίπεδο"+l); return; } next[l] = v; } }// Τέλος skipListNode /* Δομή λίστας αναπηδήσεως */ public class skipList { private skipListNode head; // κεφαλή private int Level; // το τρέχον επίπεδο της δομής private static Random ran; // η συνάρτηση $random$ private static comparator c; // $comparator$ για τις συγκρίσεις private static int maxLevel; // μέγιστο επιτρεπόμενο επίπεδο private int nofItems; // πλήθος στοιχείων στην δομή public SkipList(int maxL, comparator com) { // $constructor$ head = new skipListNode(null,maxL); Level = 0; maxLevel = maxL; ran = new Random(); c = com; nofItems = 0; } public int getNofItems() { // επιστρέφει το πλήθος των στοιχείων return nofItems; } public Random getRandom(){ // επιστρέφει την $random$ return ran; } public int getMaxLevel(){ // επιστρέφει το άνω όριο επιπέδου return maxLevel; } // αναδρομική αναζήτηση από κόμβο επιπέδου $l$ για το κλειδί $key$ public Item searchNode(Object key, skipListNode v, int l) { skipListNode nextNode = v.getNextNode(l); // δεν γίνεται να μετακινηθούμε δεξιότερα if ( (nextNode == null) || (c.less(key,nextNode.getItem().getKey())) ) { if (l == 0) // αδιέξοδο! return null; else // κατεβαίνουμε ένα επίπεδο κάτω return searchNode(key, v, l-1); } else // δυνατή η μετακίνηση προς τα δεξιά if (c.equal(key, nextNode.getItem().getKey())) return nextNode.getItem(); // ανεύρεση στον δεξιό κόμβο else return searchNode(key, nextNode,l); // μετάβαση δεξιά, στο ίδιο επίπεδο } // εκκίνηση της αναδρομικής διαδικασίας public boolean searchItem(Object key){ Item i = searchNode(key,head,Level); return (i == null ? false : true); } /* αναδρομική εισαγωγή νέου κόμβου $insNode$, με κλειδί $insKey$, δεξιά του $v$ σε επίπεδο $l$ */ private boolean insertNode(skipListNode v, skipListNode insNode, Object insKey, int l){ skipListNode nextNode = v.getNextNode(l); // ο επόμενος του $v$ Object nodeKey; if ((nextNode == null) || (c.less(insKey, nodeKey = nextNode.getItem().getKey())) ) { // βάσει κλειδιού, είναι μεταξύ του $v$ και του $nextNode$ if (l < insNode.getLevel()){ // είμαστε και σε νόμιμο επίπεδο insNode.setNextNode(l,nextNode); // τοποθέτηση ενδιάμεσα v.setNextNode(l,insNode); } if (l == 0) // ήδη στο χαμηλότερο επίπεδο return true; else // διαφορετικά, η εισαγωγή πρέπει να γίνει σε χαμηλότερο επίπεδο return insertNode(v, insNode, insKey, l-1); } else if (c.equal(insKey, nodeKey = nextNode.getItem().getKey())) return false; // υπάρχει το κλειδί, αδύνατη η εισαγωγή else // τοποθέτηση δεξιότερα, στο ίδιο επίπεδο return insertNode(nextNode,insNode,insKey,l); } // εισαγωγή του $i$ στην δομή, εάν δεν υπάρχει ήδη στοιχείο με ίδιο κλειδί public boolean insertItem(Item i) { int insLevel = getRandom().nextInt(getMaxLevel()-1)+1; // καθορισμός επιπέδου Level = (insLevel <= Level ? Level : (insLevel = Level+1)); if (insertNode(head, new skipListNode(i,insLevel), i.getKey(), Level)){ // επιτυχία nofItems++; // ενημέρωση πληθαρίθμου δομής return true; } else return false; // αποτυχία } /* αναδρομική διαγραφή κόμβου με κλειδί $insKey$, δεξιά του $v$ σε επίπεδο $l$ */ private boolean removeNode(skipListNode v, Object key, int l) { if (l == -1) return false; // βάση αναδρομής, ξεπεράσαμε το χαμηλότερο επίπεδο skipListNode nextNode = v.getNextNode(l); // δεξιός κόμβος του $v$ επιπέδου $l$ Object nodeKey; if (nextNode == null) // φθάσαμε στο δεξί άκρο της δομής... return removeNode(v, key, l-1); // κινούμαστε προς τα κάτω else // υπάρχει δεξιός κόμβος if ((c.less(nodeKey = nextNode.getItem().getKey(),key)) ) // με μικρότερο κλειδί, οπότε, κινούμαστε προς αυτόν return removeNode(nextNode,key, l); else { // διαφορετικά, υπάρχει δεξιός κόμβος με κλειδί $\geq key$ boolean flag = false; if (flag = c.equal(nodeKey,key)) // o δεξιός κόμβος έχει το κλειδί v.setNextNode(l,nextNode.getNextNode(l)); // τον παρακάμπτουμε if (l == 0) return flag; // πιάσαμε βάση return removeNode(v, key, l-1); // διαφορετικά, κινούμαστε προς τα κάτω } } // διαγραφή του στοιχείου με κλειδί $key$ από την δομή, εάν υπάρχει τέτοιο public boolean deleteItem(Object key) { if (removeNode(head, key, Level)) { // επιτυχία nofItems--; // ενημέρωση πληθαρίθμου δομής return true; } else return false; } }// Τέλος skipList /* Κλάση στοιχείου δομής treap: επέκταση της κλάσεως $Item$, ώστε να υπάρχει η προτεραιότητα στοιχείου */ public class treapItem extends Item{ private int priority; // η προτεραιότητα public treapItem (Object k, Object i, int pr) { // $constructor$ super(k,i); priority = pr; } public int getPriority() { // επιστρέφει την προτεραιότητα return priority; } public void setPriority(int pr) { // θέτει την προτεραιότητα priority = pr; } }// Τέλος treapItem /* Δομή λεξικού treap */ public class Treap extends BinarySearchTree { private static Random ran; // η συνάρτηση $Random$ public Treap(comparator com){ // $constructor \#1$ super(com); ran = new Random(230870); } public Treap(Item i, comparator com){ // $constructor \#2$ super(i,com); ran = new Random(140900); } public int getPriority(){ // επιστρέφει τυχαίο αριθμό return ran.nextInt(300); } // δεξιά περιστροφή, ώστε ο $v$ να γίνει παιδί του $w$ private void rotateLeft(BTNode w, BTNode v){ if (!isRoot(v)){ if (isRight(v)) v.getParent().setRight(w); else v.getParent().setLeft(w); w.setParent(v.getParent()); } v.setRight(w.getLeft()); if (w.getLeft() != null) w.getLeft().setParent(v); w.setLeft(v); v.setParent(w); if (isRoot(v)) { setRoot(w); w.setParent(null); } } // αριστερή περιστροφή, ώστε ο $v$ να γίνει παιδί του $w$ private void rotateRight(BTNode w, BTNode v){ if (!isRoot(v)){ if (isLeft(v)) v.getParent().setLeft(w); else v.getParent().setRight(w); w.setParent(v.getParent()); } v.setLeft(w.getRight()); if (w.getRight() != null) w.getRight().setParent(v); w.setRight(v); v.setParent(w); if (isRoot(v)) { setRoot(w); w.setParent(null); } } // διαγραφή του στοιχείου με κλειδί $key$ από την δομή, εάν υπάρχει τέτοιο public BTNode deleteItem(Object key) { if (size() == 0) return null; // η δομή είναι κενή! BTNode delNode = findNode(key, root()); // αναζήτηση του κλειδιού Object keyNode=((Item)delNode.getElement()).getKey(); if (!c.equal(keyNode, key)) // δεν υπάρχει return null; else { // υπάρχει int lpriority, rpriority; BTNode minNode = delNode, lchild = null, rchild = null; while (((lchild = delNode.getLeft()) != null) || // όσο δεν βρίσκουμε ((rchild = delNode.getRight()) != null)){ // κενό φύλλο // προτεραιότητα αριστερού γιου, εάν υπάρχει lpriority = (lchild != null ? ((treapItem) lchild.getElement()).getPriority() : -1); // προτεραιότητα δεξιού γιου, εάν υπάρχει rpriority = (rchild!=null ? ((treapItem)rchild.getElement()).getPriority() : -1); // γιος με το μικρότερο νούμερο προτεραιότητας minNode = (lchild == null ? rchild : (rchild == null ? lchild : ((lpriority < rpriority)?lchild:rchild))); if (minNode == rchild) // αριστερή περιστροφή, εφ' όσον δεξιός γιος προηγείται rotateLeft(rchild, delNode); else // δεξιά περιστροφή, αφού ο αριστερός σημαντικότερος rotateRight(lchild, delNode); } if (isRoot(delNode)) // κένωση δένδρου setRoot(null); else // γείωση δείκτη πατέρα if (isRight(delNode)) delNode.getParent().setRight(null); else delNode.getParent().setLeft(null); size--; // ενημέρωση μεγέθους return delNode; } } // εισαγωγή του στοιχείου $i$ στην δομή, εάν υπάρχει άλλο με ίδιο κλειδί public BTNode insertItem(treapItem i) { BTNode insNode = super.insertItem(i); // εισαγωγή όπως στα αζύγιστα if (insNode == null) return null; // υπάρχει το κλειδί // απόδοση προτεραιότητας στο στοιχείο int insPriority = ((treapItem) insNode.getElement()).getPriority(); while(!isRoot(insNode) && // όσο το στοιχείο έχει μικρότερο νούμερο (insPriority<((treapItem)insNode.getParent().getElement()).getPriority())) if (isLeft(insNode)) // ανάβαση με δεξιά περιστροφή rotateRight(insNode,insNode.getParent()); else // ανάβαση με αριστερή περιστροφή rotateLeft(insNode, insNode.getParent()); return insNode; } }// Τέλος Treap //////////////// Κεφάλαιο 21 --- Δομές Λεξικού Επιμερίσεως ή Τοκοχρεωλυσίου //////////////// /* Εξαρθρωμένο δένδρο */ public class splayTree extends BinarySearchTree { public SplayTree(comparator com){ // $constructor \#1$ super(com); } private BTNode splay(BTNode v){ // η βασική πράξη του δένδρου if (v == null) return null; BTNode parent = v.getParent(), grandparent = (parent != null ? parent.getParent() : null); while (parent != null) { // όσο δεν φθάσαμε στην ρίζα if (isLeft(v)){ // αριστερός κόμβος if (grandparent == null) // παιδί της ρίζας v = rRot(parent,v); else if (isLeft(parent)) // $zig-zig$ v = rRot(rRot(grandparent,parent),v); else // $zig-zag$ v = lDRot(grandparent,parent,v); } else{ // δεξιός κόμβος if (grandparent == null) // παιδί της ρίζας v = lRot(parent,v); else if (isRight(parent)) // $zig-zig$ v = lRot(lRot(grandparent,parent),v); else // $zig-zag$ v = rDRot(grandparent,parent,v); } parent = v.getParent(); grandparent = (parent != null ? parent.getParent() : null); } return v; } // δεξιά περιστροφή, ώστε ο $w$ να γίνει πατέρας του $v$ private BTNode rRot(BTNode v, BTNode w){ boolean notRoot; if (notRoot = (v.getParent() != null)){ if (isLeft(v)) v.getParent().setLeft(w); else v.getParent().setRight(w); w.setParent(v.getParent()); } v.setLeft(w.getRight()); if (w.getRight() != null) w.getRight().setParent(v); w.setRight(v); v.setParent(w); if (!notRoot) w.setParent(null); return w; } // αριστερή περιστροφή, ώστε ο $w$ να γίνει πατέρας του $v$ private BTNode lRot(BTNode v, BTNode w){ boolean notRoot; if (notRoot = (v.getParent() != null)){ if (isRight(v)) v.getParent().setRight(w); else v.getParent().setLeft(w); w.setParent(v.getParent()); } v.setRight(w.getLeft()); if (w.getLeft() != null) w.getLeft().setParent(v); w.setLeft(v); v.setParent(w); if (!notRoot) w.setParent(null); return w; } // δεξιά διπλή περιστροφή, ώστε ο $u$ να γίνει πατέρας των $v,w$ private BTNode rDRot(BTNode v, BTNode w, BTNode u){ boolean notRoot; v.setLeft(u.getRight()); if (u.getRight() != null) u.getRight().setParent(v); w.setRight(u.getLeft()); if (u.getLeft() != null) u.getLeft().setParent(w); if (notRoot = (v.getParent() != null)){ if (isLeft(v)) v.getParent().setLeft(u); else v.getParent().setRight(u); u.setParent(v.getParent()); } v.setParent(u); w.setParent(u); u.setLeft(w); u.setRight(v); if (!notRoot) u.setParent(null); return u; } // αριστερή διπλή περιστροφή, ώστε ο $u$ να γίνει πατέρας των $v,w$ private BTNode lDRot(BTNode v, BTNode w, BTNode u){ boolean notRoot; v.setRight(u.getLeft()); if (u.getLeft() != null) u.getLeft().setParent(v); w.setLeft(u.getRight()); if (u.getRight() != null) u.getRight().setParent(w); if (notRoot =(v.getParent() != null)){ if (isRight(v)) v.getParent().setRight(u); else v.getParent().setLeft(u); u.setParent(v.getParent()); } v.setParent(u); w.setParent(u); u.setLeft(v); u.setRight(w); if (!notRoot) u.setParent(null); return u; } public BTNode insertItem(Item i){ // εισαγωγή του στοιχείου $i$ BTNode insNode = super.insertItem(i); // ένθεση, όπως στα αζύγιστα if (insNode == null) return null; setRoot(splay(insNode)); // ((εξάρθρωση)), ώστε να γίνει ρίζα return root(); } // αναζήτηση και κατόπιν εξάρθρωση public BTNode splayfindNode(Object key, BTNode v){ BTNode sNode = findNode(key, v); return splay(sNode); } // εξάρθρωση και απόσβεση στοιχείου με κλειδί $key$, εάν υπάρχει public BTNode deleteItem(Object key){ if (size() == 0) return null; BTNode sNode = splayfindNode(key, root()); // αναζήτηση και εξάρθρωση Object keyNode = ((Item) sNode.getElement()).getKey(); if (!c.equal(keyNode, key)) // δεν υπάρχει return null; if (size() == 1) setRoot(null); else if (sNode.getLeft() == null) { // κενό αριστερό υποδένδρο setRoot(sNode.getRight()); // διαγραφή ρίζας root().setParent(null); } else { // υπάρχει BTNode left = sNode.getLeft(), temp; left.setParent(null); temp = splayfindNode(key,left); // ανέβασμα του μεγαλύτερου στοιχείου temp.setRight(sNode.getRight()); // του αριστερού υποδένδρου if (sNode.getRight() != null) // ώστε να γίνει η νέα ρίζα και πατέρας sNode.getRight().setParent(temp); // του δεξιού ((αδελφού)) υποδένδρου setRoot(temp); root().setParent(null); } sNode.setLeft(null); sNode.setRight(null); // γείωση και ενημέρωση sNode.setParent(null); setSize(size()-1); return sNode; } // αναζήτηση του κλειδιού $key$, εάν υπάρχει public Object findInfo(Object key, BTNode v){ setRoot(splayfindNode(key,v)); if (((Item) root().getElement()).getKey() == key) return ((Item) root().getElement()).getInfo(); else return null; } }// Τέλος splayTree /* Δένδρα εξιλαστήριου κόμβου */ public class scapeGoatTree extends BinarySearchTree { protected int maxSize; // μέγιστο παρατηρούμενο μέγεθος protected float a; // παράγων βάρους public ScapeGoatTree(comparator c, float parameter){ // $constructor \#1$ super(c); maxSize = 0; a = parameter; } public float geta(){ // επιστρέφει το α return a; } public void seta(int parameter){ // θέτει το α a=parameter; } public int getmaxSize(){ // επιστρέφει το μέγιστο μέγεθος return maxSize; } private int getDepth(BTNode v){ // υπολογίζει το βάθος του $v$ if (isRoot(v)) return 0; return 1+getDepth(v.getParent()); } private int getSize(BTNode v){ // υπολογίζει το μέγεθος του $T_v$ if (v == null) return 0; return getSize(v.getRight())+getSize(v.getLeft())+1; } private int getHeight(){ // υπολογίζει το ((ιδανικό ύψος)) return ((int) (Math.log(size())/Math.log(1.0/a))); } // αναδρομική εύρεση του κόμβου αναδομήσεως private BTNode findScapegoat(BTNode v, int s1){ if (isRoot(v)) return v; BTNode p = v.getParent(); // ο πατέρας int s2 = getSize(getSibling(v)), sizeparent = s1+s2+1; if ((s1>(a*sizeparent))||(s2>(a*sizeparent))) // τον βρήκαμε! return p; else // μετάβαση στον πατέρα... return findScapegoat(p, sizeparent); } // επιστρέφει την λίστα των κόμβων του $T_v$ κατά μη φθίνουσα σειρά private BTNode flatten(BTNode v, BTNode w){ if (v == null) return w; // βάση αναδρομής v.setRight(flatten(v.getRight(),w)); return flatten(v.getLeft(),v); } // αναδρομική αναδόμηση υποδένδρου, δοθέντος αρχικού κόμβου private BTNode build(int n, BTNode v){ if (n==0) { v.setLeft(null); return v; } BTNode r, l; r = build((n-1)/2+((n-1)%2),v); // $Τ_r$ το δεξιό υποδένδρο με τα μισά στοιχεία l = build((n-1)/2, (r != null ? r.getRight() : null)); // $Τ_l$ το αριστερό if (r != null) { r.setRight((l != null ? l.getLeft() : l)); r.setParent(l); } if ( l!= null) { if (l.getLeft() != null) l.getLeft().setParent(r); l.setLeft(r); } return l; } // αναδομεί το $T_v$ μεγέθους $n$ private BTNode rebuild(int n, BTNode v){ BTNode aux = new BTNode(null,null,null,null); // βοηθητική μεταβλητή build(n,flatten(v,aux)); // συγκέντρωση κόμβων και αναδρομικό κτίσιμο return aux.getLeft(); } // ένθεση $i$, εάν δεν υπάρχει ήδη public BTNode insertItem(Item i){ BTNode insNode = super.insertItem(i), v, w, p; // ένθεση boolean left; if (insNode == null) return null; if (size() < 3) return insNode; if (getHeight() < getDepth(insNode)){ // παραβίαση ιδανικού ύψους v = findScapegoat(insNode,1); // εντοπισμός εξιλαστήριου κόμβου p = v.getParent(); left = isLeft(v); w = rebuild(getSize(v),v); // αναδόμηση $T_v$ και if (v == root()) // τοποθέτηση πίσω στο δένδρο setRoot(w); else if (left) p.setLeft(w); else p.setRight(w); w.setParent(p); } maxSize = Math.max(size(),maxSize); // ενημέρωση μεγέθους return insNode; } // απόσβεση στοιχείου με κλειδί $key$, εάν υπάρχει public BTNode deleteItem(Object key){ BTNode delNode = super.deleteItem(key); // όπως στα αζύγιστα if (delNode == null) return null; if (size() < a*maxSize) { // αναδόμηση λόγω μεγάλου πλήθους setRoot(rebuild(size(),root())); // διαγραφών maxSize = size(); } return delNode; } // αναζήτηση βάσει κλειδιού $key$, μέσω της κληρονομημένης μεθόδου public Object findInfo(Object key, BTNode v){ return super.findInfo(key,v); } }// Τέλος scapegoatTree //////////////// Κεφάλαιο 22 --- Πιθανοτικές Δομές Ιδιότητας Μέλους ////////////////// /* Φίλτρα Bloom */ public class BloomFilter{ private BitSet BF; // πίνακας private int m; // μέγεθος πίνακα private int n; // αναμενόμενο πλήθος στοιχείων private int k; // πλήθος συναρτήσεων κατακερματισμού private int nofItems; // πλήθος στεγασμένων στοιχείων private hashOperator h; // κλάση κατακερματισμού // $constructor \#1$ public BloomFilter(int size, int nofitems, int nofhashes, hashOperator hashes){ m = size; n = nofitems; k = nofhashes; BF = new BitSet(m); h = hashes; // συναρτήσεις χρήστη nofItems = 0; } // $constructor \#2$ με βέλτιστα $m$, $k$ public BloomFilter(int nofitems, float f){ n = nofitems; m = (int) Math.floor(-n*Math.log(f)/(Math.log(2)*Math.log(2))); k = (int) Math.floor(m*Math.log(2)/n); BF = new BitSet(m); h = new hashOperator(k,m); // τυχαίες συναρτήσεις nofItems = 0; } public boolean CheckMembership(Object x){ // έλεγχος ιδιότητας μέλους for (int i=0; i>> 2) == 0 ? false : true); } void setisOccupied(boolean x){ // θέτει το μπιτ ((Κατειλημμένη)) bits = (x == false ? (byte) (bits & 3) : (byte) (bits | 4)); } boolean isContinuation(){ // επιστρέφει το μπιτ ((Επέκταση)) return ((byte) ((bits & 2) >>> 1) == 0 ? false : true); } void setisContinuation(boolean x){ // θέτει το μπιτ ((Επέκταση)) bits = (x == false ? (byte) (bits & (byte) 5) : (byte) (bits | (byte) 2)); } boolean isShifted(){ // επιστρέφει το μπιτ ((Ολισθημένη)) return ((byte) (bits & 1) == 0 ? false : true); } void setisShifted(boolean x){ // θέτει το μπιτ ((Ολισθημένη)) bits = (x == false ? (byte)(bits & 6) : (byte)(bits | 1)); } int getRemainder(){ // επιστρέφει το υπόλοιπο return remainder; } void setRemainder(int r){ // αναθέτει το υπόλοιπο remainder = r; } }// Τέλος qfEntry /* Φίλτρα Πηλίκου */ public class QuotientFilter{ qfEntry [] QF; // πίνακας κατακερματισμού int p; // μήκος αποτυπωμάτων int r; // μήκος υπολοίπων int m; // μήκος πίνακα int q; // $\log$ μήκους πίνακα int n; // πλήθος στεγασμένων υπογραφών QuotientFilter(int f, int logm){ p = f; q = logm; r = p - q; m = 1 << q; QF = new qfEntry[m]; n = 0; } int getQuotient(int f){ return (int) f >>> r; // $\lfloor f/2^r\rfloor$ } int getRemainder(int f){ return (int) f & ((1 << r) - 1); // $f \mod 2^r$ } // εύρεση της αρχής της συστοιχίας που αντιστοιχεί στην θέση p int findCluster(int p){ int r = p; while (QF[r].isShifted()){ // εύρεση της αρχής της συστοιχίας r--; if (r == -1) r += m; // αναδίπλωση else if (r == p) return -1; // επιστροφή στην αρχική θέση } return r; } int nextRun(int r){ // εύρεση επόμενης σειράς μετά την θέση $r$ int s = r; do { s++; if (s == m) s = 0; // αναδίπλωση else if (s == r) return -1; // επιστροφή στην αρχική θέση } while((QF[s] != null) && (QF[s].isContinuation())); return s; } int nextQuotient(int s){ // εύρεση επόμενου πηλίκου μετά την θέση $s$ int r = s; do { r++; if (r == m) r = 0; // αναδίπλωση else if (r == s) return -1; // επιστροφή στην αρχική θέση } while((QF[r] != null) && (!QF[r].isOccupied())); return r; } int findRun(int cluster, int fq){ // εύρεση της αρχής της σειράς του fq int r, s; s = r = cluster; // αρχή της τρέχουσας σειράς while (r != fq){ s = nextRun(s); // εύρεση αρχής επόμενης σειράς r = nextQuotient(r); // εύρεση αντίστοιχου πηλίκου } return s; } // αναζήτηση της θέσεως του $f_r$ εντός της σειράς int searchRun(int fr, int start){ int s = start; do { if (QF[s].getRemainder() >= fr) // βρέθηκε η θέση return s; s++; if (s == m) s = 0; // αναδίπλωση else if (s == start) return -1; // επιστροφή στην αρχική θέση } while((QF[s] != null) && (QF[s].isContinuation())); return s; // επιστροφή θέσης } int checkMembership(int f){ // έλεγχος ιδιότητας μέλους int fq, fr, s, r; fq = getQuotient(f); fr = getRemainder(f); if ((QF[fq] == null) || (!QF[fq].isOccupied())) // δεν υπάρχει τέτοιο return -1; // πηλίκο στον πίνακα r = findCluster(fq); // αρχή συστοιχίας s = findRun(r,fq); // αρχή της αντίστοιχής σειράς if (QF[searchRun(fr,s)].getRemainder() == fr) // βρέθηκε το υπόλοιπο return s; // επιστροφή της θέσεως return -1; } /* ένθεση στην θέση pos της σειράς που ξεκινά από την θέση s και δεξιά ολίσθηση των άλλων υπολοίπων της συστοιχίας που βρίσκονται στα δεξιά */ boolean shiftRight(int s, int pos, int fr){ int i = pos; qfEntry prev, cur; boolean first; if (s == pos) {// ένθεση στην αρχή της σειράς prev = new qfEntry(QF[pos].isOccupied(),false,QF[pos].isShifted(),fr); first = true; } else { // ένθεση ενδιάμεσα prev = new qfEntry(QF[pos].isOccupied(),true,true,fr); first = false; } cur = QF[i]; QF[i] = prev; prev = cur; if (first){ prev.setisContinuation(true); prev.setisShifted(true); first = false; } i++; while (QF[i] != null) { // μετατόπιση μέχρι να βρούμε κενή θέση cur = QF[i]; QF[i] = prev; QF[i].setisShifted(true); QF[i].setisOccupied(cur.isOccupied()); prev = cur; i++; if (i == m) // αναδίπλωση i = 0; if (i == s) return false; } QF[i] = prev; // τοποθέτηση τελευταίου υπολοίπου στην κενή θέση QF[i].setisShifted(true); QF[i].setisOccupied(false); return true; } // ολίσθηση προς δεξιά υπολοίπων από την θέση s boolean shiftRight(int s, qfEntry x){ int i = s; qfEntry prev = x, cur; while (QF[i] != null) { // όσο δεν συναντάμε κενή θέση cur = QF[i]; // τοποθέτηση προηγούμενου υπολοίπου QF[i] = prev; QF[i].setisShifted(true); QF[i].setisOccupied(cur.isOccupied()); prev = cur; i++; if (i == m) // αναδίπλωση i = 0; if (i == s) return false; } QF[i] = prev; // τοποθέτηση στην κενή θέση QF[i].setisShifted(true); QF[i].setisOccupied(false); return true; } // εισαγωγή νέου αποτυπώματος boolean InsertFingerprint(int f){ int fq, fr, s, r, pos; qfEntry x; boolean occupied; if ((checkMembership(f) != -1) || (n == m)) // υπάρχει ήδη ή ο πίνακας return false; // έχει γεμίσει fq = getQuotient(f); // η αρχική ((κανονική)) θέση fr = getRemainder(f); // το υπόλοιπο n++; // προσαρμογή πλήθους αποτυπωμάτων if (QF[fq] == null){ // αρχική θέση ελεύθερη QF[fq] = new qfEntry(true,false,false,fr); return true; } occupied = QF[fq].isOccupied(); // υπήρχε ή όχι τέτοιο πηλίκο QF[fq].setisOccupied(true); r = findCluster(fq); // αρχή συστοιχίας s = findRun(r,fq); // αρχή της σειράς if (!occupied){ // δεν υπήρχε πριν τέτοιο πηλίκο x = QF[s]; if (x == null){ // κενή θέση QF[s] = new qfEntry(false,false,true,fr); return true; } QF[s] = new qfEntry(x.isOccupied(),false,true,fr); // τοποθέτηση και return shiftRight(s+1,x); // δεξιά ολίσθηση των υπολοίπων στα δεξιά } pos = searchRun(fr,s); // θέση εντός της σειράς που αντιστοιχεί στο $f_q$ return shiftRight(s, pos, fr); // ένθεση εντός σειράς με δεξιά ολίσθηση } // ολίσθηση προς τα αριστερά από την θέση pos boolean shiftLeft(int s, int pos){ int i = s + 1, incr = 0, fq = pos; qfEntry cur = QF[s], next = QF[s+1], curplus; if (!next.isContinuation()){ // νέα σειρά, νέο πηλίκο do{ fq++; } while(!QF[fq].isOccupied()); } // προσαρμογή του μπιτ ((Ολισθημένη)), ανάλογα εάν βρίσκεται ή όχι // στην αρχική θέση QF[s] = new qfEntry(cur.isOccupied(), next.isContinuation(), ((s == fq) ? false : next.isShifted()), next.getRemainder()); if (!cur.isContinuation() && (next.isContinuation())) QF[s].setisContinuation(false); // προσαρμογή μπιτ ((Επέκταση)) while ((QF[i+1] != null) && (QF[i+1].isShifted())){ // εντός συστοιχίας cur = QF[i-1]; curplus = QF[i]; next = QF[i+1]; if (!next.isContinuation()){ // νέα σειρά, νέο πηλίκο do{ fq++; } while(!QF[fq].isOccupied()); } // προσαρμογή του μπιτ ((Ολισθημένη)), ανάλογα εάν βρίσκεται ή όχι // στην αρχική θέση QF[i] = new qfEntry(curplus.isOccupied(),next.isContinuation(),(i == fq ? false : next.isShifted()),next.getRemainder()); i++; if (i == m) // αναδίπλωση i = 0; if (i == s) // επιστροφή στην αρχική θέση return false; } QF[i] = null; κένωση τελευταίας θέσης return true; } // απόσβεση αποτυπώματος boolean DeleteFingerprint(int f){ int s, fq; s = checkMembership(f); // αναζήτηση θέσης if (s == -1) // δεν υπάρχει τέτοιο πηλίκο στον πίνακα return false; n--; // προσαρμογή πλήθους αποτυπωμάτων fq = getQuotient(f); if ((!QF[s].isContinuation()) && (!QF[s+1].isContinuation())){ // είναι το μοναδικό υπόλοιπο, ((κένωση)) κανονικής θέσης QF[fq].setisOccupied(false); } if (!QF[s+1].isShifted()){ // φτάσαμε σε νέα συστοιχία QF[s] = null; return true; } return shiftLeft(s,fq); // πλήρωση κενού με αριστερή ολίσθηση } }// Τέλος QuotientFilter //////////////// Κεφάλαιο 23 --- Δυωνυμικές Ουρές ////////////////// /* Κόμβος δυωνυμικής ουράς */ public class bqNode extends BTNode { // αριστερός δείκτης$\equiv$πρώτος γιος, δεξιός δείκτης$\equiv$δεξιός αδελφός public bqNode(Item i) { // $constructor$ super(i,null,null,null); } public Item getItem(){ // επιστρέφει το στοιχείο return (Item) getElement(); } public void setItem(Item i){ // θέτει το στοιχείο setElement(i); } public Object getKey(){ // επιστρέφει το κλειδί return getItem().getKey(); } public void setKey(Object key){ // θέτει το κλειδί getItem().setKey(key); } } /* Δυωνυμική ουρά */ public class binomialQueue { protected dynamicArray Forest; // το δάσος των δυωνυμικών δένδρων protected int nofItems; // πλήθος στοιχείων protected int minPosition; // θέση ελαχίστου protected bqNode minItemNode; // κόμβος με το ελάχιστο κλειδί protected comparator c; public BinomialQueue(comparator com, int fsize){ // $constructor$ nofItems = minPosition = 0; c = com; Forest = new dynamicArray(fsize); } protected int size(){ // επιστρέφει το πλήθος των στοιχείων return nofItems; } protected int forestLength(){ // επιστρέφει το πλήθος των δένδρων return Forest.size(); } protected bqNode getTree(int j){ // επιστρέφει το $j$-στό δένδρο bqNode t = (bqNode) Forest.get(j); Forest.set(j,null); return t; } // συνένωση των $T_v, T_w$ protected bqNode mergeTrees(bqNode v, bqNode w) { if (v == null) return w; else if (w == null) return v; else if (c.greater(v.getKey(),w.getKey())) { // $w$ νέα ρίζα v.setRight(w.getLeft()); // ο πρώτος γιος του $w$ v.setParent(w); // γίνεται δεξιός αδελφός του $v$ w.setLeft(v); // και ο $v$ πρώτος γιος του $w$ return w; } else { // $v$ νέα ρίζα w.setRight(v.getLeft()); // ο πρώτος γιος του $v$ w.setParent(v); // γίνεται δεξιός αδελφός του $w$ v.setLeft(w); // και ο $w$ πρώτος γιος του $v$ return v; } } public bqNode insert(Item i) { // ένθεση του $i$ bqNode insNode = new bqNode(i), root = insNode; // στοιχειώδες δένδρο int j = 0; if (nofItems == 0) // βάση... Forest.set(0,minItemNode = insNode); else { // συνεχόμενη προσθήκη, εξομοιώνοντας την πρόσθεση στο δυαδικό σύστημα while (true) { if (Forest.get(j) == null) { // κενή θέση Forest.set(j, root); break; } else { // συνένωση των δένδρων, με παραγωγή κρατούμενου root = mergeTrees(root,(bqNode)Forest.get(j)); Forest.set(j, null); // μηδενισμός j++; } } minItemNode = (c.greater(i.getKey(),minItemNode.getKey())? m inItemNode : insNode); // καθορισμός ελαχίστου } nofItems++; // ενημέρωση και εύρεση ελαχίστου κόμβου for (j=0, minPosition = 0; j < Forest.size(); j++, minPosition++) if (Forest.get(j) == minItemNode) break; return insNode; } public Item Min(){ // επιστρέφει το μικρότερο στοιχείο if (nofItems == 0) return null; return minItemNode.getItem(); } public Item removeMin() { // αφαιρεί το μικρότερο στοιχείο if (nofItems == 0) return null; Item minItem = Min(); // το στοιχείο που θα αφαιρεθεί bqNode[] delForest = new bqNode[minPosition]; // βοηθητικός πίνακας bqNode cursor = (bqNode) minItemNode.getLeft(), carry = null; for (int i = minPosition-1; i > -1; i--) { delForest[i] = cursor; // διάσπαση του δένδρου του cursor = (bqNode) cursor.getRight(); // ελαχίστου στα συστατικά του delForest[i].setRight(null); // δένδρα delForest[i].setParent(null); } Forest.set(minPosition,null); // διαγραφή του παλιού ελάχιστου δένδρου cursor = null; // διαδοχική προσθήκη των παραγόμενων δένδρων στην δομή: στις επεξηγήσεις // το Χ+Υ+Ζ αναφέρεται στο δάσος, στο παραγόμενο δάσος και στο κρατούμενο for (int j = 0; j < minPosition; j++) { if ((cursor=(bqNode) Forest.get(j)) == null) { if (carry == null) // $0+1+0$ Forest.set(j,delForest[j]); else // $0+1+1$ carry = mergeTrees(delForest[j],carry); } else { if (carry == null) { // $1+1+0$ carry = mergeTrees(delForest[j],cursor); Forest.set(j,null); } else // $1+1+1$ carry = mergeTrees(carry,delForest[j]); } } if (--nofItems == 0) { // κενή δομή! minItemNode = null; minPosition = -1; } else { // $1+0+1$ Forest.set(minPosition, mergeTrees(carry,(bqNode) Forest.get(minPosition))); for (minPosition = 0; Forest.get(minPosition) == null; minPosition++) ; // πρώτη μη κενή θέση minItemNode = (bqNode) Forest.get(minPosition); // εύρεση ελαχίστου κόμβου for (int j = minPosition+1; j < Forest.size(); j++) if ((cursor= (bqNode)Forest.get(j)) != null) && (c.greater(minItemNode.getKey(),cursor.getKey()))){ minPosition = j; minItemNode = cursor; } } return minItem; } // προαγωγή του $v$ λόγω μείωσης κλειδιού σε $priority$ private bqNode promote(bqNode v, Object priority) { bqNode p; Item pItem, vItem; boolean flag = false; v.setKey(priority); vItem = v.getItem(); if (c.greater(Min().getKey(),priority)) // γίνεται το νέο ελάχιστο flag = true; // προβιβάζουμε το $vItem$ όσο είναι μικρότερο από τον πατέρα while (((p = (bqNode) v.getParent()) != null)&& (c.greater(p.getKey(),priority))) { pItem = p.getItem(); p.setItem(vItem); v.setItem(pItem); v = p; } if (flag){ // ενημέρωση ότι έγινε το νέο ελάχιστο minItemNode = v; // και εύρεση της θέσης του for (minPosition = 0; ((bqNode) Forest.get(minPosition)) != v; ++minPosition) ; } return v; } // υποβιβασμός στοιχείου λόγω αυξήσεως του κλειδιού του σε $priority$ private bqNode demote(bqNode v, Object priority) { Item delItem = delete(v); // διαγραφή, delItem.setKey(priority); // ενημέρωση κλειδιού return insert(delItem); // και εισαγωγή εκ νέου } // διαγραφή του κόμβου $v$ public Item delete(bqNode v){ promote(v,c.min()); // προσωρινή προαγωγή του σε ελάχιστο return removeMin(); // και διαγραφή του } // αλλαγή του κλειδιού του $v$ σε $priority$ public bqNode changePriority(bqNode v, Object priority){ if (c.equal(v.getKey(), priority)) // καμμία αλλαγή return v; else if (c.greater(v.getKey(), priority)) // προαγωγή return promote(v,priority); else return demote(v,priority); // υποβιβασμός } // συνένωση της ουράς με μία άλλη $Q$ public void meldBQ(BinomialQueue Q){ // υπολογισμός μεγέθους int l=((int) (Math.log(Q.size()+size())/Math.log(2.0)))+1; bqNode cursor = null, carry = null, cursorQ = null; // βοηθητικοί δείκτες for (int j = 0; j < l; j++) { // ταυτόχρονη διαπέραση των ουρών // συμβολισμός Χ+Υ+Ζ: δένδρο της τρέχουσας, της $Q$ και το κρατούμενο cursorQ = Q.getTree(j); cursor = (bqNode) Forest.get(j); if (cursorQ == null) { // $X+0+Y$ if (carry == null) ; // $X+0+0$ else { // $X+0+1$ if (cursor==null) // $0+0+1$ Forest.set(j,carry); else { // $1+0+1$ carry = mergeTrees(cursor,carry); Forest.set(j,null); } } } else { // $X+1+Y$ if (carry == null) { // $X+1+0$ if (cursor == null) // $0+1+0$ Forest.set(j,cursorQ); else { // $1+1+0$ carry = mergeTrees(cursor,cursorQ); Forest.set(j,null); } } else // $X+1+1$ carry = mergeTrees(carry,cursorQ); } } bqNode t; for (minPosition = 0; minPosition < l; minPosition++) if ((minItemNode =(bqNode) Forest.get(minPosition))!= null) break; // αριστερότερο, μη κενό δένδρο for (int j = minPosition; j 0; i--) // ταίριασμα ζευγών προς τα δεξιά L.insertLast(link((BTNode) L.removeFirst(),(BTNode) L.removeFirst())); next = link(last,(BTNode) L.removeFirst()); while (L.size() != 0) // διασύνδεση προς τα αριστερά next = link(next,(BTNode) L.removeFirst()); return next; } // διασυνδέει τις ρίζες των $T_v,T_w$ private BTNode link(BTNode v, BTNode w){ if (v == null) return w; else if (w == null) return v; else if (c.less(((Item) v.getElement()).getKey(), ((Item) w.getElement()).getKey())) { // ο $v$ θα γίνει ρίζα BTNode temp = v.getLeft(); // πρώτο παιδί w.setParent(v); if (temp != null) temp.setParent(w); // ενημέρωση παιδιού για την αλλαγή w.setRight(temp); // γίνεται αδελφός με τον $w$ v.setLeft(w); // $w$ πρώτο παιδί του $v$ return v; } else { // o $w$ θα γίνει ρίζα - συμμετρική περίπτωση BTNode temp = w.getLeft(); v.setParent(w); if (temp != null) temp.setParent(v); v.setRight(temp); w.setLeft(v); return w; } } }// Τέλος pairingHeap