AVL-Baum mit Iterator durchiterieren

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.

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.

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;
    }
  }

camper

AVLTree schrieb:

Ich decke eigentlich alle Fälle ab.

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

Columbo

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; 
}

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

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.