Slovar kot iskalno drevo

Iz MaFiRaWiki

Želimo predstaviti slovar kot uravnoteženo dvojiško drevo. Kot primer uravnoteženega drevesa, ki lahko služi temu nameno je AVL drevo.

Vsebina

AVL drevo

V računalništvu je AVL drevo uravnoteženo drevo, v katerem se višini vsakih dve poddreves razlikujeta za največ 1.

Operacije v AVL drevesu

Operacije v AVL drevesu so v glavnem takšne, kot jih najdemo tudi v ostalih dvojiških drevesih vendar pa jih dopolnimo z AVL rotacijami.

Vstavljanje

Vstavljenje v AVL drevo lahko v prvi fazi naredimo na isti načit, kot bi to naredili z neuravnoteženim drevesom, nato pa ga po potrebi zarotiramo. Če je ravnotežnosti faktor po vstavljenja -1, 0 ali 1, rotacije niso potrebne, saj je drevo še zmeraj v AVL obliki.

Če pa je ravnotežnostni faktro 2 ali -2, potem je drevo neuravnoteženo in roatacije so potrebne.

Vstavljanje v AVL drevo je časovnega reda O(log(n)).

Brisanje

Če je vozlišče list, ga odstranimo. Če ni, ga nadomestimo bodisi z največjim v njgovem levem poddrevesu, bodisi z najmanjšim v desnem poddrevesu in odstranimo vozlišče. Torej ima vozlišče, ki je odstranjeno največ enega sina. Po brisanju moramo preverit pot do korena, potrebna je ponovna naravnava ravnotežnostnega faktorja.

Ko podtane ravnotežnosti faktor -1 ali 1 lahko končamo. Če postane ravnotežnosti faktor 0, moramo nadaljevati, saj se je višina poddrevesa zmanjšala za 1. Če postane ravnotežnostni faktor -2 ali 2, potem je drevo neuravnoteženo in ga moramo zarotirati, da to popravimo.

Čas, ki ga potrebujemo je reda O(h) za iskanje, plus O(h) za rotacije proti korenu. Torej je operacija končana v O(log n) časa.

Iskanje

Iskanje v AVL drevesih poteka popolnoma enako iskanju v neuravnoteženih drevesih, vendar zaradi uravnoteženosti za iskanje porabimo O(log n) časa. Pri iskanju ne potrebujemo nobenega posebnega postopka ai previdnosti, saj iskanje ne spremeni strukture drevesa.


Slovar kot AVL drevo

Slovar lahko predstavimo kot uravnoteženo AVL drevo s tem da namesto števil v drevo vstavljamo besede. Nato jih urejemo po leksikografskem pravilu. Vse operacije: vstavljenje, brisanje, iskanje so identične "navadnemu" AVL drevesu.

Implementacija Slovarja v Javi

