AVL-Baum mit Iterator durchiterieren

Ich habe mir deinen Code nicht komplett angeschaut, aber dieses Stück ist mit Sicherheit ein Fehler:

std::shared_ptr<AVLTree> thisPtr(this);

Dein Tree ist doch gar nicht dynamisch reserivert, sondern liegt auf dem Stack. Und selbst wenn es dynamisch wäre könntest du nicht so einfach den Besitz einem shared_ptr übergeben. Wenn du unbedingt einen shared_ptr auf this brauchst gibt es std::enable_shared_from_this. Aber hier reicht eigentlich ein normaler Pointer. Iteratoren sind nur so lange gültig wie die Struktur zu der sie gehören, fertig. Macht die STL auch so.

Stimmt, da hast du recht! Einen Speicherbereich implizit zu zerstören, der auf dem Stack liegt, macht einfach keinen Sinn!

Danke, da hätte ich lange gebraucht, um darauf zu kommen!

L. G.

Im übrigen hat dein Code auch noch ein Memory Leak. Du hast mit deinen shared_ptr eine zyklische Abhängigkeit zwischen Parent und Child aufgebaut. Der Parent Pointer kann ein ganz normaler Pointer sein, da das Child ja mindestens so lange lebt wie das Parent. Außerdem gibt es keinen Grund für shared_ptr überall. Du kopierst diese ständig unnötig und hast dadurch Overhead für den Reference Counter. Hier wäre unique_ptr für den Besitz und normale Pointer für das drumherum sinnvoller. Ist aber vermutlich größere Arbeit das umzustellen.

Vor allem funktioniert das Balancing nicht, wenn ich das aktiviere...

Wenn du was aktivierst?

Sorry, dumm ausgedrückt.

Zeile 68:

p = balance(p);

Hatte ich erst mal auskommentiert, um zu sehen, dass das InOrder-Feature ohne Balancing funktioniert. Das tut es. Mit Balancing funktioniert es nicht mehr. Ich hatte versucht beim Balancing die neuen Eltern richtig zu setzen, allerdings stimmt das Ergebnis einfach nicht.

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

int main()
{
    AVLTree<int> tree;

    for (int i = 0; i < 4; ++i) {
        tree.insert(i);
    }

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

    std::cout << std::endl;

    return 0;
}

Liefert:

0,3,1,2,

Hm, schon das Balancing ist kaputt. Ich habe mal das Parent-Feature deaktiviert.

#ifndef AVLTREE_H
#define AVLTREE_H

#include <memory>
#include <algorithm>
#include <assert.h>
#include <iterator>
#include <iostream>

template <typename T>
class AVLTree
{
private:
  class Node
  {
  public:
    int height = 0;
    T value;

    std::shared_ptr<Node> left = nullptr;
    std::shared_ptr<Node> right = nullptr;
    //std::shared_ptr<Node> parent = nullptr;

    Node(T v)
      : value(v)
    {
    }

    // Kleiner-Ordnung
    bool operator<(const T& _value) const { return value < _value; }
  };

  std::shared_ptr<Node> root = nullptr;

  int getHeight(std::shared_ptr<Node> p)
  {
    if (p == nullptr)
      return -1;
    else
      return p->height;
  }

  int getBalance(std::shared_ptr<Node> p)
  {
    if (p == nullptr)
      return 0;
    else
      return getHeight(p->right) - getHeight(p->left);
  }

  std::shared_ptr<Node> insertR(T value, std::shared_ptr<Node> p)
  {
    if (p == nullptr) {
      p = std::make_shared<Node>(value);
    } else if (value < p->value) {
      std::shared_ptr<Node> temp = insertR(value, p->left);
      p->left = temp;
      //temp->parent = p;
    } else if (value > p->value) {
      std::shared_ptr<Node> temp = insertR(value, p->right);
      p->right = temp;
      //temp->parent = p;
    }

    p = balance(p);

    return p;
  }

  std::shared_ptr<Node> balance(std::shared_ptr<Node> p)
  {
    if (p == nullptr)
      return nullptr;

    p->height = std::max(getHeight(p->left), getHeight(p->right)) + 1;

    if (getBalance(p) == -2) {
      if (getBalance(p->left) <= 0)
        p = rotateRight(p);
      else
        p = rotateLeftRight(p);
    } else if (getBalance(p) == 2) {
      if (getBalance(p->right) >= 0)
        p = rotateLeft(p);
      else
        p = rotateRightLeft(p);
    }

    return p;
  }

