[CTDL] Tìm node có giá trị nhỏ nhất trong Binary Search Tree

Find the node with minimum value in a Binary Search Tree

Bởi

21 Tháng Mười, 2020

1223

🔥CHỌN LỌC TOP NHỮNG KHOÁ HỌC LẬP TRÌNH ONLINE NHIỀU NGƯỜI THEO HOC TẠI ĐÂY🔥

Chào ace, bài này chúng ta sẽ tìm hiểu về Tìm node có giá trị nhỏ nhất trong Binary Search Tree, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ…) về nó thông qua các phần sau.

Điều này tương đối đơn giản, chúng ta chỉ cần duyệt đệ quy từ node root sang trái cho đến khi không còn node con bên trái nào nữa. Node cuối cùng duyệt tới được mà có node con bên trái của nó là NULL, thì node cuối cùng duyệt tới được này chính là node chứa giá trị nhỏ nhất của cây BST.

Xét ví dụ cây BST như hình trên, chúng ta sẽ bắt đầu duyệt từ node root 20, sau đó di chuyển sang trái để duyệt tới node 8, tiếp tục di chuyển sang trái cho đến khi chúng ta thấy NULL. Bởi vì node con bên trái của node 4 là NULL, nên node chứa giá trị 4 chính là node có giá trị nhỏ nhất. Dưới đây là các đoạn code ví dụ cài đặt thao tác tìm node có giá trị nhỏ nhất trong cây BST, được thực hiện bằng nhiều ngôn ngữ lập trình khác nhau:

Sử dụng C++:

//C++ program to find minimum value node in binary search Tree. 
#include <bits/stdc++.h> 
using namespace std; 

/* A binary tree node has data, pointer to left child 
and a pointer to right child */
struct node 
{ 
	int data; 
	struct node* left; 
	struct node* right; 
}; 

/* Helper function that allocates a new node 
with the given data and NULL left and right 
pointers. */
struct node* newNode(int data) 
{ 
struct node* node = (struct node*) 
					malloc(sizeof(struct node)); 
node->data = data; 
node->left = NULL; 
node->right = NULL; 

return(node); 
} 

/* Give a binary search tree and a number, 
inserts a new node with the given number in 
the correct place in the tree. Returns the new 
root pointer which the caller should then use 
(the standard trick to avoid using reference 
parameters). */
struct node* insert(struct node* node, int data) 
{ 
/* 1. If the tree is empty, return a new, 
	single node */
if (node == NULL) 
	return(newNode(data)); 
else
{ 
	/* 2. Otherwise, recur down the tree */
	if (data <= node->data) 
		node->left = insert(node->left, data); 
	else
		node->right = insert(node->right, data); 

	/* return the (unchanged) node pointer */
	return node; 
} 
} 

/* Given a non-empty binary search tree, 
return the minimum data value found in that 
tree. Note that the entire tree does not need 
to be searched. */
int minValue(struct node* node) 
{ 
struct node* current = node; 

/* loop down to find the leftmost leaf */
while (current->left != NULL) 
{ 
	current = current->left; 
} 
return(current->data); 
} 

/* Driver Code*/
int main() 
{ 
struct node* root = NULL; 
root = insert(root, 4); 
insert(root, 2); 
insert(root, 1); 
insert(root, 3); 
insert(root, 6); 
insert(root, 5); 

cout << "\n Minimum value in BST is " << minValue(root); 
getchar(); 
return 0; 
}

Sử dụng C:

#include <stdio.h> 
#include<stdlib.h> 

/* A binary tree node has data, pointer to left child 
and a pointer to right child */
struct node 
{ 
	int data; 
	struct node* left; 
	struct node* right; 
}; 

/* Helper function that allocates a new node 
with the given data and NULL left and right 
pointers. */
struct node* newNode(int data) 
{ 
struct node* node = (struct node*) 
					malloc(sizeof(struct node)); 
node->data = data; 
node->left = NULL; 
node->right = NULL; 
	
return(node); 
} 

/* Give a binary search tree and a number, 
inserts a new node with the given number in 
the correct place in the tree. Returns the new 
root pointer which the caller should then use 
(the standard trick to avoid using reference 
parameters). */
struct node* insert(struct node* node, int data) 
{ 
/* 1. If the tree is empty, return a new,	 
	single node */
if (node == NULL) 
	return(newNode(data)); 
else
{ 
	/* 2. Otherwise, recur down the tree */
	if (data <= node->data) 
		node->left = insert(node->left, data); 
	else
		node->right = insert(node->right, data); 
	
	/* return the (unchanged) node pointer */
	return node; 
} 
} 

