ST Using Left-Leaning Red-Black Tree

8MB

BalancedSearchTrees.pdf

pdf

Maps are implemented using Red-Black Trees

#include <iostream>
#include <queue>
using namespace std;

const bool RED = true;
const bool BLACK = false;

template <typename Key, typename Value>
struct Node
{
     Node *left, *right;
     Key key;
     Value val;
     bool color; // color of child to parent link

public:
     Node(Key key, Value val, bool color)
     {
          left = right = nullptr;
          this->color = color;
          this->key = key;
          this->val = val;
     }
};

template <typename Key, typename Value>
class RedBlackTree
{
     Node<Key, Value> *root;


     // Main Operations
     bool isRed(Node<Key, Value> *x)
     {
          return (x == nullptr) ? false : x->color == RED; // null and right side links are always black
     }

     // Orient a (temporarily) right-leaning red link to lean left.
     Node<Key, Value> *rotateLeft(Node<Key, Value> *h)
     {
          Node<Key, Value> *x = h->right;
          h->right = x->left;
          x->left = h;
          x->color = h->color;
          h->color = RED;
          return x;
     }

     // Orient a left-leaning red link to (temporarily) lean right.
     Node<Key, Value> *rotateRight(Node<Key, Value> *h)
     {
          Node<Key, Value> *x = h->left;
          h->left = x->right;
          x->right = h;
          x->color = h->color;
          h->color = RED;
          return x;
     }

     // Recolor to split a (temporary) 4-node.
     void flipColor(Node<Key, Value> *h)
     {
          h->color = RED;
          h->left->color = BLACK;
          h->right->color = BLACK;
     }

     Node<Key, Value> *put(Node<Key, Value> *h, Key key, Value val)
     {
          if (h == nullptr)
               return new Node<Key, Value>(key, val, RED);
          if (h->key > key)
               h->left = put(h->left, key, val);
          else if (h->key < key)
               h->right = put(h->right, key, val);
          else
               h->val = val;

          if (isRed(h->right) && !isRed(h->left))
               h = rotateLeft(h);
          if (isRed(h->left) && isRed(h->left->left))
               h = rotateRight(h);
          if (isRed(h->left) && isRed(h->right))
               flipColor(h);

          return h;
     }

     Node<Key, Value> *floor(Node<Key, Value> *x, Key key)
     {
          if (x == nullptr)
               return nullptr;
          if (key == x->key)
               return x;
          if (key < x->key)
               return floor(x->left, key);

          Node<Key, Value> *temp = floor(x->right, key);
          if (temp != nullptr)
               return temp;
          else
               return x;
     }

     void levelorder(Node<Key, Value> *x)
     {
          queue<Node<Key, Value> *> qt;
          qt.push(root);
          qt.push(nullptr);
          cout << x->key << ": " << x->val << " " << endl;

          while (!qt.empty())
          {
               Node<Key, Value> *cur = qt.front();
               qt.pop();
               if (cur != nullptr)
               {
                    if (cur->left != nullptr)
                    {
                         qt.push(cur->left);
                         cout << cur->left->key << ": " << cur->left->val << " ";
                    }
                    if (cur->right != nullptr)
                    {
                         qt.push(cur->right);
                         cout << cur->right->key << ": " << cur->right->val << " ";
                    }
               }
               if (qt.front() == nullptr)
               {
                    cout << endl;
                    qt.pop();
                    qt.push(nullptr);
               }
          }
     }

     Node<Key, Value> *delMax(Node<Key, Value> *x)
     {
          if (x->right == nullptr)
          {
               Node<Key, Value> *temp = x->left;

               return temp;
          }
          x->right = delMax(x->right);
          return x;
     }

     Node<Key, Value> *delMin(Node<Key, Value> *x)
     {
          if (x->left == nullptr)
          {
               // Node<Key, Value> *temp = x;
               return x->right;
          }
          x->left = delMin(x->left);
          return x;
     }

     Node<Key, Value> *min(Node<Key, Value> *x)
     {
          Node<Key, Value> *temp = x;
          while (temp->left != nullptr)
          {
               temp = temp->left;
          }
          return temp;
     }

     Node<Key, Value> *max(Node<Key, Value> *x)
     {
          Node<Key, Value> *temp = x;
          while (temp->right != nullptr)
          {
               temp = temp->right;
          }
          return temp;
     }

