Lines Matching +full:- +full:- +full:root
11 * EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
42 return node->height; in GetAvlTreeHeight()
49 uint32_t leftHeight = GetAvlTreeHeight(node->leftNode); in UpdateAvlTreeHeight()
50 uint32_t rightHeight = GetAvlTreeHeight(node->rightNode); in UpdateAvlTreeHeight()
51 if (node->height >= AVL_MAX_HEIGHT) { in UpdateAvlTreeHeight()
56 node->height = GetMaxHeight(leftHeight, rightHeight) + 1u; in UpdateAvlTreeHeight()
69 curNode->height = 1; in BSL_AVL_MakeLeafNode()
70 curNode->rightNode = NULL; in BSL_AVL_MakeLeafNode()
71 curNode->leftNode = NULL; in BSL_AVL_MakeLeafNode()
72 curNode->data = data; in BSL_AVL_MakeLeafNode()
79 * @param root [IN] Root node to be rotated
80 * @return rNode Root node after rotation
82 static BSL_AvlTree *AVL_RotateLeft(BSL_AvlTree *root) in AVL_RotateLeft() argument
86 5 20 --Rotate Left---> 10 30 in AVL_RotateLeft()
90 In this case, the input root node is 10, and the output node is 20. */ in AVL_RotateLeft()
91 BSL_AvlTree *rNode = root->rightNode; in AVL_RotateLeft()
92 BSL_AvlTree *lNode = rNode->leftNode; in AVL_RotateLeft()
93 root->rightNode = lNode; in AVL_RotateLeft()
94 rNode->leftNode = root; in AVL_RotateLeft()
95 UpdateAvlTreeHeight(root); in AVL_RotateLeft()
102 * @param root [IN] Root node to be rotated
103 * @return lNode Root node after rotation
105 static BSL_AvlTree *AVL_RotateRight(BSL_AvlTree *root) in AVL_RotateRight() argument
110 30 50 --Rotate Right---> 20 40 in AVL_RotateRight()
113 In this case, the input root node is 40, and the output node is 30. */ in AVL_RotateRight()
114 BSL_AvlTree *lNode = root->leftNode; in AVL_RotateRight()
115 BSL_AvlTree *rNode = lNode->rightNode; in AVL_RotateRight()
116 root->leftNode = rNode; in AVL_RotateRight()
117 lNode->rightNode = root; in AVL_RotateRight()
118 UpdateAvlTreeHeight(root); in AVL_RotateRight()
125 * @param root [IN] Root node to be balanced
126 * @return root: root node after balancing
128 static BSL_AvlTree *AVL_RebalanceRight(BSL_AvlTree *root) in AVL_RebalanceRight() argument
131 if ((GetAvlTreeHeight(root->leftNode) + 1u) >= GetAvlTreeHeight(root->rightNode)) { in AVL_RebalanceRight()
132 UpdateAvlTreeHeight(root); in AVL_RebalanceRight()
133 return root; in AVL_RebalanceRight()
136 BSL_AvlTree *curNode = root->rightNode; in AVL_RebalanceRight()
137 if (GetAvlTreeHeight(curNode->leftNode) > GetAvlTreeHeight(curNode->rightNode)) { in AVL_RebalanceRight()
138 root->rightNode = AVL_RotateRight(curNode); in AVL_RebalanceRight()
140 return AVL_RotateLeft(root); in AVL_RebalanceRight()
145 * @param root [IN] Root node to be balanced
146 * @return root: root node after balancing
148 static BSL_AvlTree *AVL_RebalanceLeft(BSL_AvlTree *root) in AVL_RebalanceLeft() argument
151 if ((GetAvlTreeHeight(root->rightNode) + 1u) >= GetAvlTreeHeight(root->leftNode)) { in AVL_RebalanceLeft()
152 UpdateAvlTreeHeight(root); in AVL_RebalanceLeft()
153 return root; in AVL_RebalanceLeft()
156 BSL_AvlTree *curNode = root->leftNode; in AVL_RebalanceLeft()
157 if (GetAvlTreeHeight(curNode->rightNode) > GetAvlTreeHeight(curNode->leftNode)) { in AVL_RebalanceLeft()
158 root->leftNode = AVL_RotateLeft(curNode); in AVL_RebalanceLeft()
160 return AVL_RotateRight(root); in AVL_RebalanceLeft()
170 BSL_AvlTree *BSL_AVL_InsertNode(BSL_AvlTree *root, uint64_t nodeId, BSL_AvlTree *node) in BSL_AVL_InsertNode() argument
172 if (root == NULL) { in BSL_AVL_InsertNode()
173 node->nodeId = nodeId; in BSL_AVL_InsertNode()
177 if (root->nodeId > nodeId) { in BSL_AVL_InsertNode()
178 // If the nodeId is smaller than the root nodeId, insert the left subtree. in BSL_AVL_InsertNode()
179 root->leftNode = BSL_AVL_InsertNode(root->leftNode, nodeId, node); in BSL_AVL_InsertNode()
181 return AVL_RebalanceLeft(root); in BSL_AVL_InsertNode()
182 } else if (root->nodeId < nodeId) { in BSL_AVL_InsertNode()
183 // If the nodeId is greater than the root nodeId, insert the right subtree. in BSL_AVL_InsertNode()
184 root->rightNode = BSL_AVL_InsertNode(root->rightNode, nodeId, node); in BSL_AVL_InsertNode()
186 return AVL_RebalanceRight(root); in BSL_AVL_InsertNode()
195 BSL_AvlTree *BSL_AVL_SearchNode(BSL_AvlTree *root, uint64_t nodeId) in BSL_AVL_SearchNode() argument
197 BSL_AvlTree *curNode = root; in BSL_AVL_SearchNode()
200 if (curNode->nodeId == nodeId) { in BSL_AVL_SearchNode()
202 } else if (curNode->nodeId > nodeId) { in BSL_AVL_SearchNode()
203 // If the nodeId is smaller than the root nodeId, search the left subtree. in BSL_AVL_SearchNode()
204 curNode = curNode->leftNode; in BSL_AVL_SearchNode()
206 // If the nodeId is greater than the root nodeId, search the right subtree. in BSL_AVL_SearchNode()
207 curNode = curNode->rightNode; in BSL_AVL_SearchNode()
219 * @return root Return the deleted root node of the AVL tree.
227 if (rmNodeChild->rightNode == NULL) { in AVL_DeleteNodeWithTwoChilds()
229 BSL_AvlTree *curNode = rmNodeChild->leftNode; in AVL_DeleteNodeWithTwoChilds()
230 removeNode->nodeId = rmNodeChild->nodeId; in AVL_DeleteNodeWithTwoChilds()
231 removeNode->data = rmNodeChild->data; in AVL_DeleteNodeWithTwoChilds()
237 rmNodeChild->rightNode = AVL_DeleteNodeWithTwoChilds(rmNodeChild->rightNode, removeNode); in AVL_DeleteNodeWithTwoChilds()
241 BSL_AvlTree *BSL_AVL_DeleteNode(BSL_AvlTree *root, uint64_t nodeId, BSL_AVL_DATA_FREE_FUNC func) in BSL_AVL_DeleteNode() argument
243 if (root == NULL) { in BSL_AVL_DeleteNode()
244 return root; in BSL_AVL_DeleteNode()
247 if (root->nodeId == nodeId) { in BSL_AVL_DeleteNode()
248 if (root->leftNode == NULL) { in BSL_AVL_DeleteNode()
249 if (root->rightNode == NULL) { in BSL_AVL_DeleteNode()
251 AVL_FreeData(root->data, func); in BSL_AVL_DeleteNode()
252 BSL_SAL_FREE(root); in BSL_AVL_DeleteNode()
256 BSL_AvlTree *curNode = root->rightNode; in BSL_AVL_DeleteNode()
257 AVL_FreeData(root->data, func); in BSL_AVL_DeleteNode()
258 BSL_SAL_FREE(root); in BSL_AVL_DeleteNode()
261 } else if (root->rightNode == NULL) { in BSL_AVL_DeleteNode()
263 BSL_AvlTree *curNode = root->leftNode; in BSL_AVL_DeleteNode()
264 AVL_FreeData(root->data, func); in BSL_AVL_DeleteNode()
265 BSL_SAL_FREE(root); in BSL_AVL_DeleteNode()
269 AVL_FreeData(root->data, func); in BSL_AVL_DeleteNode()
270 root->leftNode = AVL_DeleteNodeWithTwoChilds(root->leftNode, root); in BSL_AVL_DeleteNode()
271 return AVL_RebalanceRight(root); in BSL_AVL_DeleteNode()
275 if (root->nodeId > nodeId) { in BSL_AVL_DeleteNode()
276 root->leftNode = BSL_AVL_DeleteNode(root->leftNode, nodeId, func); in BSL_AVL_DeleteNode()
277 return AVL_RebalanceRight(root); in BSL_AVL_DeleteNode()
279 root->rightNode = BSL_AVL_DeleteNode(root->rightNode, nodeId, func); in BSL_AVL_DeleteNode()
280 return AVL_RebalanceLeft(root); in BSL_AVL_DeleteNode()
284 void BSL_AVL_DeleteTree(BSL_AvlTree *root, BSL_AVL_DATA_FREE_FUNC func) in BSL_AVL_DeleteTree() argument
286 if (root == NULL) { in BSL_AVL_DeleteTree()
290 BSL_AVL_DeleteTree(root->leftNode, func); in BSL_AVL_DeleteTree()
291 BSL_AVL_DeleteTree(root->rightNode, func); in BSL_AVL_DeleteTree()
292 AVL_FreeData(root->data, func); in BSL_AVL_DeleteTree()
293 BSL_SAL_FREE(root); in BSL_AVL_DeleteTree()