wavlTree.h (2816B)
1 #pragma once 2 3 #include "libsheepyObject.h" 4 #undef put 5 6 /** 7 * WAVL Tree 8 * 9 * The WAVL tree combines elements of AVL & Red-black trees. 10 * 11 * The WAVL tree deletion is described in the 2015 paper "Rank Balanced Trees" 12 * The related RAVL tree is described in the 2016 paper "Deletion Without Rebalancing in Binary Search Trees" 13 * available at: 14 * http://sidsen.azurewebsites.net/papers/rb-trees-talg.pdf 15 * http://sidsen.azurewebsites.net/papers/ravl-trees-journal.pdf 16 * 17 * 18 * in this implementation: 19 * - key is int 20 * - value is int 21 * 22 * the code is inspired by: 23 * https://github.com/dmcmanam/bbst-showdown 24 */ 25 26 // namespace 27 #ifndef WAVL_NAMESPACE 28 #define WAVL_NAMESPACE wavlTree 29 #endif 30 #define keyt TOKENPASTE(WAVL_NAMESPACE, keyt) 31 #define valuet TOKENPASTE(WAVL_NAMESPACE, valuet) 32 #define nodet TOKENPASTE(WAVL_NAMESPACE, nodet) 33 #define t TOKENPASTE(WAVL_NAMESPACE, t) 34 #define St TOKENPASTE(WAVL_NAMESPACE, St) 35 #define init TOKENPASTE(WAVL_NAMESPACE, init) 36 37 typedef int keyt; 38 typedef int valuet; 39 //typedef char* valuet; 40 41 typedef struct St t; 42 43 44 45 typedef struct nodet nodet; 46 struct nodet { 47 keyt key; 48 valuet value; 49 nodet *left; 50 nodet *right; 51 nodet *parent; 52 int8_t rank; 53 }; 54 55 typedef int (*heightFt) (t *tree); 56 typedef valuet (*getFt) (t *tree, keyt k); 57 typedef valuet (*putFt) (t *tree, keyt k, valuet v); 58 typedef valuet (*removeKVFt) (t *tree, keyt k); 59 typedef void (*inOrderTraversalFt)(nodet *X); 60 typedef void (*clearFt) (t *tree); 61 typedef nodet* (*getFirstEntryFt) (t *tree); 62 typedef nodet* (*getLastEntryFt) (t *tree); 63 typedef void (*iterStartFt) (t *tree, nodet *first); 64 typedef bool (*hasNextFt) (t *tree); 65 typedef nodet* (*nextEntryFt) (t *tree); 66 typedef nodet* (*prevEntryFt) (t *tree); 67 typedef bool (*removeCurrentFt) (t *tree); 68 69 struct St { 70 size_t count; // number of entries in the tree 71 size_t modCount; // number of structural modifications to the tree 72 size_t rotations; 73 bool deleteWAVL; 74 nodet *root; 75 76 // private iterator 77 size_t expectedModCount; 78 nodet *next; 79 nodet *lastReturned; 80 // end private iterator 81 82 getFt get; 83 putFt put; 84 heightFt treeHeight; 85 removeKVFt remove; 86 inOrderTraversalFt inOrderTraversal; 87 clearFt clear; 88 getFirstEntryFt getFirstEntry; 89 getLastEntryFt getLastEntry; 90 iterStartFt iterStart; 91 hasNextFt hasNext; 92 nextEntryFt nextEntry; 93 prevEntryFt prevEntry; 94 removeCurrentFt removeCurrent; 95 }; 96 97 bool init(t *tree); 98 99 // vim: set expandtab ts=2 sw=2: