Red Black Trees Top Down Deletion Anlatım

Red-Black Tree Deletion (TOP DOWN)

Red-Black Tree(Kırmızı-Siyah Ağaçlar) üzerinde ekleme ve silme üzerine türkçe makaleler bulamadığım için ve özellikle top-down deletion konusunda ingilizce olarakta kaynak sıkıntısı yaşadığım için anladığım kadarı ile açıklamaya çalışacağım.

Red-Black Tree nedir?

Red-Black tree bir çeşit binary tree'dir. Bildiğiniz üzere binary tree ikili ağaçlar demektir. Peki binary tree varken neden bu tarz ağaç sistemleri oluşturulmuştur? Binary tree tek başına bir yere kadar hayatımızı kurtarıyor. Sayılar rasgele geldiği zaman size O(logn) arama , ekleme ve silme maliyetini garanti ediyor.

Binary tree Visualization

Peki veriler rasgele değilde sıralı gelirse. İkili ağaçlarda eklemeler tek bir kurala göre yapılıyor ve bu kural ağacın tek kuralı. Bu durum sıralı verilerde soruna yol açıyor.

Binary tree Visualization

Bu tarz durumlarda sağ alt ağaca yapacağınız işlemler O(n) oluyor. İkili ağaçların en büyük özelliği işlemleri O(logn) zaman karmaşıklığında yapabilmemiz. Bu tarz durumları çözmek için ise AVL-SPLAY-RED BLACK TREE ağaçlar geliştirilmiştir. Bu ağaç çeşitleri ağaç üzerinde döndürmeler yaparak ağacı dengeli hale getirmeyi amaçlar.(splay belki biraz daha farklı ama amaç aynı)

Şimdi örnek olması açısından AVL ve Red Black üzerine 1,2,3,4,5,6 değerlerini ekleyelim ve ağaçların yapısına bakalım.


AVL Tree Visualization

Red-Black Tree Visualization

Gördüğünüz üzere her ağaç kendi yapısına uygun şekilde ağacı daha düzenli hale getiriyor. Bu yazımda sizin Ağaç nedir? İkili Ağaç nedir? AVL nedir? bildiğinizi kabul ederek devam edeceğim ve RB(red-black) Insertion kolay ve anlaşılır olduğundan ve bu konuda yeterli makale olduğunu düşündüğümden o konu üzerine düşmeyeceğim.

Red-Black Tree Top-Down Deletion

Red-Black üzerinde silme işlemi gerçekten yorucu bir süreç. Kural üstüne kural gelirken sadece döndürme değil aynı zamanda renklendirmeler-döndürmeler yapılır. Direk konuya giriyorum.
Öncelikle bu işlemi, yazdığım C# kodu üzerinden anlatacağımı belirtmek isterim. Eğer ingilizcenize güveniyorsanız ve C++/C tercih ediyorsanız buradan devam edebilirsiniz. Gayet güzel bir anlatım ve esprili bir üslubu ile bu sayfa size daha eğlenceli zaman geçirtebilir. Bizimle kalanlar ile devam ediyoruz :)
Silmeye girmeden hemen önce yardımcı fonksiyonlar ile başlamak isterim.