     // Hibbard deletion: Simple BST Deletion
     Node<Key, Value> *delPair(Node<Key, Value> *x, Key key)
     {
          if (x == nullptr)
               return x;
          if (key < x->key)
               x->left = delPair(x->left, key);
          else if (key > x->key)
               x->right = delPair(x->right, key);
          else
          {
               if (x->left == nullptr)
                    return x->right;
               if (x->right == nullptr)
                    return x->left;
               Node<Key, Value> *t = x;
               x = min(t->right);
               x->right = delMin(t->right); // will return t->right
               x->left = t->left;
          }
          return x;
     }

public:
     void put(Key key, Value val)
     {
          root = put(root, key, val);
     }

     Key floor(Key key)
     {
          Node<Key, Value> *x = floor(root, key);
          if (x == nullptr)
               throw "";
          return x->key;
     }

     Value get(Key key)
     {
          Node<Key, Value> *cur = root;
          while (cur != nullptr)
          {
               if (cur->key < key)
               {
                    cur = cur->right;
               }
               else if (cur->key > key)
                    cur = cur->left;
               else
                    return cur->val;
          }
          throw "Key Not found!";
     }

     void print_levelorder()
     {
          levelorder(root);
     }
     Key min()
     {
          if (root == nullptr)
               throw "Empty Symbol Table";
          Node<Key, Value> *temp = min(root);
          return temp->key;
     }
     Key max()
     {
          if (root == nullptr)
               throw "Empty Symbol Table";
          Node<Key, Value> *temp = max(root);
          return temp->key;
     }
     void delMin()
     {
          root = delMin(root);
     }
     void delMax()
     {
          root = delMax(root);
     }
     void delPair(Key key)
     {
          root = delPair(root, key);
     }
};

int main()
{
     RedBlackTree<char, int> *rb = new RedBlackTree<char, int>();
     rb->put('S', 1);
     rb->put('E', 2);
     rb->put('A', 3);
     rb->put('R', 4);
     rb->put('C', 5);
     rb->put('H', 6);
     rb->put('X', 7);
     rb->put('M', 8);
     rb->put('P', 9);
     rb->put('L', 10);

     rb->delPair('L'); // hibbard deletion O(lgn) Black links Not Balanced
     rb->delPair('P');

     rb->put('P', 9);
     cout << rb->floor('N') << endl;
     rb->print_levelorder();
}

Hibbard-Deletion

If you don't use any extra property to maintain the Red-Black Tree properties after performing Hibbard deletion, the tree will effectively degrade into an ordinary Binary Search Tree (BST). In this scenario, the balance of the tree is not maintained, which can lead to the tree becoming unbalanced over time.

Key Points:

1. Finding the Node to Delete:

   • This still takes (O(lg n) time in the best case when the tree is balanced, but could degrade to O(n) in the worst case if the tree becomes unbalanced.

2. Hibbard Deletion:

   • The Hibbard deletion process itself involves finding the in-order predecessor (or successor), which takes O(lg n) time in a balanced tree but O(n) in the worst case for an unbalanced tree. Replacing the node and deleting the predecessor or successor also takes O(lg n ) or O(n) time depending on the balance of the tree.

3. No Maintenance of Red-Black Properties:

   • Since you are not maintaining the Red-Black properties, there is no additional cost for rotations and color changes.

Time Complexity Without Maintaining Red-Black Properties:

Without maintaining the Red-Black properties, the time complexity for deletion will be:

• Best Case (Balanced Tree): O(lo n)

• Worst Case (Unbalanced Tree): O(n)

Conclusion:

• In a balanced tree: The time complexity for deletion will be O(lg n) .

• In an unbalanced tree: The time complexity for deletion can degrade to O(n) .

Therefore, if you don't maintain the Red-Black Tree properties, the worst-case time complexity for deletion can degrade to O(n) due to a potential unbalanced tree structure.

MCQs

Suppose that you left rotate the node containing E in the BST below. Which is the level-order traversal of the resulting red–black BST?

• R E X C M S Y A H P F

• R M X E H S Y C F P A

• R M X E P S Y C H A F

• R C X A E S Y M H P F

Here is a drawing of the resulting red–black BST: