Let T be a red black tree with rank r. Write a function to compute the rank of e

Question

Let T be a red black tree with rank r. Write a function to compute the rank of each node in the tree. The time complexity of your function should be linear in the number off nodes in the tree. Show that this is the case

Explanation / Answer

// This is the implemetation of ranked red black tree. Each node already stores its rank. this is linear as the rank is distance from root node and for a node of rank n we need n steps to reach there #include #include // "nodelist" is a circular linked list template class. // Unlike the Standard C++ list class, previously existing classes can be made into linked list nodes. // This offers greater flexibility than STL provides. namespace wstd { template class RrbTree; template class RrbNode { friend class RrbTree; private: RrbNode *parent; RrbNode *link[2]; size_t span; // weight + getSpan(0) + getSpan(1) size_t weight; // must be at least 1 size_t order; // 1 + getOrder(0) + getOrder(1) signed char red; ValueType value; size_t getSpan(int child) const { if(link[child] == NULL) return 0; return link[child]->span; } size_t getOrder(int child) const { if(link[child] == NULL) return 0; return link[child]->order; } void updateSpan() { span = weight + getSpan(0) + getSpan(1); order = 1 + getOrder(0) + getOrder(1); } RrbNode *min() { RrbNode *x = this; while(x->link[0] != NULL) x = x->link[0]; return x; } RrbNode *max() { RrbNode *x = this; while(x->link[1] != NULL) x = x->link[1]; return x; } public: RrbNode() { parent = NULL; link[0] = link[1] = NULL; span = weight = 1; red = 1; // new nodes are red order = 1; } RrbNode *next() { RrbNode *node = this; if(node->link[1] != NULL) return node->link[1]->min(); RrbNode *y = node->parent; while(y != NULL && node == y->link[1]) { node = y; y = y->parent; } return y; } const RrbNode *next() const { const RrbNode *node = (const RrbNode *)(this); if(node->link[1] != NULL) return node->link[1]->min(); RrbNode *y = node->parent; while(y != NULL && node == y->link[1]) { node = y; y = y->parent; } return y; } RrbNode *prev() { RrbNode *node = this; if(node->link[0] != NULL) return node->link[0]->max(); RrbNode *y = node->parent; while(y != NULL && node == y->link[0]) { node = y; y = y->parent; } return y; } const RrbNode *prev() const { const RrbNode *node = (const RrbNode *)(this); if(node->link[0] != NULL) return node->link[0]->max(); RrbNode *y = node->parent; while(y != NULL && node == y->link[0]) { node = y; y = y->parent; } return y; } size_t getWeight() const { return weight; } bool setWeight(size_t value) { if(value == 0) return false; if(value == weight) return true; // Check that we won't overflow. if(value > weight) { RrbNode *node = this; while(node->parent != NULL) node = node->parent; // node is now the root node. size_t delta = value - weight; size_t tmp = node->span + delta; if(tmp span || tmp

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---