NodeHasChild,IsRed,Move ve TreeDirection enum


	enum TreeDirection:byte { None=0,Right,Left}
	bool NodeHasChild(Node node)
	{
	return (node != null && (node.right != null \|\| node.right != null));
	}

	bool isRed(Node node)
	{
	return node != null && node.treeColor == TreeColor.Red;
	}
	private TreeDirection Move(int data,ref Node x,ref Node p,ref Node s)
	{
	if (data < x.data && isRed(x))
	{
	p = x;
	s = x.right;
	x = x.left;
	return TreeDirection.Left;
	}
	if (data > x.data && isRed(x))
	{
	p = x;
	s = x.left;
	x = x.right;
	return TreeDirection.Right;
	}
	return TreeDirection.None;
	}
	private void SingleLeftRotation(Node node, Node parent, Node grandParent)
	{

	Node temp = node.left;
	//node is parents parent now
	node.left = parent;
	parent.parent = node;
	//so node is the new child of gp
	grandParent.left = node;
	node.parent = grandParent;
	parent.right = temp;
	if (temp != null)
	temp.parent = parent;
	}

	private void SingleRightRotation(Node node, Node parent, Node grandParent)
	{
	Node temp = node.right;
	//node is parents parent now
	node.right = parent;
	parent.left = temp;
	parent.parent = node;
	//so node is the new child of gp
	grandParent.right = node;
	node.parent = grandParent;
	if (temp != null)
	temp.parent = parent;
	}

	private void RotateRight(Node parent, Node grandParent)
	{
	Node tempParentRight = parent.right;
	parent.parent = grandParent.parent;
	if (grandParent.parent != null && grandParent.parent.right == grandParent)
	{
	grandParent.parent.right = parent;
	}
	else if (grandParent.parent != null && grandParent.parent.left == grandParent)
	{
	grandParent.parent.left = parent;
	}
	parent.right = grandParent;
	grandParent.parent = parent;
	grandParent.left = tempParentRight;

	if (tempParentRight != null)
	tempParentRight.parent = grandParent;

	//swap colors
	TreeColor tempNodeColor = grandParent.treeColor;
	grandParent.treeColor = parent.treeColor;
	parent.treeColor = tempNodeColor;
	}
	private void RotateLeft(Node parent, Node grandParent)
	{
	// Console.WriteLine(parent.data);
	Node tempParentLeft = parent.left;
	parent.parent = grandParent.parent;
	if (grandParent.parent != null && grandParent.parent.right == grandParent)
	{
	grandParent.parent.right = parent;
	}
	else if (grandParent.parent != null && grandParent.parent.left == grandParent)
	{
	grandParent.parent.left = parent;
	}
	parent.left = grandParent;
	grandParent.parent = parent;
	grandParent.right = tempParentLeft;

	if (tempParentLeft != null)
	tempParentLeft.parent = grandParent;

	//swap colors
	TreeColor tempNodeColor = grandParent.treeColor;
	grandParent.treeColor = parent.treeColor;
	parent.treeColor = tempNodeColor;
	}

view raw Red Black Tree Top-Down Del Helpers.cs hosted with ❤ by GitHub

-        private void DelFunc(Node x, TreeDirection treeDirection)
-        {
-            if (treeDirection == TreeDirection.Left)
-            {
-                x.parent.left = null;
-            }
-            else if (treeDirection == TreeDirection.Right)
-            {
-                x.parent.right = null;
-            }
-            x.parent = null;
-         }

view raw RB HELPER DELETE.cs hosted with ❤ by GitHub

NodeHasChild: Bulunduğumuz düğüm herhangi bir çocuğa sahip mi?
IsRed    :Bulunduğumuz düğüm kırmızı mı?
Move                :Eğer bulunduğun düğüm kırmızı ise aranan veriye göre sola yada sağa ilerle. Parent Sibling ve X değerini güncelle geriye hangi tarafa gittiğini belirten değeri dönder.
ROTATIONS :Single ve double rotation işlemlerini halleden referans aktarımı yapılan metodlar.
DelFunc    : Silinecek düğüm ağaçtan koparılmak için kullanılır

Top-Down Deletion temel amacı:

Size kendi anladığım gibi anlatacağım ve bunun %100 literatürde olduğu gibi olduğunu söylemiyorum.
Eğer ağaçta aradığınız veriyi bulacaksanız ilerlemeniz gerekiyor ve bunun için her zaman bir sonraki düğüme geçtiğinizde ulaştığınız düğümün kırmızı yada o düğüme geldiğiniz bir önceki düğümün(ebeveyninin) kırmızı olduğundan emin olacaksınız. Tüm döndürme ve yeniden renklendirme işlemleri bunu garanti etmeyi amaçlıyor. Eğer yanılıyorsam yanlış bildiğim bir şeyi sezerseniz yorumlarda belirtirseniz sevinirim bu sayede daha doğru bir makale olmuş olur.

İlk olarak silmek istediğimiz veriyi arayacağız ve ağaca kök düğümden giriyoruz. İlk önce silmek istediğimiz veri bu mu diye bakıyoruz eğer silinecek veri bulunmuşsa işlemlerde küçük bir nüans eklemesi ile aynı şekilde devam edeceğiz. Silinecek veriyi bulamadığımızı düşünelim ve verimiz kökten küçük olsun sol ağaca gitmemiz gerekiyor ama gitmeden şu kontrolleri yapmalıyız.
Kök kırmızı mı?
Kökün çocuğu var mı?
Kökün kırmızı çocuğu var mı?
RB Tree de kökün asla kırmızı olmayacağını biliyoruz o halde bu durumu ana kök için atlayabiliriz ve sadece kökün çocuğu var mı ve en az bir tanesi kırmızı mı?

