Mercurial > hg > ucx / file diff

     1.1 --- a/ucx/avl.c	Sat Jul 15 20:46:18 2017 +0200
     1.2 +++ b/ucx/avl.c	Sat Jul 15 22:36:29 2017 +0200
     1.3 @@ -314,3 +314,43 @@
     1.4  size_t ucx_avl_count(UcxAVLTree *tree) {
     1.5      return ucx_avl_countn(tree->root);
     1.6  }
     1.7 +
     1.8 +UcxAVLNode* ucx_avl_pred(UcxAVLNode* node) {
     1.9 +    if (node->left) {
    1.10 +        UcxAVLNode* n = node->left;
    1.11 +        while (n->right) {
    1.12 +            n = n->right;
    1.13 +        }
    1.14 +        return n;
    1.15 +    } else {
    1.16 +        UcxAVLNode* n = node;
    1.17 +        while (n->parent) {
    1.18 +            if (n->parent->right == n) {
    1.19 +                return n->parent;
    1.20 +            } else {
    1.21 +                n = n->parent;
    1.22 +            }
    1.23 +        }
    1.24 +        return NULL;
    1.25 +    }
    1.26 +}
    1.27 +
    1.28 +UcxAVLNode* ucx_avl_succ(UcxAVLNode* node) {
    1.29 +    if (node->right) {
    1.30 +        UcxAVLNode* n = node->right;
    1.31 +        while (n->left) {
    1.32 +            n = n->left;
    1.33 +        }
    1.34 +        return n;
    1.35 +    } else {
    1.36 +        UcxAVLNode* n = node;
    1.37 +        while (n->parent) {
    1.38 +            if (n->parent->left == n) {
    1.39 +                return n->parent;
    1.40 +            } else {
    1.41 +                n = n->parent;
    1.42 +            }
    1.43 +        }
    1.44 +        return NULL;
    1.45 +    }
    1.46 +}