construct a self balanced BStree

Posted on |

leetCode 109 construct a height-balanced Binary Search tree from input array(sorted or not).

a self-balanced BStree, which means the left and right kid of each node have no more than 1 height difference, also named as AVL tree. There are three basic routines in implementation of AVL tree: right tree rotate, left tree rotate, and insert. and each TreeNode requires an additionly height value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
TreeNode*  rightRotate(TreeNode* leaf)
{
	if(leaf==nullptr)
		return leaf;
	
	TreeNode*  root_left =  leaf->left ;
	TreeNode*  left_right = root_left->right ;
	root_left->right = leaf;
	leaf->left = left_right;
	
	return root_left; 
}
TreeNode* leftRotate(TreeNode* leaf)
{
	if(leaf==nullptr)
		return leaf;
	
	TreeNode* root_right = leaf->right; 
	TreeNode* right_left = root_right->left; 
	root_right->left = leaf;
	leaf->right =  right_left;
	
	return root_right;
}
TreeNode* insert(TreeNode* root, int key)
{
	if(root==nullptr)
		return (new TreeNode(key));
	
	if(key > root->val)
		root->right = insert(root->right, key);
	
	else if(key < root->val)
			root->left = insert(root->left, key);
	else
		return root; 
	
	root->height = std::max(height(root->left), height(root->right)) + 1 ; 
	int balance = height_dif(root); 
	if(balance > 1 && key < root->val )  //new key inserted in left sub 
	{
		return rightRotate(root); 
	}
	
	/* keep in mind,    -1 <= last_balance <= 1 
	   only  key < root->val, will it possible that current_balance > 1 */
	if(balance < -1 && key > root->val )
	{	
		return leftRotate(root);
	}
	
	return root; 
}

at the very first coding I natively pass node pointer by reference:

TreeNode* insert(TreeNode* &root, int key)
root->right = insert(root->right, key);

since assigned insert() back to the same node pointer again, if passing by reference, each insert will clear the memory-write the same memory all the time, and can’t generate. what actually happen in insert is creating a new object.

the structure pointer inside structure definition is the trick here. when define root node, both leftand right nodes are nullptr, so argument root->right is nullptr, but the returning root->right is actually pointing to a node structure memory.

also nullptr can’t be dereferring, basically since nullptr doesn’t point to any meaningful object, to dereference a null pointer will cause runtime or immediate crash.