Eğer kökün hiç kırmızı çocuğu yok ise kök girişte kırmızı yapılır. İşlemler yapıldıktan sonra kök siyah hale getirilir.

	else if(x == root && !isRed(x) && !isRed(x.left) && !isRed(x.right) )
	{
	Console.WriteLine("root black childs black");
	x.treeColor = TreeColor.Red;
	treeDirection = Move(data,ref x,ref p,ref s);
	}

view raw rbTD Del.cs hosted with ❤ by GitHub

Kök kırmızı yapıldıktan sonra bir sonraki uygun düğüme ilerlenir. Bu düğüm için kontroller yapılır.

	//if X has any red child
	else if(isRed(x.left) \|\| isRed(x.right))
	{
	//check if there is a red node under x if there is just move
	//move to the node which is appropriate
	treeDirection = Move(data, ref x, ref p, ref s);
	//check where did you move
	//if you are in red node keep moving
	if (isRed(x))
	{
	treeDirection = Move(data, ref x, ref p, ref s);
	}
	//if you are in black node rotate red node around parent
	else
	{
	//rotate s around p
	if(treeDirection == TreeDirection.Right)
	{
	//rotate left side
	SingleLeftRotation(s, p, p.parent);
	}
	else if(treeDirection == TreeDirection.Left)
	{
	//rotate right side
	SingleRightRotation(s, p, p.parent);
	}
	//recolor p and s
	TreeColor temp = s.treeColor;
	s.treeColor = p.treeColor;
	p.treeColor = temp;
	}
	}

view raw rbTD Del red child.cs hosted with ❤ by GitHub

Kırmızı ise ilerlemeye devam edeceğiz. Eğer gelinen düğüm kırmızı değilse:
Bu durumu görselleştirelim

Bu durumda üst düğümün sağ tarafına mı yoksa sol tarafına mı girdiğimiz önem kazanıyor çünkü burada bir döndürme ve yeniden renklendirme mevcut. Eğer burada olduği gibi sağa girmişsek
kırmızı olan kardeşimizi yani S düğümünü P yani ebeveyn düğümün etrafında döndürülür ve P - S arasında bir renk dönüşümü yapılır. Bu işlemin sonucunda oluşacak yapı daha önce bahsettiğimiz ebeveyni kırmızı hale getirme yapısıdır. Yani kırmızı bir düğümden gelmişsek buraya bu ağaç düzgündür gibi bir algı oluşturabiliriz. Ağacın dönmüş hali:

Ağacın dönmüş hali bu şekilde ama henüz işlemler bitmedi. İlk olarak kırmızı-kırmızı bozukluğu görüyoruz. İkincisi X e geldiğimiz düğümün kırmızı olacağından bahsetmiştik ama olmadığını görüyoruz. P ve S düğümleri renk değiş-tokuşu yapacak.

Renk değiş-tokuşu yapıldıktan sonra yaşanılan problemlerin çözüldüğünü gördük. Burada bahsetmemiz gereken bir durum var yazdığım kod üzerinde bu işlem rotasyonlar yapılırken hallediliyor. Ama eğer S düğümünün sağında çocuğu var ise bu data yı kaybedemeyiz. S'nin sağına P yi koyduk S nin eski sağını da P nin soluna yazarsak ne ağaç bozulur ne de veri kaybı olur. P > S olduğu için S nin altında kalan tüm değerler P den küçüktür. P nin soluna yazmak ağacı bu sebepten bozmayacaktır. Burada kırmızı P nin solunda siyah P nin sağında kalıyordu ve döndürmeler ona göre yapıldı. S ve X in yerleri tam tersi olursa döndürme ona uygun olacak şekilde yapılır. Bu bizim ağaç üzerinde döndürme işlemi hakkında ne kadar bildiğimiz ile alakalı.

X in çocuklarından ikisi de siyah ise=>

Tüm çocuklar siyah

	//if there is no red nodes under X so we have to check childrens of sibling of X
	else
	{
	//if sibling is on the left side so you have to make double rotation
	if (isRed(s.left) && treeDirection == TreeDirection.Right)
	{
	//left left ->single rotation
	RotateRight(s, s.parent);
	TreeColor temp = p.treeColor;
	p.treeColor = TreeColor.Black;
	x.treeColor = temp;
	s.treeColor = temp;
	if(s.right != null)
	s.right.treeColor = TreeColor.Black;
	}

	else if (isRed(s.right) && treeDirection == TreeDirection.Right)
	{
	//left right ->double
	SingleLeftRotation(s.right, s, s.parent);
	RotateRight(s.right, s);
	x.treeColor = TreeColor.Red;
	p.treeColor = TreeColor.Black;

	}
	else if (isRed(s.right) && treeDirection == TreeDirection.Left)
	{
	//right right -> single rot
	RotateLeft(s, s.parent);
	TreeColor temp = p.treeColor;
	p.treeColor = TreeColor.Black;
	x.treeColor = temp;
	s.treeColor = temp;
	if(s.left!=null)
	s.left.treeColor = TreeColor.Black;
	}
	else if (isRed(s.left) && treeDirection == TreeDirection.Left)
	{
	//right left -> double
	SingleRightRotation(s.right, s, s.parent);
	RotateRight(s.right, s);
	x.treeColor = TreeColor.Red;
	p.treeColor = TreeColor.Black;
	}
	else
	{
	//all childrens of s are black recolor p,x,s
	TreeColor temp = x.parent.treeColor;
	x.parent.treeColor = x.treeColor;
	x.treeColor = temp;
	s.treeColor = temp;
	}
	}
	}
	root.treeColor = TreeColor.Black;
	}

