source: src/tests/avltree/avl-private.c@ ed3ff0a2

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors deferred_resn demangler enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum with_gc
Last change on this file since ed3ff0a2 was 3dcd347a, checked in by Thierry Delisle <tdelisle@…>, 9 years ago

moved some more tests to new test folder
  • Property mode set to 100644
File size: 3.2 KB
RevLine 
[6e3ae00]1#include "avl.h"
2#include "avl-private.h"
3
4// AVL tree specific (internal) operations:
5// rotateLeft, rotateRight, fix
6//
7// AVL tree enhanced height operation
8//
9// calcBalance is a simple computation of height(R) - height(L)
10
11// an AVL tree's height is easy to compute
12// just follow path with the larger balance
13forall(otype K | Comparable(K), otype V)
14int height(tree(K, V) * t){
15 int helper(tree(K, V) * t, int ht){
16 if (empty(t)){
17 return ht;
18 } else if (t->balance > 0){
19 return helper(t->right, 1+ht);
20 } else {
21 // can traverse either branch to find the height
22 // of an AVL tree whose balance is 0
23 return helper(t->left, 1+ht);
24 }
25 }
26 return helper(t, 0);
27}
28
29forall(otype K | Comparable(K), otype V)
30int calcBalance(tree(K, V) * t){
31 int l = height(t->left);
32 int r = height(t->right);
33 t->balance = r-l;
34 return t->balance;
35}
36
37// re-establish the link between parent and child
38forall(otype K | Comparable(K), otype V)
39void relinkToParent(tree(K, V) * t){
40 tree(K, V) * parent = t->parent; // FIX ME!!
41 if (empty(t->parent)){
42 return;
43 } else if (parent->key < t->key){
44 parent->right = t;
45 } else {
46 parent->left = t;
47 }
48}
49
50// rotate left from t
51forall(otype K | Comparable(K), otype V)
52tree(K, V) * rotateLeft(tree(K, V) * t){
53 tree(K, V) * newRoot = t->right;
54 t->right = newRoot->left;
55 newRoot->left = t;
56
57 // swap parents
58 newRoot->parent = t->parent;
59 t->parent = newRoot;
60 if (t->right != NULL) {
61 tree(K, V) * right = t->right; // FIX ME!!
62 right->parent = t;
63 }
64 // re-establish the link between newRoot and its parent
65 relinkToParent(newRoot);
66 return newRoot;
67}
68
69// rotate right from t
70forall(otype K | Comparable(K), otype V)
71tree(K, V) * rotateRight(tree(K, V) * t){
72 tree(K, V) * newRoot = t->left;
73 t->left = newRoot->right;
74 newRoot->right = t;
75
76 // swap parents
77 newRoot->parent = t->parent;
78 t->parent = newRoot;
79 if (t->left != NULL){
80 tree(K, V) * left = t->left; // FIX ME!!
81 left->parent = t;
82 }
83 // re-establish the link between newRoot and its parent
84 relinkToParent(newRoot);
85 return newRoot;
86}
87
88// balances a node that has balance factor -2 or 2
89forall(otype K | Comparable(K), otype V)
90tree(K, V) * fix(tree(K, V) * t){
91 // ensure that t's balance factor is one of
92 // the appropriate values
93 assert(t->balance == 2 || t->balance == -2);
94
95 if (t->balance == -2){
96 tree(K, V) * left = t->left; // FIX ME!!
97 if (left->balance == 1){
98 t->left = rotateLeft(t->left);
99 }
100 return rotateRight(t);
101 } else if (t->balance == 2){
102 tree(K, V) * right = t->right; // FIX ME!!
103 if (right->balance == -1){
104 t->right = rotateRight(t->right);
105 }
106 return rotateLeft(t);
107 } else {
108 // shouldn't ever get here
109 assert((int)0);
110 return t;
111 }
112}
113
114// attempt to fix the tree, if necessary
115forall(otype K | Comparable(K), otype V)
116tree(K, V) * tryFix(tree(K, V) * t){
117 int b = calcBalance(t);
118
119 if (b == -2 || b == 2){
120 t = fix(t);
121 } else {
122 assert(b == 0 || b == 1 || b == -1);
123 }
124 return t;
125}
126
127// sets parent field of c to be p
128forall(otype K | Comparable(K), otype V)
129void setParent(tree(K, V) * c, tree(K, V) * p){
130 if (! empty(c)){
131 c->parent = p;
132 }
133}
134
Note: See TracBrowser for help on using the repository browser.