Untitled
unknown
plain_text
a year ago
9.6 kB
7
Indexable
#pragma once #include <sstream> #include <exception> #include <memory> namespace cs251 { // Custom exception classes class duplicate_key : public std::runtime_error { public: duplicate_key() : std::runtime_error("Duplicate key!") {} }; class nonexistent_key : public std::runtime_error { public: nonexistent_key() : std::runtime_error("Key does not exist!") {} }; class empty_tree : public std::runtime_error { public: empty_tree() : std::runtime_error("Tree is empty!") {} }; template <typename K, typename V> class splay_tree { public: struct splay_tree_node { // Pointer to the left child std::shared_ptr<splay_tree_node> m_left {}; // Pointer to the right child std::shared_ptr<splay_tree_node> m_right {}; // Weak pointer to the parent std::weak_ptr<splay_tree_node> m_parent {}; // The key of this element K m_key {}; // Pointer to the value of this element std::unique_ptr<V> m_value {}; }; // Return a pointer to the root of the tree std::shared_ptr<splay_tree_node> get_root() const; // Default constructor - create an empty splay tree splay_tree(); // Insert the key/value pair into the tree, if the key doesn't already exist // Throw duplicate_key if the key already exists void insert(const K& key, std::unique_ptr<V> value); // Return a const reference to the value associated with the given key // Throw nonexistent_key if the key is not in the splay tree const std::unique_ptr<V>& peek(const K& key); // Remove and return the key-value pair associated with the given key // Throw nonexistent_key if the key is not in the splay tree std::unique_ptr<V> extract(const K& key); // Return the minimum key in the splay tree, and splay the node // Throw empty_tree if the tree is empty K minimum_key(); // Return the maximum key in the splay tree, and splay the node // Throw empty_tree if the tree is empty K maximum_key(); // Return the current number of elements in the splay tree bool empty() const; // Return whether the splay tree is currently empty size_t size() const; private: // Pointer to the root node of the splay tree std::shared_ptr<splay_tree_node> m_root {}; // TODO: Add any additional methods or variables here size_t m_size = 0; void left_rotate(std::shared_ptr<splay_tree_node>& x); void right_rotate(std::shared_ptr<splay_tree_node>& x); }; template <typename K, typename V> std::shared_ptr<typename splay_tree<K,V>::splay_tree_node> splay_tree<K,V>::get_root() const { return m_root; } template <typename K, typename V> splay_tree<K,V>::splay_tree() { // TODO: Remove the following line and add your implementation here. throw std::logic_error("splay_tree::" + std::string(__FUNCTION__) + "() not implemented"); } template <typename K, typename V> void splay_tree<K,V>::insert(const K& key, std::unique_ptr<V> value) { // TODO: Remove the following line and add your implementation here. if (!m_root) { m_root = std::make_shared<splay_tree_node>(); m_root->m_key = key; m_root->m_value = std::move(value); m_size++; return; } std::shared_ptr<splay_tree_node> current = m_root; std::shared_ptr<splay_tree_node> parent; while (current) { parent = current; if (key < current->m_key) current = current->m_left; else if (key > current->m_key) current = current->m_right; else throw duplicate_key(); } current = std::make_shared<splay_tree_node>(); current->m_key = key; current->m_value = std::move(value); current->m_parent = parent; if (key < parent->m_key) parent->m_left = current; else parent->m_right = current; m_size++; // Splay the newly inserted node to the root while (current->m_parent.lock()) { std::shared_ptr<splay_tree_node> parent = current->m_parent.lock(); std::shared_ptr<splay_tree_node> grandparent = parent->m_parent.lock(); if (!grandparent) { // Zig case if (current == parent->m_left) right_rotate(parent); else left_rotate(parent); } else { if (parent == grandparent->m_left) { if (current == parent->m_left) { // Zig-Zig case right_rotate(grandparent); right_rotate(parent); } else { // Zig-Zag case left_rotate(parent); right_rotate(grandparent); } } else { if (current == parent->m_right) { // Zig-Zig case left_rotate(grandparent); left_rotate(parent); } else { // Zig-Zag case right_rotate(parent); left_rotate(grandparent); } } } } m_root = current; } template <typename K, typename V> const std::unique_ptr<V>& splay_tree<K,V>::peek(const K& key) { // TODO: Remove the following line and add your implementation here. std::shared_ptr<splay_tree_node> current = m_root; while (current) { if (key == current->m_key) break; else if (key < current->m_key) current = current->m_left; else current = current->m_right; } if (!current) throw nonexistent_key(); // Splay the found node to the root while (current->m_parent.lock()) { std::shared_ptr<splay_tree_node> parent = current->m_parent.lock(); std::shared_ptr<splay_tree_node> grandparent = parent->m_parent.lock(); if (!grandparent) { // Zig case if (current == parent->m_left) right_rotate(parent); else left_rotate(parent); } else { if (parent == grandparent->m_left) { if (current == parent->m_left) { // Zig-Zig case right_rotate(grandparent); right_rotate(parent); } else { // Zig-Zag case left_rotate(parent); right_rotate(grandparent); } } else { if (current == parent->m_right) { // Zig-Zig case left_rotate(grandparent); left_rotate(parent); } else { // Zig-Zag case right_rotate(parent); left_rotate(grandparent); } } } } m_root = current; return current->m_value; } template <typename K, typename V> std::unique_ptr<V> splay_tree<K,V>::extract(const K& key) { // TODO: Remove the following line and add your implementation here. std::shared_ptr<splay_tree_node> current = m_root; while (current) { if (key == current->m_key) break; else if (key < current->m_key) current = current->m_left; else current = current->m_right; } if (!current) throw nonexistent_key(); // Splay the found node to the root while (current->m_parent.lock()) { std::shared_ptr<splay_tree_node> parent = current->m_parent.lock(); std::shared_ptr<splay_tree_node> grandparent = parent->m_parent.lock(); if (!grandparent) { // Zig case if (current == parent->m_left) right_rotate(parent); else left_rotate(parent); } else { if (parent == grandparent->m_left) { if (current == parent->m_left) { // Zig-Zig case right_rotate(grandparent); right_rotate(parent); } else { // Zig-Zag case left_rotate(parent); right_rotate(grandparent); } } else { if (current == parent->m_right) { // Zig-Zig case left_rotate(grandparent); left_rotate(parent); } else { // Zig-Zag case right_rotate(parent); left_rotate(grandparent); } } } } m_root = current; // Remove the node std::unique_ptr<V> extracted_value = std::move(current->m_value); if (current->m_left) current->m_left->m_parent = current->m_parent; if (current->m_right) current->m_right->m_parent = current->m_parent; if (current->m_parent.lock()) { if (current == current->m_parent.lock()->m_left) current->m_parent.lock()->m_left = nullptr; else current->m_parent.lock()->m_right = nullptr; } m_size--; return extracted_value; } template <typename K, typename V> K splay_tree<K,V>::minimum_key() { // TODO: Remove the following line and add your implementation here. if (empty()) throw empty_tree(); std::shared_ptr<splay_tree_node> current = m_root; while (current->m_left) current = current->m_left; peek(current->m_key); return current->m_key; } template <typename K, typename V> K splay_tree<K,V>::maximum_key() { // TODO: Remove the following line and add your implementation here. if (empty()) throw empty_tree(); std::shared_ptr<splay_tree_node> current = m_root; while (current->m_right) current = current->m_right; peek(current->m_key); return current->m_key; } template <typename K, typename V> bool splay_tree<K,V>::empty() const { // TODO: Remove the following line and add your implementation here. return !m_root; } template <typename K, typename V> size_t splay_tree<K,V>::size() const { // TODO: Remove the following line and add your implementation here. return m_size; } template <typename K, typename V> void splay_tree<K,V>::left_rotate(std::shared_ptr<splay_tree_node>& x) { // TODO: Add your implementation here. td::shared_ptr<splay_tree_node> y = x->m_right; if (!y) return; x->m_right = y->m_left; if (y->m_left) y->m_left->m_parent = x; y->m_parent = x->m_parent; if (!x->m_parent.lock()) m_root = y; else if (x == x->m_parent.lock()->m_left) x->m_parent.lock()->m_left = y; else x->m_parent.lock()->m_right = y; y->m_left = x; x->m_parent = y; } template <typename K, typename V> void splay_tree<K,V>::right_rotate(std::shared_ptr<splay_tree_node>& x) { // TODO: Add your implementation here. std::shared_ptr<splay_tree_node> y = x->m_left; if (!y) return; x->m_left = y->m_right; if (y->m_right) y->m_right->m_parent = x; y->m_parent = x->m_parent; if (!x->m_parent.lock()) m_root = y; else if (x == x->m_parent.lock()->m_right) x->m_parent.lock()->m_right = y; else x->m_parent.lock()->m_left = y; y->m_right = x; x->m_parent = y; } }
Editor is loading...
Leave a Comment