Java Balanced Binary Search Tree with Strings

Açıklama

  • Balanced Binary Search Tree ( Dengeli İkili Arama Ağacı ) algoritmasının, verilerin birbirine göre küçüklük büyüklük ilişkisi göre ağaça yerleştilmesi ve her düğüm yükseklik farkı 1 yada 0 olmalıdır.
  • Bu algoritmada, Dengeli ikili ağaç oluştururken sıralanmış diziden yararlanıyoruz !

 

Görsel ile gösterim

blanced-tree-nonblanced-tree

 

Kod

package bst;

import java.io.File;
import java.io.FileNotFoundException;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class main2 {
	
	public static void main(String []args) {
		
		try {
		
			
			Scanner s = new Scanner(new File("words.txt"));
			
			ArrayList<String> a =new ArrayList<String>();
			
			while(s.hasNextLine()) {
				a.add(s.nextLine());
			}
				
			
			Collections.sort(a);
			
			ArrayList<Node> nodes = new ArrayList<Node>();
			
			for(int i=0;i<a.size();i++) {
				nodes.add(new Node(a.get(i)));
			}
			
		//	System.out.println(a.toString());
			
			
			
			BBST bbst = new BBST();
			
			bbst.root = b.add(nodes, 0, nodes.size()-1);  // dengeli ağaçın ilk kökünü belirleme işlemi ve rekürsif fonksiyonla dengeli ağaç oluşturma
			
			System.out.println(bbst.find("KodSözlük")); // dengeli ağaçta veri arama işlemi
			
			
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		
		
	}

}

class BBST{
	
	Node root;
	
	public BBST() {
		root=null;
	}
	
	
	
	
	public Node add(ArrayList<Node> nodes,int start,int end) {
		
		
		if(start > end)
			return null;
		
		int mid = (start+end)/2;
		
	//	System.out.println();
		
	//	System.out.println("mid= "+mid+" start= "+start+" end= "+end);
		
		Node node = nodes.get(mid);
		
		

		node.left = add(nodes,start,mid-1);
		node.right = add(nodes,mid+1,end);
		
		
		return node;
		
		
		
	}

	
	boolean find(String value) {
		
		
		Node tmp = root;
		Node pre = null;
	
	
		
		while(tmp != null) {
			
			
			
			pre=tmp;
			
			boolean large = false;
			
			if(tmp.value.equals(value))
				return true;
			
			
			
			for(int i=0;i<value.length();i++) {
				

				if(i < tmp.value.length() && i < value.length() && value.charAt(i) != tmp.value.charAt(i)) {
					if(value.charAt(i) < tmp.value.charAt(i)) {
						large=true;
						break;
					}
				}
				
			}
			
			if(large) {
				tmp = tmp.left;
			}
			else {
				tmp = tmp.right;
			}
			
		
			
			
		}
	
		return false;
	}
	
}

class Node  
{ 
    String value; 
    Node left, right; 
  
    public Node(String value)  
    { 
        this.value=value;
        left=null;
        right=null;
    } 
} 

Yorumlar

Bu gönderi için yorum yapılmadı.