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

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since db67b11 was 3dcd347a, checked in by Thierry Delisle <tdelisle@…>, 5 years ago

moved some more tests to new test folder

• Property mode set to `100644`
File size: 3.2 KB
Line
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)
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
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
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.