  std::shared_ptr<Node> rotateRight(std::shared_ptr<Node> p)
  {
    assert(p->left != nullptr);

    std::shared_ptr<Node> q = p->left;
    p->left = q->right;
    q->right = p;

    p->height = std::max(getHeight(p->left), getHeight(p->right)) + 1;
    q->height = std::max(getHeight(q->left), getHeight(q->right)) + 1;

    //q->parent = p->parent;
    //q->right->parent = p;
    //p->parent = q;

    return q;
  }

  void inOrder(std::shared_ptr<Node> p)
  {
      if (p!=nullptr)
      {
          inOrder(p->left);
          std::cout<< p->value <<"\t";
          inOrder(p->right);
      }
  }

  std::shared_ptr<Node> rotateLeft(std::shared_ptr<Node> p)
  {
    assert(p->right != nullptr);

    std::shared_ptr<Node> q = p->right;
    p->right = q->left;
    q->left = p;

    p->height = std::max(getHeight(p->left), getHeight(p->right)) + 1;
    q->height = std::max(getHeight(q->left), getHeight(q->right)) + 1;
/*
    q->parent = p->parent;
    q->left->parent = p;
    p->parent = q;*/

    return q;
  }

  std::shared_ptr<Node> rotateLeftRight(std::shared_ptr<Node> p)
  {
    assert(p->left != nullptr);

    p->left = rotateLeft(p->left);
    return rotateRight(p);
  }

  std::shared_ptr<Node> rotateRightLeft(std::shared_ptr<Node> p)
  {
    assert(p->right != nullptr);

    p->right = rotateRight(p->right);
    return rotateLeft(p);
  }

  bool contains(T value, std::shared_ptr<Node> p)
  {
    if (p == nullptr) {
      return false;
    } else {
      if (value < *p) {
        contains(value, p->left);
      } else {
        if (value > *p) {
          contains(value, p->right);
        } else {
          return true;
        }
      }
    }
  }

  std::shared_ptr<Node> findMax(std::shared_ptr<Node> p)
  {
    if (p == nullptr) {
      return p;
    } else {
      while (p->right != nullptr) {
        p = p->right;
      }
      return p;
    }
  }

  std::shared_ptr<Node> findMin(std::shared_ptr<Node> p)
  {
    if (p == nullptr) {
      return p;
    } else {
      while (p->left != nullptr) {
        p = p->left;
      }
      return p;
    }
  }

  class iterator : std::iterator<std::forward_iterator_tag, T>
  {
    AVLTree* tree;
    std::shared_ptr<Node> node;

  private:
    /*std::shared_ptr<Node> inOrderSuccessor(std::shared_ptr<Node> n)
    {
      // step 1 of the above algorithm
      if (n->right != nullptr)
        return tree->findMin(n->right);

      // step 2 of the above algorithm
      std::shared_ptr<Node> p = n->parent;
      while (p != nullptr && n == p->right) {
        n = p;
        p = p->parent;
      }
      return p;
    }*/

  public:
    explicit iterator()
      : tree(nullptr)
      , node(nullptr)
    {
    }

    explicit iterator(AVLTree* tree)
      : tree(tree)
    {
      node = tree->findMin(tree->root);
    }

    T& operator*() { return node->value; }

    iterator& operator++()
    {
      if (node != nullptr) {
        //node = inOrderSuccessor(node);
      }

      return *this;
    }

    iterator operator++(int)
    {
      iterator tmp = *this;
      ++*this;
      return tmp;
    }

    void printInOrder() {
        tree->inOrder(tree->root);
    }

    bool operator==(const iterator& other) const { return node == other.node; }
    bool operator!=(const iterator& other) const { return node != other.node; }
  };

public:
  iterator begin() { return iterator(this); }
  iterator end() { return iterator(); }

  void insert(T value)
  {
    if (root == nullptr) {
      root = std::make_shared<Node>(value);
    } else {
      insertR(value, root);
    }
  }

  bool contains(T value) { return contains(value, root); }

  T findMax() { findMax(root)->value; }
};

#endif // AVLTREE_H

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

int main()
{
    AVLTree<int> tree;

    for (int i = 0; i < 10; ++i) {
        tree.insert(i);
    }

    tree.begin().printInOrder();

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

    std::cout << std::endl;

    return 0;
}

Gibt hier "0 9" aus.

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.

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.

volkard

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.

Columbo

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.