1 /* 2 * ctrees.h 3 * 4 * Author: mozman 5 * Copyright (c) 2010-2013 by Manfred Moitzi 6 * License: MIT-License 7 */ 8 9 #ifndef __CTREES_H 10 #define __CTREES_H 11 12 #include <Python.h> 13 14 typedef struct tree_node node_t; 15 16 struct tree_node { 17 node_t *link[2]; 18 PyObject *key; 19 PyObject *value; 20 int xdata; 21 }; 22 23 typedef node_t* nodeptr; 24 25 /* common binary tree functions */ 26 void ct_delete_tree(node_t *root); 27 int ct_compare(PyObject *key1, PyObject *key2); 28 PyObject *ct_get_item(node_t *root, PyObject *key); 29 node_t *ct_find_node(node_t *root, PyObject *key); 30 node_t *ct_succ_node(node_t *root, PyObject *key); 31 node_t *ct_prev_node(node_t *root, PyObject *key); 32 node_t *ct_max_node(node_t *root); 33 node_t *ct_min_node(node_t *root); 34 node_t *ct_floor_node(node_t *root, PyObject *key); 35 node_t *ct_ceiling_node(node_t *root, PyObject *key); 36 int ct_index_of(node_t *root, PyObject *key); 37 node_t *ct_node_at(node_t *root, int index); 38 39 /* unbalanced binary tree */ 40 int ct_bintree_insert(node_t **root, PyObject *key, PyObject *value); 41 int ct_bintree_remove(node_t **root, PyObject *key); 42 43 /* avl-tree functions */ 44 int avl_insert(node_t **root, PyObject *key, PyObject *value); 45 int avl_remove(node_t **root, PyObject *key); 46 47 /* rb-tree functions */ 48 int rb_insert(node_t **root, PyObject *key, PyObject *value); 49 int rb_remove(node_t **root, PyObject *key); 50 51 #endif 52