3. AVL-Baum mit Iterator durchiterieren

AVL-Baum mit Iterator durchiterieren

  • ?

    Vielen Dank! Du erleichterst mir das Leben!
    Vll. fragst du dich, weshalb ich einen eigenen AVL-Baum mache. Das ist eigentlich nicht zu Übungszwecken gedacht, sondern ich brauche einen AVL-Baum der einen 2D-Range-Search kann. D. h., das soll mal ein 2D-AVL-Baum werden, aber erst mal, muss das für 1D funktionieren. Eigentlich will ich damit geometrische Algorithmen implementieren (das ist die eigentliche Übung), aber erst mal brauche ich diesen doofen Baum. 😛

    Der Code wird OpenSource sein, auch weil du mir geholfen hast.

    Der neueste Stand funktioniert leider nicht mehr, wenn der Baum linkslastig wird. Er gibt dann rekursiv 4,3 aus. Werde wohl weiter brüten.

    #include "avltree.h"
#include <iostream>

int main()
{
    AVLTree<int> tree;

    for (int i = 6; i > 0; --i) {
        tree.insert(i);
    }

    for (int elem : tree) {
        std::cout << elem << ",";
    }

    std::cout << std::endl;

    return 0;
}

    Den neuesten Code findest du hier:

    https://github.com/StefanoD/AVLTree

    L. G.

    0
  • V

    sebi707 schrieb:

    Hab mich gerade 30 min durch deinen Code geschlagen. Der Fehler (oder wenigstens einer) ist in deiner void insert(T value) Funktion. Dort muss es

    root = insertR(value, root);

    heißen, da sich der Wurzelknoten bei einem balance ja auch ändern kann. Mit der kleine Änderung scheint es zu funktionieren.

    👍 👍 👍

    0
  • Mod

    👍

    0
  • ?

    Der Code scheint jetzt zu funktionieren! Die Parents wurden nicht richtig gesetzt.

    Jetzt würde ich den Code ein bisschen auräumen, d. h. von shared_ptr auf unique_ptr umsteigen. Verbesserungsvorschläge sind gerne erwünscht. Wie gesagt: Das ist OpenSource und soll der Allgemeinheit dienen. Im Internet findet man leider kaum AVL-Bäume mit Templates und Iteratoren, geschweigedenn mit Range-Search!

    L. G.

    0
  • ?

    Habe nun auf Raw-Pointer umgestellt, weil der Code mit unique_ptr ganz schön hässlich wurde. Da musste man ein .get() aufrufen, wenn man den unique_ptr an eine Funktion übergeben wollte und man musste einen unique_ptr erstellen und anschließend moven, wenn man eine Zuweisung an einen unique_ptr machen wollte.

    Allerdings sagt valgrind:

    ==10262== 