/* Given a non-empty binary search tree, 
return the minimum data value found in that 
tree. Note that the entire tree does not need 
to be searched. */
int minValue(struct node* node) { 
struct node* current = node; 

/* loop down to find the leftmost leaf */
while (current->left != NULL) { 
	current = current->left; 
} 
return(current->data); 
} 

/* Driver program to test sameTree function*/	
int main() 
{ 
struct node* root = NULL; 
root = insert(root, 4); 
insert(root, 2); 
insert(root, 1); 
insert(root, 3); 
insert(root, 6); 
insert(root, 5); 

printf("\n Minimum value in BST is %d", minValue(root)); 
getchar(); 
return 0;	 
}

Sử dụng Java:

// Java program to find minimum value node in Binary Search Tree 

// A binary tree node 
class Node { 

	int data; 
	Node left, right; 

	Node(int d) { 
		data = d; 
		left = right = null; 
	} 
} 

class BinaryTree { 

	static Node head; 
	
	/* Given a binary search tree and a number, 
	inserts a new node with the given number in 
	the correct place in the tree. Returns the new 
	root pointer which the caller should then use 
	(the standard trick to avoid using reference 
	parameters). */
	Node insert(Node node, int data) { 
		
		/* 1. If the tree is empty, return a new,	 
		single node */
		if (node == null) { 
			return (new Node(data)); 
		} else { 
			
			/* 2. Otherwise, recur down the tree */
			if (data <= node.data) { 
				node.left = insert(node.left, data); 
			} else { 
				node.right = insert(node.right, data); 
			} 

			/* return the (unchanged) node pointer */
			return node; 
		} 
	} 

	/* Given a non-empty binary search tree, 
	return the minimum data value found in that 
	tree. Note that the entire tree does not need 
	to be searched. */
	int minvalue(Node node) { 
		Node current = node; 

		/* loop down to find the leftmost leaf */
		while (current.left != null) { 
			current = current.left; 
		} 
		return (current.data); 
	} 
	
	// Driver program to test above functions 
	public static void main(String[] args) { 
		BinaryTree tree = new BinaryTree(); 
		Node root = null; 
		root = tree.insert(root, 4); 
		tree.insert(root, 2); 
		tree.insert(root, 1); 
		tree.insert(root, 3); 
		tree.insert(root, 6); 
		tree.insert(root, 5); 

		System.out.println("Minimum value of BST is " + tree.minvalue(root)); 
	} 
}

Sử dụng Python:

# Python program to find the node with minimum value in bst 

# A binary tree node 
class Node: 

	# Constructor to create a new node 
	def __init__(self, key): 
		self.data = key 
		self.left = None
		self.right = None

""" Give a binary search tree and a number, 
inserts a new node with the given number in 
the correct place in the tree. Returns the new 
root pointer which the caller should then use 
(the standard trick to avoid using reference 
parameters). """
def insert(node, data): 

	# 1. If the tree is empty, return a new, 
	# single node 
	if node is None: 
		return (Node(data)) 

	else: 
		# 2. Otherwise, recur down the tree 
		if data <= node.data: 
			node.left = insert(node.left, data) 
		else: 
			node.right = insert(node.right, data) 

		# Return the (unchanged) node pointer 
		return node 

""" Given a non-empty binary search tree, 
return the minimum data value found in that 
tree. Note that the entire tree does not need 
to be searched. """
def minValue(node): 
	current = node 

	# loop down to find the lefmost leaf 
	while(current.left is not None): 
		current = current.left 

	return current.data 

# Driver program 
root = None
root = insert(root,4) 
insert(root,2) 
insert(root,1) 
insert(root,3) 
insert(root,6) 
insert(root,5) 

print "\nMinimum value in BST is %d" %(minValue(root))

Sử dụng C#:

using System; 

// C# program to find minimum value node in Binary Search Tree 

// A binary tree node 
public class Node 
{ 

	public int data; 
	public Node left, right; 

	public Node(int d) 
	{ 
		data = d; 
		left = right = null; 
	} 
} 

public class BinaryTree 
{ 

	public static Node head; 