view raw Red Black Tree Top-Down Del No Red child.cs hosted with ❤ by GitHub

Eğer X in her iki çocuğuda siyah ise bu durumda kardeşinin çocukları önemlidir. Eğer kardeşinin çocukları da siyah ise un var yağ var şeker var helva yapsana.... :(

Bu durumda işimiz çok kolay:
X ve S => P'nin rengini alır
P de X in eski rengini alır.
Bu örnek üzerinde X ve S kırmızı olacak
P siyah olacak
X artık kırmızı olduğu için uygun çocuğa ilerleyebiliriz.

S nin çocuklarından birisi veya ikisi de kırmızı ise döndür ve yeniden renklendir uygulayacağız. Döndürme işlemleri S nin çocuklarına bağlı
eğer S nin kırmızı olan tek çocuğu var ve bu çocuk iç tarafta ise:

İç çocuklar kırmızı

Bu durumda iç çocuk baz alınarak çift döndürme yapılır ve X=Kırmızı P = Siyah yapılır.

Eğer dış çocuk kırmızı ise yada iki çocuk birden kırmızı ise tek döndürme ve renklendirme yapılır.
İki çocukta kırmızı iken dış çocuk baz alınır çünkü tek döndürme işlemi yapılır daha az işleme tabi tutlmuş olur.

Dış çocuklar kırmızı

Dış çocuklar baz alınarak tek döndürme yapılır ve P=Siyah X,S=Kırmızı ve S nin döndürülen çocuğu =Siyah şeklinde yeniden renklendiriliyor

Aranan düğüm bulunduğunda:

	if (data == x.data)
	{
	//find the max value of left sub tree and change datas and do all recolorings
	//if you find a node which has no child then check rules and delete
	if (NodeHasChild(x))
	{
	TreeDirection tD = TreeDirection.None;
	Node currentNode=null;
	//biggest val of left
	if (x.left != null)
	{
	currentNode = x.left;
	while (currentNode != null)
	{
	if (currentNode.right != null)
	currentNode = currentNode.right;
	else
	break;
	}

	tD = TreeDirection.Left;
	}
	//smallest val of right
	if (x.right != null)
	{
	currentNode = x.right;
	while (currentNode != null)
	{
	if (currentNode.left != null)
	currentNode = currentNode.left;
	else
	break;
	}
	tD = TreeDirection.Right;
	}
	int cData = currentNode.data;
	currentNode.data = x.data;
	x.data = cData;
	if(tD == TreeDirection.Right)
	{
	x = x.right;
	}
	else if(tD == TreeDirection.Left)
	{
	x = x.left;
	}
	//if the leaf node is red then change the val and delete it
	//it wont change the black height of the tree
	if (currentNode.treeColor == TreeColor.Red)
	{
	DelFunc(currentNode, tD);
	break;
	}
	//Console.WriteLine(currentNode.data);
	continue;
	}
	else
	{

	DelFunc(x, treeDirection);
	break;
	}
	}

view raw Red black topdown Deletion Data Found.cs hosted with ❤ by GitHub

Eğer düğümün sol alt ağacı mevcutsa en büyük değer alınır değilse sağ alt ağacın en küçüğüne bakılır. Eğer bulunduğumuz düğüm herhangi bir çocuğa sahip değilse ve kırmızı ise(ki işlemlerin sonucunda kırmızı yapılacaktır) DelFunc çağrılıp değer ağaçtan kopartılır.
Silme işlemi bu şekilde tamamlanmış olur.

Kodun tam halini buradan alabilirsiniz.Insertion Kodu dahil.
Github hesabıma buradan gidip projelere göz atıp düzeltmeler için önerilerde bulunabilirsiniz.