Problema se lotimo kot problema standardnega AVL drevesa. Definiramo razred slovar, ki v bistvu predstavlja AVL drevo, le da so njegovi podatki besede, oz. "Stringi". Enako kot pri AVL drevesu definiramo ravnotežnostni faktor, ter levega in desnega sina.

  1.  
  2. public class Slovar {
  3. private java.lang.String podatek;// vrednost vozlišca
  4.  
  5. private int ravnovesje;// ravnovesje
  6.  
  7. private Slovar Levi;// levi sin
  8.  
  9. private Slovar Desni;// desni sin

Skonstruiramo drevo:

  1.  
  2. public Slovar(java.lang.String p) {
  3. this.podatek = p;
  4. this.ravnovesje = 0;
  5. this.Desni = null;
  6. this.Levi = null;
  7. }

Preberemo vrednost danega vozlišča:

  1.  
  2. public java.lang.String preberi() {
  3. return podatek;
  4. }

Sedaj konstruiramo funkcijo za iskanje po drevesu:

  1.  
  2. public Slovar poisci(String beseda) {
  3. if (beseda.equals(podatek)) {
  4. return this;
  5. } else if (beseda.compareTo(podatek) > 0) {
  6. if (Desni() != null) {
  7. return Desni().poisci(beseda);
  8. } else {
  9. return null;
  10. }
  11. } else {
  12. if (Levi() != null) {
  13. return Levi().poisci(beseda);
  14. } else {
  15. return null;
  16. }
  17. }
  18. }

Definiramo še nekaj konstruktorjev, ki jih bomo potrebovali v nadaljevanju:

  1.  
  2. public int ravnovesje() {
  3. return ravnovesje;
  4. }
  5.  
  6. public void nastaviRavnovesje(int r) {
  7. ravnovesje = r;
  8. }
  9.  
  10. public void nastaviPodatek(String p) {
  11. podatek = p;
  12. }
  13.  
  14. public Slovar Levi() {
  15. return Levi;
  16. }
  17.  
  18. public void Levi(Slovar a) {
  19. Levi = a;
  20. }
  21.  
  22. public Slovar Desni() {
  23. return Desni;
  24. }
  25.  
  26. public void Desni(Slovar a) {
  27. Desni = a;
  28. }

Sedaj naredimo funkcijo vstavi, ki pokliče podfunkcijo vstaviD, ki pravilno vstavi podatek & ureja drevo

  1.  
  2.  
  3. public Slovar vstavi(String beseda) {
  4. return this.vstaviD(beseda).d;
  5.  
  6. }

Vstavi podatek in naredi vse potrebne rotacije:

  1.  
  2. public Vrni vstaviD(String beseda) {
  3. Vrni c = new Vrni(this, 0);
  4. Vrni a = new Vrni(this, 0);
  5. if (podatek.compareTo(beseda)>0) {
  6. if (Levi == null) {
  7. Levi = new Slovar(beseda);
  8. ravnovesje = ravnovesje + 1;
  9. if (ravnovesje != 0)
  10. c.r = 1;
  11. } else {
  12. a = Levi.vstaviD(beseda);
  13. Levi = a.d;
  14. ravnovesje = ravnovesje + a.r;
  15. }
  16. } else if (podatek.compareTo(beseda)<0) {
  17. if (Desni == null) {
  18. Desni = new Slovar(beseda);
  19. ravnovesje = ravnovesje - 1;
  20. if (ravnovesje != 0)
  21. c.r = 1;
  22. } else {
  23. a = Desni.vstaviD(beseda);
  24. Desni = a.d;
  25. ravnovesje = ravnovesje - a.r;
  26. }
  27. } else {
  28. return c;
  29. }
  30. if (ravnovesje == 2) {
  31. if (Levi.ravnovesje() == 1) {
  32. c = new Vrni(rotacijaLL(this), 0);
  33. } else if (Levi.ravnovesje() == -1) {
  34. c = new Vrni(rotacijaLD(this), 0);
  35. } else {
  36. // napaka pri vstavljanju ne sme priti do te situacije
  37. }
  38. }
  39. if (ravnovesje == -2) {
  40. if (Desni.ravnovesje() == -1) {
  41. c = new Vrni(rotacijaDD(this), 0);
  42. } else if (Desni.ravnovesje() == 1) {
  43. c = new Vrni(rotacijaDL(this), 0);
  44. } else {
  45. // napaka pri vstavljanju ne sme priti do te situacije
  46. }
  47. }
  48. if (ravnovesje == 0 || a.r == 0) {
  49. return c;
  50. } else {
  51. c.r = 1;
  52. }
  53. return c;
  54.  
  55. }

Konstruiramo ustrezne rotacije (LD, DD, LL, DL))

  1.  
  2. public static Slovar rotacijaDD(Slovar t) {
  3. Slovar a = t;
  4. Slovar b = t.Desni();
  5. Slovar c = b.Levi();
  6. // procedura
  7. a.nastaviRavnovesje(0);
  8. b.nastaviRavnovesje(0);
  9. // menjava
  10. a.Desni(c);
  11. b.Levi(a);
  12. return b;
  13. }
  14.  
  15. public static Slovar rotacijaLL(Slovar t) {
  16. Slovar a = t;
  17. Slovar b = t.Levi();
  18. Slovar c = b.Desni();
  19. // procedura
  20. a.nastaviRavnovesje(0);
  21. b.nastaviRavnovesje(0);
  22. // menjava
  23. a.Levi(c);
  24. b.Desni(a);
  25. return b;
  26. }
  27.  
  28. public static Slovar rotacijaLD(Slovar t) {
  29. Slovar c = t;
  30. Slovar a = t.Levi();
  31. Slovar b = a.Desni();
  32. // procedura
  33. if (b.ravnovesje() == -1) {
  34. a.nastaviRavnovesje(1);
  35. c.nastaviRavnovesje(0);
  36. } else if (b.ravnovesje() == 1) {
  37. a.nastaviRavnovesje(0);
  38. c.nastaviRavnovesje(-1);
  39. } else {
  40. a.nastaviRavnovesje(0);
  41. c.nastaviRavnovesje(0);
  42. }
  43. b.nastaviRavnovesje(0);
  44.  
  45. // menjava
  46. a.Desni(b.Levi());
  47. c.Levi(b.Desni());
  48. b.Desni(c);
  49. b.Levi(a);
  50. return b;
  51. }
  52.  
  53. public static Slovar rotacijaDL(Slovar t) {
  54. Slovar c = t;
  55. Slovar a = t.Desni();
  56. Slovar b = a.Levi();
  57. // procedura
  58. if (b.ravnovesje() == 1) {
  59. a.nastaviRavnovesje(-1);
  60. c.nastaviRavnovesje(0);
  61. } else if (b.ravnovesje() == -1) {
  62. a.nastaviRavnovesje(0);
  63. c.nastaviRavnovesje(1);
  64. } else {
  65. a.nastaviRavnovesje(0);
  66. c.nastaviRavnovesje(0);
  67. }
  68. b.nastaviRavnovesje(0);
  69. // menjava
  70. a.Levi(b.Desni());
  71. c.Desni(b.Levi());
  72. b.Desni(a);
  73. b.Levi(c);
  74. return b;
  75. }
  76.  
  77. public String toString() {
  78.  
  79. String ret = "";
  80. if (Levi != null) {
  81. ret = ret + "(" + Levi + "?";
  82. }
  83.  
  84. ret = ret + podatek + "|" + ravnovesje + "|";
  85.  
  86. if (Desni != null)
  87. ret = ret + "?" + Desni + ")";
  88.  
  89.  
  90. return ret;
  91. }
  92.  