	/* Given a binary search tree and a number, 
	inserts a new node with the given number in 
	the correct place in the tree. Returns the new 
	root pointer which the caller should then use 
	(the standard trick to avoid using reference 
	parameters). */
	public virtual Node insert(Node node, int data) 
	{ 

		/* 1. If the tree is empty, return a new,	 
		single node */
		if (node == null) 
		{ 
			return (new Node(data)); 
		} 
		else
		{ 

			/* 2. Otherwise, recur down the tree */
			if (data <= node.data) 
			{ 
				node.left = insert(node.left, data); 
			} 
			else
			{ 
				node.right = insert(node.right, data); 
			} 

			/* return the (unchanged) node pointer */
			return node; 
		} 
	} 

	/* Given a non-empty binary search tree, 
	return the minimum data value found in that 
	tree. Note that the entire tree does not need 
	to be searched. */
	public virtual int minvalue(Node node) 
	{ 
		Node current = node; 

		/* loop down to find the leftmost leaf */
		while (current.left != null) 
		{ 
			current = current.left; 
		} 
		return (current.data); 
	} 

	// Driver program to test above functions 
	public static void Main(string[] args) 
	{ 
		BinaryTree tree = new BinaryTree(); 
		Node root = null; 
		root = tree.insert(root, 4); 
		tree.insert(root, 2); 
		tree.insert(root, 1); 
		tree.insert(root, 3); 
		tree.insert(root, 6); 
		tree.insert(root, 5); 

		Console.WriteLine("Minimum value of BST is " + tree.minvalue(root)); 
	} 
}

Sử dụng PHP:

<?php 
// PHP program to find the node with 
// minimum value in bst 

// create a binary tree 
class node 
{ 
	private $node, $left, $right; 
	function __construct($node) 
	{ 
		$this->node = $node; 
		$left = $right = NULL; 
	} 

	// set the left node in tree 
	function set_left($left) 
	{ 
		$this->left = $left; 
	} 

	// set the right node in tree 
	function set_right($right) 
	{ 
		$this->right = $right; 
	} 

	// get left node 
	function get_left() 
	{ 
		return $this->left; 
	} 

	// get right node 
	function get_right() 
	{ 
		return $this->right; 
	} 

	// get value of current node 
	function get_node() 
	{ 
		return $this->node; 
	} 
	
} 

// Find the node with minimum value 
// in a Binary Search Tree 
function get_minimum_value($node) 
{ 
	/*travel till last left node to 
	get the minimum value*/
	while ($node->get_left() != NULL) 
	{ 
		$node = $node->get_left(); 
	} 
	return $node->get_node(); 
} 

// code to creating a tree 
$node = new node(4); 
$lnode = new node(2); 
$lnode->set_left(new node(1)); 
$lnode->set_right(new node(3)); 
$rnode = new node(6); 
$rnode->set_left(new node(5)); 
$node->set_left($lnode); 
$node->set_right($rnode); 

$minimum_value = get_minimum_value($node); 
echo 'Minimum value of BST is '. 
				$minimum_value; 
?>

Kết quả in ra là:

Minimum value in BST is 1

Độ phức tạp về thời gian: Chúng ta sẽ gặp phải trường hợp xấu nhất khi làm việc trên các cây lệch trái – left skewed trees, lúc đó độ phức tạp về thời gian sẽ là O(n).

Tương tự, chúng ta có thể tìm được giá trị lớn nhất của cây BST bằng cách duyệt đệ quy từ node root cho tới toàn bộ các node con nằm ở phía bên phải của cây BST.

Nguồn và Tài liệu tiếng anh tham khảo:

Tài liệu từ cafedev:

Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:

Chào thân ái và quyết thắng!

[CTDL] Tìm node có giá trị nhỏ nhất trong Binary Search Tree

Đăng ký kênh youtube để ủng hộ Cafedev nha các bạn, Thanks you!

BÀI VIẾT TIÊU BIỂU

Học JavaScript từ cơ bản đến nâng cao | Hiểu về...

Học JavaScript từ cơ bản đến nâng cao | Chi sẻ...

Học JavaScript từ cơ bản đến nâng cao | Top các...

BÀI VIẾT PHỔ BIẾN

Tổng hợp toàn bộ tài liệu học hướng đối tượng và...

[Tự học C++] Số dấu phẩy động(float, double,…) trong C++

Tổng hợp và chọn lọc bài tập SQL full hướng dẫn...

MỤC XEM NHIỀU