İkili Arama Ağaçları (BST)

package main

import (
	"fmt"
	"strings"
)

type Node struct {
	Value       int
	Left, Right *Node
}

type BST struct {
	root *Node
	size int
}

// Insert: O(h) — h, ağacın yüksekliği
func (t *BST) Insert(v int) bool {
	if t.root == nil {
		t.root = &Node{Value: v}
		t.size++
		return true
	}
	cur := t.root
	for {
		switch {
		case v < cur.Value:
			if cur.Left == nil {
				cur.Left = &Node{Value: v}
				t.size++
				return true
			}
			cur = cur.Left
		case v > cur.Value:
			if cur.Right == nil {
				cur.Right = &Node{Value: v}
				t.size++
				return true
			}
			cur = cur.Right
		default:
			return false // zaten var
		}
	}
}

// Contains: O(h) — her adımda kalanın yarısı elenir (dengeli ağaçta)
func (t *BST) Contains(v int) (found bool, steps int) {
	for cur := t.root; cur != nil; {
		steps++
		switch {
		case v < cur.Value:
			cur = cur.Left
		case v > cur.Value:
			cur = cur.Right
		default:
			return true, steps
		}
	}
	return false, steps
}

// InOrder: sıralı çıktı — BST'nin tanımlayıcı özelliği
func (t *BST) InOrder() []int {
	out := make([]int, 0, t.size)
	var walk func(*Node)
	walk = func(n *Node) {
		if n == nil {
			return
		}
		walk(n.Left)
		out = append(out, n.Value)
		walk(n.Right)
	}
	walk(t.root)
	return out
}

func (t *BST) Height() int {
	var h func(*Node) int
	h = func(n *Node) int {
		if n == nil {
			return -1
		}
		return 1 + max(h(n.Left), h(n.Right))
	}
	return h(t.root)
}

// String: ağacı yatay olarak çizer (sağ üstte, sol altta)
func (t *BST) String() string {
	var sb strings.Builder
	var draw func(*Node, string, string)
	draw = func(n *Node, prefix, branch string) {
		if n == nil {
			return
		}
		draw(n.Right, prefix+"    ", "┌── ")
		fmt.Fprintf(&sb, "%s%s%d\n", prefix, branch, n.Value)
		draw(n.Left, prefix+"    ", "└── ")
	}
	draw(t.root, "", "")
	return sb.String()
}

func main() {
	var t BST
	for _, v := range []int{50, 30, 70, 20, 40, 60, 80} {
		t.Insert(v)
	}

	fmt.Print(t.String())
	fmt.Println("eleman sayısı:", t.size, "| yükseklik:", t.Height())
	fmt.Println("sıralı:", t.InOrder())

	fmt.Println()
	for _, v := range []int{40, 80, 45} {
		found, steps := t.Contains(v)
		fmt.Printf("%d ara → bulundu=%-5t adım=%d\n", v, found, steps)
	}

	fmt.Println("tekrar ekleme kabul edildi mi:", t.Insert(40))
}

package main

import "fmt"

type Node struct {
	Value       int
	Left, Right *Node
}

func insert(n *Node, v int) *Node {
	if n == nil {
		return &Node{Value: v}
	}
	switch {
	case v < n.Value:
		n.Left = insert(n.Left, v)
	case v > n.Value:
		n.Right = insert(n.Right, v)
	}
	return n
}

// Min: sürekli sola in — O(h)
func minNode(n *Node) *Node {
	if n == nil {
		return nil
	}
	for n.Left != nil {
		n = n.Left
	}
	return n
}

// Max: sürekli sağa in — O(h)
func maxNode(n *Node) *Node {
	if n == nil {
		return nil
	}
	for n.Right != nil {
		n = n.Right
	}
	return n
}

// successor: v'den büyük en küçük değer (inorder ardılı)
func successor(root *Node, v int) (int, bool) {
	var best *Node
	for cur := root; cur != nil; {
		if v < cur.Value {
			best = cur // aday: daha küçüğünü sol tarafta ara
			cur = cur.Left
		} else {
			cur = cur.Right
		}
	}
	if best == nil {
		return 0, false
	}
	return best.Value, true
}

// predecessor: v'den küçük en büyük değer
func predecessor(root *Node, v int) (int, bool) {
	var best *Node
	for cur := root; cur != nil; {
		if v > cur.Value {
			best = cur
			cur = cur.Right
		} else {
			cur = cur.Left
		}
	}
	if best == nil {
		return 0, false
	}
	return best.Value, true
}

