ASD6

asd6.md

Ćwiczenia 5

z iConem :D

1. Sprawdzamy czy drzewo jest drzewem AVL

   struct Node {
       Node *left, *right;
       int val;
   }
   
   int isAVL(Node *t) {
       if (t==NULL)
           return 0;
           
       int leftH=isAVL(t->left);
       
       if (leftH<0)
           return -1;
           
       int rightH=isAVL(t->right);
       
       if (rightH<0)
           return -1;
       
       if (abs(leftH-rightH)>1)
           return -1;
           
       return 1+max(leftH,rightH);
   }

2. Wstawianie do drzewa BST

   void add(String word, Node* proot) {       
       if(proot == NULL) {
           proot = new Node;
           proot->left = proot->right = NULL;
           proot->val = word;
           proot->count = 1;
       } else if(proot->val == word) {
           proot->count++;
       } else if(proot->val < word) {
           add(word,proot->right);
       } else {
           add(word,proot->left);
       }
       
   }

3. Modyfikacja drzewa BST

   • znalezienie i-tego co do wielkośći elementu w drzewie BST
   • wyznaczenie , który co do wielkości jest dany element

---

• Przechowujemy liczbę wierzchołków dla każdego poddrzewa

• Stwierdzamy, czy szukany indeks jest po lewej, czy prawej stronie

• Dalej to już prosto. :D

  struct Node {
      ...
      int count;
  };
  
  Node * findN(Node * proot, int n) {
      if(!proot) {
          return NULL;
      }
      if(n > proot->count) {
          return NULL;
      }
      if(proot->left) {
          int lcount = proot->left->count;
          if(n == lcount + 1) {
              return proot;
          } else if (n <= lcount ) {
              return findN( proot->left, n );
          } else {
              
          }
      }
  }