==10262== HEAP SUMMARY:
==10262==     in use at exit: 91,308 bytes in 7 blocks
==10262==   total heap usage: 1,010 allocs, 1,003 frees, 123,412 bytes allocated
==10262== 
==10262== 4 bytes in 1 blocks are still reachable in loss record 1 of 7
==10262==    at 0x4C2BBCF: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==10262==    by 0x8CE8F22: ??? (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8CE9464: g_private_get (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8CC173C: g_slice_alloc (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8C937ED: g_hash_table_new_full (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8CB470A: ??? (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8C75E58: ??? (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x40105B9: call_init.part.0 (dl-init.c:72)
==10262==    by 0x40106CA: call_init (dl-init.c:30)
==10262==    by 0x40106CA: _dl_init (dl-init.c:120)
==10262==    by 0x4000D09: ??? (in /lib/x86_64-linux-gnu/ld-2.21.so)
==10262== 
==10262== 32 bytes in 1 blocks are still reachable in loss record 2 of 7
==10262==    at 0x4C2DB95: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==10262==    by 0x8CAA5D0: g_malloc0 (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8C93854: g_hash_table_new_full (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8CB470A: ??? (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8C75E58: ??? (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x40105B9: call_init.part.0 (dl-init.c:72)
==10262==    by 0x40106CA: call_init (dl-init.c:30)
==10262==    by 0x40106CA: _dl_init (dl-init.c:120)
==10262==    by 0x4000D09: ??? (in /lib/x86_64-linux-gnu/ld-2.21.so)
==10262== 
==10262== 64 bytes in 1 blocks are still reachable in loss record 3 of 7
==10262==    at 0x4C2DB95: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==10262==    by 0x8CAA5D0: g_malloc0 (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8C9383F: g_hash_table_new_full (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8CB470A: ??? (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8C75E58: ??? (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x40105B9: call_init.part.0 (dl-init.c:72)
==10262==    by 0x40106CA: call_init (dl-init.c:30)
==10262==    by 0x40106CA: _dl_init (dl-init.c:120)
==10262==    by 0x4000D09: ??? (in /lib/x86_64-linux-gnu/ld-2.21.so)
==10262== 
==10262== 88 bytes in 1 blocks are still reachable in loss record 4 of 7
==10262==    at 0x4C2BBCF: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==10262==    by 0x8CAA578: g_malloc (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8CC1762: g_slice_alloc (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8C937ED: g_hash_table_new_full (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8CB470A: ??? (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8C75E58: ??? (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x40105B9: call_init.part.0 (dl-init.c:72)
==10262==    by 0x40106CA: call_init (dl-init.c:30)
==10262==    by 0x40106CA: _dl_init (dl-init.c:120)
==10262==    by 0x4000D09: ??? (in /lib/x86_64-linux-gnu/ld-2.21.so)
==10262== 
==10262== 2,032 bytes in 1 blocks are still reachable in loss record 5 of 7
==10262==    at 0x4C2DB95: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==10262==    by 0x8CAA5D0: g_malloc0 (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8CC19CB: g_slice_alloc (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8C937ED: g_hash_table_new_full (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8CB470A: ??? (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8C75E58: ??? (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x40105B9: call_init.part.0 (dl-init.c:72)
==10262==    by 0x40106CA: call_init (dl-init.c:30)
==10262==    by 0x40106CA: _dl_init (dl-init.c:120)
==10262==    by 0x4000D09: ??? (in /lib/x86_64-linux-gnu/ld-2.21.so)
==10262== 
==10262== 16,384 bytes in 1 blocks are still reachable in loss record 6 of 7
==10262==    at 0x4C2BBCF: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==10262==    by 0x8CAA578: g_malloc (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8CB471B: ??? (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x8C75E58: ??? (in /lib/x86_64-linux-gnu/libglib-2.0.so.0.4600.1)
==10262==    by 0x40105B9: call_init.part.0 (dl-init.c:72)
==10262==    by 0x40106CA: call_init (dl-init.c:30)
==10262==    by 0x40106CA: _dl_init (dl-init.c:120)
==10262==    by 0x4000D09: ??? (in /lib/x86_64-linux-gnu/ld-2.21.so)
==10262== 
==10262== 72,704 bytes in 1 blocks are still reachable in loss record 7 of 7
==10262==    at 0x4C2BBCF: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==10262==    by 0x58261FF: ??? (in /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.21)
==10262==    by 0x40105B9: call_init.part.0 (dl-init.c:72)
==10262==    by 0x40106CA: call_init (dl-init.c:30)
==10262==    by 0x40106CA: _dl_init (dl-init.c:120)
==10262==    by 0x4000D09: ??? (in /lib/x86_64-linux-gnu/ld-2.21.so)
==10262== 
==10262== LEAK SUMMARY:
==10262==    definitely lost: 0 bytes in 0 blocks
==10262==    indirectly lost: 0 bytes in 0 blocks
==10262==      possibly lost: 0 bytes in 0 blocks
==10262==    still reachable: 91,308 bytes in 7 blocks
==10262==         suppressed: 0 bytes in 0 blocks
==10262== 
==10262== For counts of detected and suppressed errors, rerun with: -v
==10262== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

    Also 1,010 allocs und 1,003 frees, heißt es gab Memory-Leaks? So wie es ausschaut jedoch nicht in meinem Code, sondern irgendwo in den System-Libs. Sehe ich das richtig?!

    L. G.

    0
  • ?

    Jemand eine Idee, weshalb ich hier folgenden Fehler kriege?

    .../AVLTree/avltree.h:186: Warnung: control may reach end of non-void function [-Wreturn-type]
  }
  ^

    Ich decke eigentlich alle Fälle ab.

    bool contains(T value, Node* p)
  {
    if (p == nullptr) {
      return false;
    } else if (value < p->value) {
      contains(value, p->left);
    } else if (value > p->value) {
      contains(value, p->right);
    } else {
      return true;
    }
  }
    0
  • C
    Mod

    AVLTree schrieb:

    Ich decke eigentlich alle Fälle ab.

    Stimmt, aber nicht alle diese Fälle enthalten auch ein return.

    0
  • Mod

    Probier' mal

    bool contains(T value, Node* p) 
{ 
    if (p == nullptr)
        return false; 

    if (value < p->value)
        return contains(value, p->left); 

    if (p->value < value)
        return contains(value, p->right); 

    return true; 
}
    0
  • ?

    Ah, verdammt, ich habe zu viel in Scala programmiert! 😞 Das hätte dort wunderbar geklappt! Thx und L. G.!

    0
  • ?

    AVLTree schrieb:

    Ah, verdammt, ich habe zu viel in Scala programmiert! 😞 Das hätte dort wunderbar geklappt! Thx und L. G.!

    Wobei der Fehler war ja nicht das else if oder so sondern, dass du kein return bei deinen Funktionsaufrufen in den beiden mittleren Fällen hattest.

    0
Anmelden zum Antworten