// rangeQuery: [lo, hi] aralığındaki değerleri sıralı verir.
// Aralık dışındaki alt ağaçlara hiç inmez — budama (pruning).
func rangeQuery(n *Node, lo, hi int, out *[]int) {
	if n == nil {
		return
	}
	if n.Value > lo {
		rangeQuery(n.Left, lo, hi, out)
	}
	if n.Value >= lo && n.Value <= hi {
		*out = append(*out, n.Value)
	}
	if n.Value < hi {
		rangeQuery(n.Right, lo, hi, out)
	}
}

func main() {
	var root *Node
	for _, v := range []int{50, 30, 70, 20, 40, 60, 80, 35, 45} {
		root = insert(root, v)
	}

	fmt.Println("minimum:", minNode(root).Value)
	fmt.Println("maksimum:", maxNode(root).Value)

	fmt.Println()
	for _, v := range []int{40, 45, 80, 10} {
		s, sok := successor(root, v)
		p, pok := predecessor(root, v)
		fmt.Printf("%-3d → ardıl=%v(%t) önce gelen=%v(%t)\n", v, s, sok, p, pok)
	}

	fmt.Println()
	var inRange []int
	rangeQuery(root, 35, 65, &inRange)
	fmt.Println("35-65 aralığı:", inRange)

	var all []int
	rangeQuery(root, -1000, 1000, &all)
	fmt.Println("tüm değerler:", all)
}

package main

import "fmt"

type Node struct {
	Value       int
	Left, Right *Node
}

func insert(n *Node, v int) *Node {
	if n == nil {
		return &Node{Value: v}
	}
	switch {
	case v < n.Value:
		n.Left = insert(n.Left, v)
	case v > n.Value:
		n.Right = insert(n.Right, v)
	}
	return n
}

func minValue(n *Node) int {
	for n.Left != nil {
		n = n.Left
	}
	return n.Value
}

// remove: üç durumu da ele alır, yeni kökü döndürür
func remove(n *Node, v int) *Node {
	if n == nil {
		return nil
	}
	switch {
	case v < n.Value:
		n.Left = remove(n.Left, v)
	case v > n.Value:
		n.Right = remove(n.Right, v)
	default:
		// DURUM 1 ve 2: sıfır veya tek çocuk
		if n.Left == nil {
			return n.Right
		}
		if n.Right == nil {
			return n.Left
		}
		// DURUM 3: iki çocuk — ardılı yerine koy, ardılı sağdan sil
		n.Value = minValue(n.Right)
		n.Right = remove(n.Right, n.Value)
	}
	return n
}

func inorder(n *Node, out *[]int) {
	if n == nil {
		return
	}
	inorder(n.Left, out)
	*out = append(*out, n.Value)
	inorder(n.Right, out)
}

func collect(n *Node) []int {
	var out []int
	inorder(n, &out)
	return out
}

func contains(n *Node, v int) bool {
	for n != nil {
		switch {
		case v < n.Value:
			n = n.Left
		case v > n.Value:
			n = n.Right
		default:
			return true
		}
	}
	return false
}

func main() {
	var root *Node
	for _, v := range []int{50, 30, 70, 20, 40, 60, 80, 35} {
		root = insert(root, v)
	}
	fmt.Println("başlangıç:", collect(root))

	root = remove(root, 20) // durum 1: yaprak
	fmt.Println("20 (yaprak) silindi:  ", collect(root))

	root = remove(root, 30) // durum 2: tek çocuk (35)
	fmt.Println("30 (tek çocuk) silindi:", collect(root))

	root = remove(root, 50) // durum 3: iki çocuk
	fmt.Println("50 (iki çocuk) silindi:", collect(root))
	fmt.Println("yeni kök:", root.Value)

	root = remove(root, 999) // olmayan değer
	fmt.Println("olmayan değer sonrası:", collect(root))

	fmt.Println()
	fmt.Println("50 hâlâ var mı:", contains(root, 50))
	fmt.Println("60 var mı:", contains(root, 60))

	// Her şeyi sil
	for _, v := range collect(root) {
		root = remove(root, v)
	}
	fmt.Println("hepsi silindi, kök nil mi:", root == nil)
}

package main

import (
	"fmt"
	"math"
)

type Node struct {
	Value       int
	Left, Right *Node
}

