Skip to content
Snippets Groups Projects
Select Git revision
  • 1eba891324ac11e5fb8c760c71e810836baf4234
  • devel default
  • master
  • fo
  • jirka/typing
  • fo-base
  • mj/submit-images
  • jk/issue-96
  • jk/issue-196
  • honza/add-contestant
  • honza/mr7
  • honza/mrf
  • honza/mrd
  • honza/mra
  • honza/mr6
  • honza/submit-images
  • honza/kolo-vs-soutez
  • jh-stress-test-wip
  • shorten-schools
19 results

csv.py

Blame
  • tree_successor.h 1.79 KiB
    // A node of the tree
    class Node {
      public:
        int key;
        Node* left;
        Node* right;
        Node* parent;
    
        // Constructor
        Node(int key, Node* parent=nullptr) {
            this->key = key;
            this->parent = parent;
            this->left = nullptr;
            this->right = nullptr;
        }
    };
    
    // Binary tree
    class Tree {
      public:
        // Pointer to root of the tree; nullptr if the tree is empty.
        Node* root = nullptr;
    
        // Insert a key into the tree.
        // If the key is already present, nothing happens.
        void insert(int key) {
            if (!root) {
                root = new Node(key);
                return;
            }
    
            Node* node = root;
            while (node->key != key) {
                if (key < node->key) {
                    if (!node->left)
                        node->left = new Node(key, node);
                    node = node->left;
                } else {
                    if (!node->right)
                        node->right = new Node(key, node);
                    node = node->right;
                }
            }
        }
    
        // Return successor of the given node.
        //
        // The successor of a node is the node with the next higher key.
        // Return nullptr if there is no such node.
        // If the argument is nullptr, return the node with the smallest key.
        Node* successor(Node* node) {
            // TODO: Implement
        }
    
        // Destructor to free all allocated memory.
        ~Tree() {
            Node* node = root;
            while (node) {
                Node* next;
                if (node->left) {
                    next = node->left;
                    node->left = nullptr;
                } else if (node->right) {
                    next = node->right;
                    node->right = nullptr;
                } else {
                    next = node->parent;
                    delete node;
                }
                node = next;
            }
        }
    };