SPLAY TREE Ağaç Yapısı [ Data Structure ]

13:25 | 1 Comments

Honeyd kodları üzerinde kodları anlamak için kendimi yırtarken karşıma çıkan arpd paketinin içerisinde "tree.h" dosyasında "SPLAY TREE" diye bir yapı ile karşılaştım ilgimi çekti diye araştırdım Türkçe aramalarda çıkmadı bile. Derslerde de görmediğim bu yapıyı araştırmaya karar verdim. While i researched codes of honeyd I saw about SPLAY TREE in tree.h in arpd packet. I researched it and I didn't find Turkish results. I decided to understand this data structure. Algoritmaya göre bir kez kullanılan düğümün bir sonrakinde de kullanılacağında hemen bulunmasını sağlar. Özel bir veri yapısı olduğu için pek karşılaşmıyoruz sanırım. honeyd içinde bol bol karşılaştığım bu yapıyı nerelerde ne için kullanacak merak ediyorum. Şimdi gelelim basitçe şu yapıyı anlatmaya... Algorithm ; A node has used other search first node to be provide, This is a Private data structure so we don't see anywhere. Lets see this structure.
LRU ilkesine dayalı bir ağaç yapısıdır. Aranan düğüm "root" olur ve en az sıklıkla kullanılan düğüm "root"tan uzaklaşır.
It is a tree structe like LRU policy. The node that is being searh will be root and least frequently used node will move away from the root node
SPLAY TREE yapısında 3 durum bulunmaktadır. (Kısaltmalar: aranan düğüm : n(x) , n(x) düğümünün atası Pn, root r ) SPLAY TREE structure have 3 cases
Ana Durum- Main case
1. DURUM :(Zig Adımı)
-n(x) 'root' un hemen altında ise
-n(x) 'root' olur. -'child nodes' sıralama için düzenlenir. 1. CASE:(Zig Step) - if the parent of n(x) is the root - rotate at n(x) ,make n(x) the root - makes its former parent into its child - fixes child nodes for order.
Durum 1.
- 2 yi bul - 2 yi root yap - 5 yi sağa ötele - find 2 -2 is the root - rotate right 5
yeni root=2; eski root=6; new root=2; old root=6; -----------------------------------------------------------------------
2. Durum :(Zig Zig Adımı) - n(x) ve Pn aynı yönde ise(hepsi sağ ya da hepsi sol dal) -n(x) 'root' olur. -dal yönü değişir 'root' a göre sıralanır. -'child nodes' sıralamaya göre düzenlenir. 2.Case : (Zig Zig Step) -if n(x) and Pn have the same orientation (each one right or each one left) - first rotate at Pn then at n(x) - make n(x) the root - branch changes and orders according to root - fix child nodes
1 yi bul; - 1 i root yap - 1<2<6>2>6 olarak çevir. -5 'i 2 den kopar bir üst 'parent' a göre düzenle 2 1 6 5 7 10 15 find 1; - 1 is the root -change branch 1<2<6>2>1 -fix 5
3. Durum : (Zig Zag Adımı) - n(x) ve Pn aynı yönde değil ise (biri sağ yön diğeri sol ya da tam tersi) -n(x) iki kez döndülür ve root olur. -'child nodes' dala göre sıralanır. 3.Case : (Zig Zag Step) - n(x) and Pn have different orientation (one of them right direction, other one left direction or opposite) - rotate twice at n(x) - make 2 the root - fix 'child nodes'
bul : 5 -5 i iki kez 'root' a yaklaştır sonra 'root' yap -5 ile 10 arasında kalan 6 yı ağaca göre düzenle
find :5 -rotate 5 and make root - fix 6 between 5 to 10
Bağlantılar : Links : http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/Splay-Algorithm.html http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/splay-case1.html http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/splay-case2a.html http://www.ibr.cs.tu-bs.de/courses/ss98/audii/applets/BST/splay-case3.html http://en.wikipedia.org/wiki/Splay_tree http://techunix.technion.ac.il/~itai/

About

seruhatto