Πώς λειτουργεί η αναζήτηση στο δέντρο;

Η αναζήτηση σε ένα δέντρο εξαρτάται από τη δομή του και τον σκοπό της αναζήτησης.

Βασικοί τρόποι αναζήτησης:

Αναζήτηση βάθους (DFS - Depth-First Search): Πηγαίνει όσο το δυνατόν πιο βαθιά σε ένα κλάδο προτού μεταβεί σε γειτονικό. Υλοποιείται με χρήση στοίβας (ρητά ή μέσω αναδρομής).
- Προκαταρκτική επίσκεψη (Pre-order): Επισκέπτεται τη ρίζα, μετά το αριστερό υποδέντρο, μετά το δεξί υποδέντρο.
- Ενδιάμεση επίσκεψη (In-order): Επισκέπτεται το αριστερό υποδέντρο, μετά τη ρίζα, μετά το δεξί υποδέντρο. Χρησιμοποιείται σε δυαδικά δέντρα αναζήτησης για την απόκτηση ταξινομημένης λίστας στοιχείων.
- Μετα-διάσχιση (Post-order): Επισκέπτεται το αριστερό υποδέντρο, μετά το δεξί υποδέντρο, μετά τη ρίζα.
Αναζήτηση πλάτους (BFS - Breadth-First Search): Εξετάζει όλους τους γείτονες σε ένα επίπεδο προτού προχωρήσει στο επόμενο επίπεδο. Υλοποιείται με χρήση ουράς.

Παράδειγμα DFS (In-order) για δυαδικό δέντρο:

// TreeNode αντιπροσωπεύει τον κόμβο ενός δυαδικού δέντρου
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// InOrderTraversal εκτελεί διάσχιση σε in-order
func InOrderTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Αναδρομική κλήση για το αριστερό υποδέντρο
	result = append(result, InOrderTraversal(root.Left)...)
	// Επίσκεψη τρέχοντος κόμβου
	result = append(result, root.Val)
	// Αναδρομική κλήση για το δεξί υποδέντρο
	result = append(result, InOrderTraversal(root.Right)...)

	return result
}

Παράδειγμα BFS:

// TreeNode αντιπροσωπεύει τον κόμβο ενός δυαδικού δέντρου
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// BFSTraversal εκτελεί διάσχιση BFS
func BFSTraversal(root *TreeNode) []int {
	var result []int
	if root == nil {
		return result
	}

	// Ουρά για αποθήκευση κόμβων σε τρέχον επίπεδο
	queue := []*TreeNode{root}

	for len(queue) > 0 {
		// Αφαιρούμε το πρώτο στοιχείο
		node := queue[0]
		queue = queue[1:]

		// Προσθέτουμε την τιμή του κόμβου στο αποτέλεσμα
		result = append(result, node.Val)

		// Προσθέτουμε τον αριστερό παιδί στην ουρά, αν υπάρχει
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
		// Προσθέτουμε τον δεξιό παιδί στην ουρά, αν υπάρχει
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
	return result
}

Για δυαδικά δέντρα αναζήτησης (BST), όπου το αριστερό υποδέντρο είναι μικρότερο από τη ρίζα και το δεξί μεγαλύτερο:

Δυαδική αναζήτηση: Κατά την αναζήτηση μιας συγκεκριμένης τιμής, συγκρίνουμε με τη ρίζα. Αν η τιμή είναι μικρότερη, αναζητούμε στο αριστερό υποδέντρο· αν μεγαλύτερη, στο δεξί. Αυτή είναι η πιο αποτελεσματική στρατηγική αναζήτησης σε BST.

// TreeNode αντιπροσωπεύει τον κόμβο ενός δυαδικού δέντρου αναζήτησης
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// SearchBST εκτελεί δυαδική αναζήτηση σε BST
func SearchBST(root *TreeNode, target int) *TreeNode {
	if root == nil || root.Val == target {
		return root // Βρέθηκε ο κόμβος ή το δέντρο είναι κενό
	}

	if target < root.Val {
		// Αναζητούμε στο αριστερό υποδέντρο
		return SearchBST(root.Left, target)
	}
	// Αναζητούμε στο δεξί υποδέντρο
	return SearchBST(root.Right, target)
}

Η επιλογή του αλγορίθμου αναζήτησης εξαρτάται από το πρόβλημα και τα χαρακτηριστικά του δέντρου. Το DFS είναι κατάλληλο για περιπτώσεις όπου πρέπει να προχωρήσετε βαθιά σε ένα κλάδο ή να βρείτε διαδρομή προς έναν στόχο. Το BFS είναι κατάλληλο για εύρεση της συντομότερης διαδρομής ή διάσχιση κατά επίπεδα. Η δυαδική αναζήτηση είναι αποτελεσματική για την εύρεση συγκεκριμένης τιμής σε ταξινομημένες δομές, όπως το BST.