// isBSTNaive: YANLIŞ — yalnızca yerel kontrol yapar
func isBSTNaive(n *Node) bool {
	if n == nil {
		return true
	}
	if n.Left != nil && n.Left.Value >= n.Value {
		return false
	}
	if n.Right != nil && n.Right.Value <= n.Value {
		return false
	}
	return isBSTNaive(n.Left) && isBSTNaive(n.Right)
}

// isBST: DOĞRU — her düğüme izin verilen aralığı taşır
func isBST(n *Node, lo, hi int) bool {
	if n == nil {
		return true
	}
	if n.Value <= lo || n.Value >= hi {
		return false
	}
	return isBST(n.Left, lo, n.Value) && isBST(n.Right, n.Value, hi)
}

// isBSTInorder: alternatif — inorder gezinme artan olmalı
func isBSTInorder(root *Node) bool {
	var prev *int
	var walk func(*Node) bool
	walk = func(n *Node) bool {
		if n == nil {
			return true
		}
		if !walk(n.Left) {
			return false
		}
		if prev != nil && *prev >= n.Value {
			return false
		}
		v := n.Value
		prev = &v
		return walk(n.Right)
	}
	return walk(root)
}

func main() {
	// Geçerli BST
	valid := &Node{50,
		&Node{30, &Node{20, nil, nil}, &Node{40, nil, nil}},
		&Node{70, &Node{60, nil, nil}, &Node{80, nil, nil}},
	}

	// Geçersiz: 60, kökün SOL alt ağacında olmasına rağmen 50'den büyük
	invalid := &Node{50,
		&Node{30, &Node{20, nil, nil}, &Node{60, nil, nil}},
		&Node{70, nil, &Node{80, nil, nil}},
	}

	fmt.Println("geçerli ağaç:")
	fmt.Println("  naif kontrol   :", isBSTNaive(valid))
	fmt.Println("  aralık kontrolü:", isBST(valid, math.MinInt, math.MaxInt))
	fmt.Println("  inorder kontrol:", isBSTInorder(valid))

	fmt.Println()
	fmt.Println("geçersiz ağaç:")
	fmt.Println("  naif kontrol   :", isBSTNaive(invalid), "← yanlış cevap!")
	fmt.Println("  aralık kontrolü:", isBST(invalid, math.MinInt, math.MaxInt))
	fmt.Println("  inorder kontrol:", isBSTInorder(invalid))

	fmt.Println()
	fmt.Println("boş ağaç geçerli mi:", isBST(nil, math.MinInt, math.MaxInt))
}

package main

import "fmt"

type Node struct {
	Value       int
	Left, Right *Node
}

func insert(n *Node, v int) *Node {
	if n == nil {
		return &Node{Value: v}
	}
	if v < n.Value {
		n.Left = insert(n.Left, v)
	} else if v > n.Value {
		n.Right = insert(n.Right, v)
	}
	return n
}

func height(n *Node) int {
	if n == nil {
		return -1
	}
	return 1 + max(height(n.Left), height(n.Right))
}

func searchSteps(n *Node, v int) int {
	steps := 0
	for n != nil {
		steps++
		switch {
		case v < n.Value:
			n = n.Left
		case v > n.Value:
			n = n.Right
		default:
			return steps
		}
	}
	return steps
}

// balancedInsert: sıralı diliminden dengeli ağaç kurar (orta elemanı kök yap)
func balancedInsert(values []int) *Node {
	if len(values) == 0 {
		return nil
	}
	mid := len(values) / 2
	return &Node{
		Value: values[mid],
		Left:  balancedInsert(values[:mid]),
		Right: balancedInsert(values[mid+1:]),
	}
}

func main() {
	const n = 1023

	sorted := make([]int, n)
	for i := range sorted {
		sorted[i] = i + 1
	}

	// 1) Sıralı ekleme: dejenere ağaç
	var degenerate *Node
	for _, v := range sorted {
		degenerate = insert(degenerate, v)
	}

	// 2) Dengeli kurulum
	balanced := balancedInsert(sorted)

	fmt.Printf("%-22s %10s %14s\n", "ağaç", "yükseklik", "arama adımı")
	fmt.Printf("%-22s %10d %14d\n", "sıralı eklenmiş", height(degenerate), searchSteps(degenerate, n))
	fmt.Printf("%-22s %10d %14d\n", "dengeli kurulmuş", height(balanced), searchSteps(balanced, n))

	fmt.Println()
	fmt.Println("teorik en iyi yükseklik (log₂ 1023 ≈ 9):", height(balanced))
	fmt.Println("dejenere ağaç kaç kat daha yavaş:",
		searchSteps(degenerate, n)/searchSteps(balanced, n))
}