Page 184 - ARM 64 Bit Assembly Language

Abstract data types 171

106 wordlistnode* nrt = rt->left;
107 rt->left = nrt->right;
108 nrt->right = rt;
109 rt->height =
110 MAX(wln_height(rt->left),wln_height(rt->right)) + 1;
111 nrt->height =
112 MAX(wln_height(nrt->left),wln_height(nrt->right)) + 1;
113 return nrt;
114 }
115
116 /**********************************************************/
117 /* wln_insert performs a tree insertion, and re-balances */
118 wordlistnode * wln_insert(wordlistnode *root, wordlistnode *node)
119 {
120 int balance;
121 if (root == NULL)
122 /* handle case where tree is empty, or we reached a leaf */
123 root = node;
124 else
125 {
126 /* Recursively search for insertion point, and perform the
127 insertion. */
128 if (strcmp(node->word,root->word) < 0)
129 root->left = wln_insert(root->left, node);
130 else
131 root->right = wln_insert(root->right, node);
132
133 /* As we return from the recursive calls, recalculate the heights
134 and perform rotations as necessary to re-balance the tree */
135 root->height = MAX(wln_height(root->left),
136 wln_height(root->right)) + 1;
137
138 /* Calculate the balance factor */
139 balance = wln_balance(root);
140 if (balance > 1)
141 {
142 /* the tree is deeper on the left than on the right) */
143 if(strcmp(node->word,root->left->word) <= 0)
144 root = wln_rotate_right(root);
145 else
146 {
147 root->left = wln_rotate_left(root->left);
148 root = wln_rotate_right(root);
149 };
150 }
151 else
152 if(balance < -1)
153 {
154 /* the tree is deeper on the right than on the left) */