Clasele 11-12 lecția 5 - 30 oct 2015

Arbore binar de căutare

#include <cstdio>
#include <algorithm>

using std::pair;

class BST { // Binary Search Tree
public:
  int value;
  BST* left;
  BST* right;

};

BST* find(BST* node, int value) {
  if (node == NULL || node->value == value) {
    return node;
  } else if (node->value < value) {
    return find(node->right, value);
  } else { // if (value < node->value)
    return find(node->left, value);
  }
}

pair<BST*, BST*> split(BST* node, int value) {
  pair<BST*, BST*> answer;
  if (node == NULL) {
    answer.first = NULL;
    answer.second = NULL;
  } else if (node->value <= value) {
    answer.first = new BST;
    answer.first->value = node->value;
    answer.first->left = node->left;
    pair<BST*, BST*> splitAnswer = split(node->right, value);
    answer.first->right = splitAnswer.first;
    answer.second = splitAnswer.second;
    delete node;
  } else { // value < node->value
    answer.second = new BST;
    answer.second->value = node->value;
    answer.second->right = node->right;
    pair<BST*, BST*> splitAnswer = split(node->left, value);
    answer.first = splitAnswer.first;
    answer.second->left = splitAnswer.second;
    delete node;
  }
  return answer;
}

BST* join(BST* first, BST* second) {
  if (first == NULL) {
    return second;
  } else {
    first->right = join(first->right, second);
    return first;
  }
}

BST* insert(BST* node, int value) {
  pair<BST*, BST*> splitAnswer = split(node, value);
  BST* answer = new BST;
  answer->value = value;
  answer->left = splitAnswer.first;
  answer->right = splitAnswer.second;
  return answer;
}

BST* erase(BST* node, int value) {
  if (node == NULL) {
    return NULL;
  } else if (node->value == value) {
    BST* answer = join(node->left, node->right);
    delete node;
    return answer;
  } else if (node->value < value) {
    node->right = erase(node->right, value);
    return node;
  } else { // if (value < node->value)
    node->left = erase(node->left, value);
    return node;
  }
}

void dump(BST* node, int depth = 0) {
  if (node != NULL) {
    dump(node->left, depth + 1);
    for (int i = 0; i < depth; i++) {
      printf("  ");
    }
    printf("%d\n", node->value);
    dump(node->right, depth + 1);
  }
}

int main(void) {
  BST* arb = NULL;
  arb = insert(arb, 5);
  arb = insert(arb, 3);
  arb = insert(arb, 6);
  arb = insert(arb, 4);
  arb = insert(arb, 9);
  arb = insert(arb, 1);
  arb = insert(arb, 7);
  //dump(arb);
  //printf("\n");
  arb = erase(arb, 7);
  //dump(arb);
  
  return 0;
}

Heap

class Heap {
public:
  int value;
  Heap* left;
  Heap* right;
};

Heap* insert(Heap* node, int value) {
  if (node == NULL) {
    node = new Heap;
    node->value = value;
    node->left = NULL;
    node->right = NULL;
  } else if (node->value < value) {
    int oldValue = node->value;
    node->value = value;
    if (rand() % 2 == 1) {
      node->left = insert(node->left, oldValue);
    } else {
      node->right = insert(node->right, oldValue);
    }
  } else { // if (value <= node->value)
    if (rand() % 2 == 1) {
      node->left = insert(node->left, value);
    } else {
      node->right = insert(node->right, value);
    }
  }
  return node;
}

int top(Heap* node) {
  return node->value;
}

Heap* pop(Heap* node) {
  if (node == NULL) {
    return NULL;
  } else { // if (node != NULL)
    if (node->left == NULL) {
      Heap* answer = node->right;
      delete node;
      return answer;
    } else if (node->right == NULL) {
      Heap* answer = node->left;
      delete node;
      return answer;
    } else if (node->right->value < node->left->value) {
      node->value = node->left->value;
      node->left = pop(node->left);
      return node;
    } else { // if (node->left->value <= node->right->value)
      node->value = node->right->value;
      node->right = pop(node->right);
      return node;
    }
  }
}

void dump(Heap* node, int depth = 0) {
  if (node != NULL) {
    dump(node->left, depth + 1);
    for (int i = 0; i < depth; i++) {
      printf("  ");
    }
    printf("%d\n", node->value);
    dump(node->right, depth + 1);
  }
}

int main() {
  Heap* h = NULL;
  h = insert(h, 5);
  h = insert(h, 3);
  h = insert(h, 6);
  h = insert(h, 4);
  h = insert(h, 9);
  h = insert(h, 1);
  h = insert(h, 7);
  dump(h);
  for (int i = 0; i < 7; i++) {
    printf("%d ", top(h));
    h = pop(h);
  }
  return 0;
}

Temă

Pentru data viitoare veți avea de rezolvat următoarele 2 probleme:

• 1513 - Lemon Tale (Timus);
• 1495 - One-two, One-two 2 (Timus).