From b9659f0ae3b4766cccea4f6f62d883cd61f98620 Mon Sep 17 00:00:00 2001 From: Steve Lee Date: Sun, 10 Dec 2017 22:57:14 +0800 Subject: avl_tree impl --- .../data_structures/chapter_4/avl_tree | Bin 0 -> 13712 bytes .../data_structures/chapter_4/avl_tree.c | 164 +++++++++++++++++++++ .../data_structures/chapter_4/avl_tree.h | 27 ++++ .../data_structures/chapter_4/binary_search_tree | Bin 0 -> 13624 bytes .../data_structures/chapter_4/binary_search_tree.c | 9 +- .../data_structures/chapter_4/binary_search_tree.h | 8 + .../data_structures/chapter_4/print_ascii_tree.c | 3 +- .../data_structures/chapter_4/print_ascii_tree.h | 11 +- 8 files changed, 213 insertions(+), 9 deletions(-) create mode 100755 Computer_Science/data_structures/chapter_4/avl_tree create mode 100644 Computer_Science/data_structures/chapter_4/avl_tree.c create mode 100644 Computer_Science/data_structures/chapter_4/avl_tree.h create mode 100755 Computer_Science/data_structures/chapter_4/binary_search_tree (limited to 'Computer_Science/data_structures/chapter_4') diff --git a/Computer_Science/data_structures/chapter_4/avl_tree b/Computer_Science/data_structures/chapter_4/avl_tree new file mode 100755 index 0000000..1d5d102 Binary files /dev/null and b/Computer_Science/data_structures/chapter_4/avl_tree differ diff --git a/Computer_Science/data_structures/chapter_4/avl_tree.c b/Computer_Science/data_structures/chapter_4/avl_tree.c new file mode 100644 index 0000000..da6ab0d --- /dev/null +++ b/Computer_Science/data_structures/chapter_4/avl_tree.c @@ -0,0 +1,164 @@ +#include +#include +#include + +#include "avl_tree.h" +#include "print_ascii_tree.h" + +AvlTree make_empty(AvlTree t) +{ + if(t != NULL) { + make_empty(t->left); + make_empty(t->right); + free(t); + } + + return NULL; +} + +Position find(elem_t x, AvlTree t) +{ + if(t == NULL) + return NULL; + else if(x == t->elem) + return t; + else if(x > t->elem) + return find(x, t->right); + else if(x < t->elem) + return find(x, t->left); +} + +Position find_min(AvlTree t) +{ + if(t == NULL) + return NULL; + else if(t->left == NULL) + return t; + else + return find_min(t->left); +} + +Position find_max(AvlTree t) +{ + if(t == NULL) + return NULL; + else if(t->right == NULL) + return t; + else + return find_max(t->right); +} + +static int height(Position p) +{ + return p == NULL ? -1 : p->height; +} + +static Position single_rotate_with_left(Position p) +{ + Position p_left; + + p_left = p->left; + p->left = p_left->right; + p_left->right = p; + + /* derectly use ->height may case some problem */ + p->height = MAX(height(p->left), height(p->right)) + 1; + p_left->height = MAX(height(p_left->left), p->height) + 1; + + /* return new Node */ + return p_left; +} + +static Position single_rotate_with_right(Position p) +{ + Position p_right; + + p_right = p->right; + p->right = p_right->left; + p_right->left = p; + + p->height = MAX(height(p->left), height(p->right)) + 1; + p_right->height = MAX(height(p_right->right), p->height) + 1; + + /* return new node */ + return p_right; + +} + +static Position double_rotate_with_left(Position p) +{ + p->left = single_rotate_with_right(p->left); + + return single_rotate_with_left(p); +} + + +static Position double_rotate_with_right(Position p) +{ + + p->right = single_rotate_with_left(p->right); + + return single_rotate_with_right(p); +} + +AvlTree insert(elem_t x, AvlTree t) +{ + if(t == NULL) { + t = malloc(sizeof(struct AvlNode)); + t->elem = x; + t->height = 0; + t->left = t->right = NULL; + } else if(x > t->elem) { + t->right = insert(x, t->right); + /* > 1 or == 2? */ + if(height(t->right) - height(t->left) > 1) { + if(x > t->right->elem) + t = single_rotate_with_right(t); + if(x < t->right->elem) + t = double_rotate_with_right(t); + } + } else if(x < t->elem) { + t->left = insert(x, t->left); + + if(height(t->left) - height(t->right) == 2) { + if(x < t->left->elem) + t = single_rotate_with_left(t); + if(x > t->left->elem) + t = double_rotate_with_left(t); + } + } + + /* else do nothing, but update the height */ + t->height = MAX(height(t->left), height(t->right)) + 1; + + return t; +} + +/* lazy delete ? */ +AvlTree delete(elem_t x, AvlTree t) +{ + +} + +void test() +{ + AvlTree t = NULL; + + t = insert(4, t); + t = insert(3, t); + t = insert(2, t); + t = insert(1, t); + t = insert(8, t); + t = insert(9, t); + + printf("min:%d\n", find_min(t)->elem); + printf("max:%d\n", find_max(t)->elem); + printf("find 2:%d\n", find(2, t)->elem); + print_ascii_tree(t); +} + +int main() +{ + test(); + return 0; +} diff --git a/Computer_Science/data_structures/chapter_4/avl_tree.h b/Computer_Science/data_structures/chapter_4/avl_tree.h new file mode 100644 index 0000000..1be3cd6 --- /dev/null +++ b/Computer_Science/data_structures/chapter_4/avl_tree.h @@ -0,0 +1,27 @@ +#ifndef _AVL_TREE_H +#define _AVL_TREE_H + +struct AvlNode; +typedef struct AvlNode *Position; +typedef struct AvlNode *AvlTree; +typedef int elem_t; + +AvlTree make_empty(AvlTree t); +Position find(elem_t x, AvlTree t); +Position find_min(AvlTree t); +Position find_max(AvlTree t); +AvlTree insert(elem_t x, AvlTree t); +AvlTree delete(elem_t x, AvlTree t); +elem_t retrieve(Position p); + +/* for print node, place impl in header file */ +struct AvlNode +{ + elem_t elem; + AvlTree left; + AvlTree right; + int height; +}; +typedef AvlTree Tree; + +#endif diff --git a/Computer_Science/data_structures/chapter_4/binary_search_tree b/Computer_Science/data_structures/chapter_4/binary_search_tree new file mode 100755 index 0000000..7c74886 Binary files /dev/null and b/Computer_Science/data_structures/chapter_4/binary_search_tree differ diff --git a/Computer_Science/data_structures/chapter_4/binary_search_tree.c b/Computer_Science/data_structures/chapter_4/binary_search_tree.c index fb61e7b..b498d54 100644 --- a/Computer_Science/data_structures/chapter_4/binary_search_tree.c +++ b/Computer_Science/data_structures/chapter_4/binary_search_tree.c @@ -5,13 +5,6 @@ #include "binary_search_tree.h" #include "print_ascii_tree.h" -struct TreeNode -{ - elem_t elem; - SearchTree left; - SearchTree right; -}; - SearchTree make_empty(SearchTree t) { if(t != NULL) { @@ -125,6 +118,8 @@ void test() insert(3, t); insert(2, t); insert(10, t); + insert(12, t); + insert(-1, t); print_tree_pre_order(t); printf("\n"); diff --git a/Computer_Science/data_structures/chapter_4/binary_search_tree.h b/Computer_Science/data_structures/chapter_4/binary_search_tree.h index da128f8..2d9425e 100644 --- a/Computer_Science/data_structures/chapter_4/binary_search_tree.h +++ b/Computer_Science/data_structures/chapter_4/binary_search_tree.h @@ -14,4 +14,12 @@ SearchTree insert(elem_t x, SearchTree t); SearchTree delete(elem_t x, SearchTree t); elem_t retrieve(Position p); +struct TreeNode +{ + elem_t elem; + SearchTree left; + SearchTree right; +}; +typedef SearchTree Tree; + #endif /* _BINARY_SEARCH_TREE_H */ diff --git a/Computer_Science/data_structures/chapter_4/print_ascii_tree.c b/Computer_Science/data_structures/chapter_4/print_ascii_tree.c index f2e9839..7b71d27 100644 --- a/Computer_Science/data_structures/chapter_4/print_ascii_tree.c +++ b/Computer_Science/data_structures/chapter_4/print_ascii_tree.c @@ -2,7 +2,7 @@ #include #include -#include "binary_search_tree.h" +#include "avl_tree.h" #include "print_ascii_tree.h" struct asciinode_struct @@ -256,6 +256,7 @@ void print_ascii_tree(Tree t) asciinode *proot; int xmin, i; if (t == NULL) return; + printf("\n"); proot = build_ascii_tree(t); compute_edge_lengths(proot); for (i=0; iheight && i < MAX_HEIGHT; i++) diff --git a/Computer_Science/data_structures/chapter_4/print_ascii_tree.h b/Computer_Science/data_structures/chapter_4/print_ascii_tree.h index 12eed6a..1ddfa3b 100644 --- a/Computer_Science/data_structures/chapter_4/print_ascii_tree.h +++ b/Computer_Science/data_structures/chapter_4/print_ascii_tree.h @@ -1,12 +1,21 @@ +/* +** !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! +** !!!Code originally from /http://www.openasthra.com/c-tidbits/printing-binary-trees-in-ascii/ +** !!! Just saved it, cause the website is down. +** !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! +** I use it here for learning. +*/ #ifndef _PRINT_ASCII_TREE_H #define _PRINT_ASCII_TREE_H struct asciinode_struct; typedef struct asciinode_struct asciinode; -typedef SearchTree Tree; #define MAX_HEIGHT 1000 + +#ifndef INFINITY #define INFINITY (1 << 20) +#endif int MIN (int X, int Y); int MAX (int X, int Y); -- cgit v1.2.3