Nareidmo ukaz izbrisi, ki kliče podprogram IzbrisiD, ki pravilno izbriše element

  1.  
  2. public Slovar izbrisi(String b) {
  3. return this.izbrisiD(b).d;
  4. }

IzbrišiD poišče element za izbris, ga nadomesti z listomin izbriše list. Po potrebi naredi rotacije vse do korena.

  1.  
  2. public Vrni izbrisiD(String b) {
  3. Vrni c;
  4. String s = podatek;
  5. String nadomestek;
  6. if (podatek.compareTo(b)==0) {
  7. // našli poskusimo najti nadomestek
  8. Slovar zacasno;
  9. if (Levi != null) {
  10. zacasno = Levi;
  11. while (zacasno.Desni() != null) {
  12. zacasno = zacasno.Desni();
  13. }
  14. } else if (Desni != null) {
  15. zacasno = Desni;
  16. while (zacasno.Desni() != null) {
  17. zacasno = zacasno.Levi();
  18. }
  19. } else {
  20. return new Vrni(null, 1);
  21. }
  22. // pobrišemo nadomesetek
  23. nadomestek = zacasno.preberi();
  24. c = this.izbrisiD(nadomestek);
  25. podatek = nadomestek;
  26. return c;
  27. } else if (b.compareTo(podatek)>0) {
  28. if (Desni == null)
  29. return new Vrni(this, 0);
  30. else {
  31. c = Desni.izbrisiD(b);
  32. }
  33. } else {
  34. if (Levi == null)
  35. return new Vrni(this, 0);
  36. else {
  37. c = Levi.izbrisiD(b);
  38. }
  39. }
  40. if (b.compareTo(s) > 0) {
  41. Desni = c.d;
  42. ravnovesje = ravnovesje + c.r;
  43. } else if (b.compareTo(s) < 0) {
  44. Levi = c.d;
  45. ravnovesje = ravnovesje - c.r;
  46. } else {
  47. // napaka
  48. }
  49. if (ravnovesje == 2) {
  50. if (Levi.ravnovesje() == 1) {
  51. return new Vrni(rotacijaLL(this), 1);
  52. } else if (Levi.ravnovesje() == -1) {
  53. return new Vrni(rotacijaLD(this), 1);
  54. } else {
  55. // posebna rotacija do katere pride samo pri brisanju naredimo
  56. // LL rotacijo s malo drugacnimi indeksi ravnovesja
  57. Slovar ma = this;
  58. Slovar mb = ma.Levi();
  59. Slovar mc = mb.Desni();
  60. // procedura
  61. ma.nastaviRavnovesje(1);
  62. mb.nastaviRavnovesje(-1);
  63. // menjava
  64. ma.Levi(mc);
  65. mb.Desni(ma);
  66. return new Vrni(mb, 0);
  67. }
  68. }
  69. if (ravnovesje == -2) {
  70. if (Desni.ravnovesje() == -1) {
  71. return new Vrni(rotacijaDD(this), 1);
  72. } else if (Desni.ravnovesje() == 1) {
  73. return new Vrni(rotacijaDL(this), 1);
  74. } else {
  75. // posebna rotacija do katere pride samo pri brisanju naredimo
  76. // DD rotacijo s malo drugacnimi indeksi ravnovesja
  77. Slovar ma = this;
  78. Slovar mb = ma.Desni();
  79. Slovar mc = mb.Levi();
  80. // procedura
  81. ma.nastaviRavnovesje(-1);
  82. mb.nastaviRavnovesje(1);
  83. // menjava
  84. ma.Desni(mc);
  85. mb.Levi(ma);
  86. return new Vrni(mb, 0);
  87.  
  88. }
  89. }
  90. if (ravnovesje != 0 || c.r == 0) {
  91. return new Vrni(this, 0);
  92. } else {
  93. return new Vrni(this, 1);
  94. }
  95.  
  96. }
  97.  
  98. }

Ustvarimo pomožni razred, ki hrani 2 spremenljivki: referenco na drevo in indeks, ki ga potrebujemo pri rekurzivnem klicu, da vemo če so rotacije potrebne.

  1.  
  2. class Vrni {
  3. public Slovar d;
  4.  
  5. public int r;
  6.  
  7. public Vrni(Slovar d, int r) {
  8. this.d = d;
  9. this.r = r;
  10. }
  11.  
  12. public String toString() {
  13. return "" + r + "|\r" + d;
  14. }
  15. }
Osebna orodja