大家好,又见面了,我是全栈君。
新秀nginx源代码分析数据结构篇(四)红黑树ngx_rbtree_t
假设有相等的结点。会直接被覆盖,如上图插入key为2的结点,则当tmp 为2的结点时。p为叶子遍历结束。这样p就会被覆盖为新的值。 6.2 唯一时间类型插入 唯一差别就是推断大小时,採用了两个值相减,避免溢出。 1: typedef ngx_int_t ngx_rbtree_key_int_t; 2: void 3: ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, 4: ngx_rbtree_node_t *sentinel) 5: { 6: ngx_rbtree_node_t **p; 7: 8: for ( ;; ) { 9: 10: /* 11: * Timer values 12: * 1) are spread in small range, usually several minutes, 13: * 2) and overflow each 49 days, if milliseconds are stored in 32 bits. 14: * The comparison takes into account that overflow. 15: */ 16: 17: /* node->key < temp->key */ 18: 19: p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 0) 20: ? &temp->left : &temp->right; 21: 22: if (*p == sentinel) { 23: break; 24: } 25: 26: temp = *p; 27: } 28: 29: *p = node; 30: node->parent = temp; 31: node->left = sentinel; 32: node->right = sentinel; 33: ngx_rbt_red(node); 34: } 7.ngx_rbtree删除ngx_rbtree_delete 也是依照《算法导论》上的步骤,先删除后调整,在《手把手实现红黑树》已介绍,请參考 1: void 2: ngx_rbtree_delete_delete(ngx_thread_volatile ngx_rbtree_t *tree, 3: ngx_rbtree_node_t *node) 4: { 5: ngx_uint_t red; 6: ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w; 7: 8: /* a binary tree delete */ 9: 10: root = (ngx_rbtree_node_t **) &tree->root; 11: sentinel = tree->sentinel; 12: 13: if (node->left == sentinel) { 14: temp = node->right; 15: subst = node; 16: 17: } else if (node->right == sentinel) { 18: temp = node->left; 19: subst = node; 20: 21: } else { 22: subst = ngx_rbtree_min(node->right, sentinel); 23: 24: if (subst->left != sentinel) { 25: temp = subst->left; 26: } else { 27: temp = subst->right; 28: } 29: } 30: 31: if (subst == *root) { 32: *root = temp; 33: ngx_rbt_black(temp); 34: 35: /* DEBUG stuff */ 36: node->left = NULL; 37: node->right = NULL; 38: node->parent = NULL; 39: node->key = 0; 40: 41: return; 42: } 43: 44: red = ngx_rbt_is_red(subst); 45: 46: if (subst == subst->parent->left) { 47: subst->parent->left = temp; 48: 49: } else { 50: subst->parent->right = temp; 51: } 52: 53: if (subst == node) { 54: 55: temp->parent = subst->parent; 56: 57: } else { 58: 59: if (subst->parent == node) { 60: temp->parent = subst; 61: 62: } else { 63: temp->parent = subst->parent; 64: } 65: 66: subst->left = node->left; 67: subst->right = node->right; 68: subst->parent = node->parent; 69: ngx_rbt_copy_color(subst, node); 70: 71: if (node == *root) { 72: *root = subst; 73: 74: } else { 75: if (node == node->parent->left) { 76: node->parent->left = subst; 77: } else { 78: node->parent->right = subst; 79: } 80: } 81: 82: if (subst->left != sentinel) { 83: subst->left->parent = subst; 84: } 85: 86: if (subst->right != sentinel) { 87: subst->right->parent = subst; 88: } 89: } 90: 91: /* DEBUG stuff */ 92: node->left = NULL; 93: node->right = NULL; 94: node->parent = NULL; 95: node->key = 0; 96: 97: if (red) { 98: return; 99: } 100: 101: /* a delete fixup */ 102: 103: while (temp != *root && ngx_rbt_is_black(temp)) { 104: 105: if (temp == temp->parent->left) { 106: w = temp->parent->right; 107: 108: if (ngx_rbt_is_red(w)) { 109: ngx_rbt_black(w); 110: ngx_rbt_red(temp->parent); 111: ngx_rbtree_left_rotate(root, sentinel, temp->parent); 112: w = temp->parent->right; 113: } 114: 115: if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) { 116: ngx_rbt_red(w); 117: temp = temp->parent; 118: 119: } else { 120: if (ngx_rbt_is_black(w->right)) { 121: ngx_rbt_black(w->left); 122: ngx_rbt_red(w); 123: ngx_rbtree_right_rotate(root, sentinel, w); 124: w = temp->parent->right; 125: } 126: 127: ngx_rbt_copy_color(w, temp->parent); 128: ngx_rbt_black(temp->parent); 129: ngx_rbt_black(w->right); 130: ngx_rbtree_left_rotate(root, sentinel, temp->parent); 131: temp = *root; 132: } 133: 134: } else { 135: w = temp->parent->left; 136: 137: if (ngx_rbt_is_red(w)) { 138: ngx_rbt_black(w); 139: ngx_rbt_red(temp->parent); 140: ngx_rbtree_right_rotate(root, sentinel, temp->parent); 141: w = temp->parent->left; 142: } 143: 144: if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) { 145: ngx_rbt_red(w); 146: temp = temp->parent; 147: 148: } else { 149: if (ngx_rbt_is_black(w->left)) { 150: ngx_rbt_black(w->right); 151: ngx_rbt_red(w); 152: ngx_rbtree_left_rotate(root, sentinel, w); 153: w = temp->parent->left; 154: } 155: 156: ngx_rbt_copy_color(w, temp->parent); 157: ngx_rbt_black(temp->parent); 158: ngx_rbt_black(w->left); 159: ngx_rbtree_right_rotate(root, sentinel, temp->parent); 160: temp = *root; 161: } 162: } 163: } 164: 165: ngx_rbt_black(temp); 166: } 8.实战 因为ngx_rbtree_t未牵涉到内存池,所以很easy抽出来使用,例如以下为实现了插入、打印最小值、删除的样例 1: #include <iostream> 2: #include <algorithm> 3: #include <pthread.h> 4: #include <time.h> 5: #include <stdio.h> 6: #include <errno.h> 7: #include <string.h> 8: #include "ngx_queue.h" 9: #include "ngx_rbtree.h" 10: 11: 12: int main() 13: { 14: 15: ngx_rbtree_t tree; 16: ngx_rbtree_node_t sentinel; 17: 18: ngx_rbtree_init(&tree,&sentinel,ngx_rbtree_insert_value); 19: 20: ngx_rbtree_node_t *rbnode = new ngx_rbtree_node_t[100]; 21: for(int i = 99; i >= 0 ;i--) 22: { 23: rbnode[i].key = i; 24: rbnode[i].parent = NULL; 25: rbnode[i].left = NULL; 26: rbnode[i].right = NULL; 27: ngx_rbtree_insert(&tree,&rbnode[i]); 28: } 29: 30: for(int i = 0; i < 100;i++) 31: { 32: ngx_rbtree_node_t *p = ngx_rbtree_min(tree.root,&sentinel); 33: std::cout << p->key << " "; 34: ngx_rbtree_delete(&tree,p); 35: } 36: 37: 38: delete[] rbnode; 39: 40: return 0; 41: } 执行结果:
– Echo Chen:Blog.csdn.net/chen19870707 –
版权声明:本文博客原创文章,博客,未经同意,不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/117353.html原文链接:https://javaforall.cn