درخت قرمز-سیاه یک درخت جستجوی باینری خود متعادل کننده است که در آن هر گره حاوی یک بیت اضافی برای نشان دادن رنگ گره، قرمز یا سیاه است. در این مقاله به بررسی این نوع درخت میپردازیم.
ویژگی های درخت قرمز- سیاه
یک درخت قرمز-سیاه دارای ویژگی های زیر است:
- ویژگی قرمز/سیاه: هر گره رنگی است، قرمز یا سیاه.
- ویژگی ریشه: ریشه سیاه است.
- ویژگی برگ: هر برگ (NIL) سیاه است.
- ویژگی قرمز: اگر یک گره قرمز دارای فرزند باشد، فرزندان همیشه سیاه هستند.
- ویژگی عمق: برای هر گره، هر مسیر سادهای از این گره به هر یک از برگهای نواده آن، عمق سیاه یکسانی دارد (تعداد گرههای سیاه).
عملیات های درخت قرمز-سیاه
عملیاتهای درخت قرمز-سیاه بطور کامل در مقاله عملیاتهای درخت قرمز-سیاه توضیح داده شدهاند. برای آشنایی با این عملیاتها پیشنهاد میکنیم مقاله مربوطه را مطالعه کنید.
پیاده سازی درخت قرمز-سیاه
در ادامه به پیادهسازی درخت قرمز-سیاه درزبان های برنامه نویسیزبان های برنامه نویسی چیست؟این مقاله عالی توضیح داده که زبان های برنامه نویسی چیست؟ و انواع زبان های برنامه نویسی و بهترین زبان برنامه نویسی برای شروع و پردرآمدترین آنها را معرفی کرده پایتونزبان برنامه نویسی پایتون چیست؟ – نحوه شروع و دلایل محبوبیتزبان برنامه نویسی پایتون (Python) چیست؟ این مقاله عالی به بررسی دلایل محبوبیت پایتون، موارد استفاده از پایتون و نحوه شروع به برنامه نویسی پایتون پرداخته و سی پلاس پلاسبرنامه نویسی سی پلاس پلاس چیست؟ مزایای برنامه نویسی C++؟برنامه نویسی سی پلاس پلاس چیست و چه کاربردی دارد؟ این صفحه عالی به بررسی مزایای برنامه نویسی C++ پرداخته و نمونه هایی از کدهای زبان برنامه نویسی ++C را آورده میپردازیم:
Python
import sys
# Node creation
class Node:
def __init__(self, item):
self.item = item
self.parent = None
self.left = None
self.right = None
self.color = 1
class RedBlackTree:
def __init__(self):
self.TNULL = Node(0)
self.TNULL.color = 0
self.TNULL.left = None
self.TNULL.right = None
self.root = self.TNULL
# Preorder
def pre_order_helper(self, node):
if node != TNULL:
sys.stdout.write(node.item + " ")
self.pre_order_helper(node.left)
self.pre_order_helper(node.right)
# Inorder
def in_order_helper(self, node):
if node != TNULL:
self.in_order_helper(node.left)
sys.stdout.write(node.item + " ")
self.in_order_helper(node.right)
# Postorder
def post_order_helper(self, node):
if node != TNULL:
self.post_order_helper(node.left)
self.post_order_helper(node.right)
sys.stdout.write(node.item + " ")
# Search the tree
def search_tree_helper(self, node, key):
if node == TNULL or key == node.item:
return node
if key < node.item:
return self.search_tree_helper(node.left, key)
return self.search_tree_helper(node.right, key)
# Balancing the tree after deletion
def delete_fix(self, x):
while x != self.root and x.color == 0:
if x == x.parent.left:
s = x.parent.right
if s.color == 1:
s.color = 0
x.parent.color = 1
self.left_rotate(x.parent)
s = x.parent.right
if s.left.color == 0 and s.right.color == 0:
s.color = 1
x = x.parent
else:
if s.right.color == 0:
s.left.color = 0
s.color = 1
self.right_rotate(s)
s = x.parent.right
s.color = x.parent.color
x.parent.color = 0
s.right.color = 0
self.left_rotate(x.parent)
x = self.root
else:
s = x.parent.left
if s.color == 1:
s.color = 0
x.parent.color = 1
self.right_rotate(x.parent)
s = x.parent.left
if s.right.color == 0 and s.left.color == 0:
s.color = 1
x = x.parent
else:
if s.left.color == 0:
s.right.color = 0
s.color = 1
self.left_rotate(s)
s = x.parent.left
s.color = x.parent.color
x.parent.color = 0
s.left.color = 0
self.right_rotate(x.parent)
x = self.root
x.color = 0
def __rb_transplant(self, u, v):
if u.parent == None:
self.root = v
elif u == u.parent.left:
u.parent.left = v
else:
u.parent.right = v
v.parent = u.parent
# Node deletion
def delete_node_helper(self, node, key):
z = self.TNULL
while node != self.TNULL:
if node.item == key:
z = node
if node.item <= key:
node = node.right
else:
node = node.left
if z == self.TNULL:
print("Cannot find key in the tree")
return
y = z
y_original_color = y.color
if z.left == self.TNULL:
x = z.right
self.__rb_transplant(z, z.right)
elif z.right == self.TNULL:
x = z.left
self.__rb_transplant(z, z.left)
else:
y = self.minimum(z.right)
y_original_color = y.color
x = y.right
if y.parent == z:
x.parent = y
else:
self.__rb_transplant(y, y.right)
y.right = z.right
y.right.parent = y
self.__rb_transplant(z, y)
y.left = z.left
y.left.parent = y
y.color = z.color
if y_original_color == 0:
self.delete_fix(x)
# Balance the tree after insertion
def fix_insert(self, k):
while k.parent.color == 1:
if k.parent == k.parent.parent.right:
u = k.parent.parent.left
if u.color == 1:
u.color = 0
k.parent.color = 0
k.parent.parent.color = 1
k = k.parent.parent
else:
if k == k.parent.left:
k = k.parent
self.right_rotate(k)
k.parent.color = 0
k.parent.parent.color = 1
self.left_rotate(k.parent.parent)
else:
u = k.parent.parent.right
if u.color == 1:
u.color = 0
k.parent.color = 0
k.parent.parent.color = 1
k = k.parent.parent
else:
if k == k.parent.right:
k = k.parent
self.left_rotate(k)
k.parent.color = 0
k.parent.parent.color = 1
self.right_rotate(k.parent.parent)
if k == self.root:
break
self.root.color = 0
# Printing the tree
def __print_helper(self, node, indent, last):
if node != self.TNULL:
sys.stdout.write(indent)
if last:
sys.stdout.write("R----")
indent += " "
else:
sys.stdout.write("L----")
indent += "| "
s_color = "RED" if node.color == 1 else "BLACK"
print(str(node.item) + "(" + s_color + ")")
self.__print_helper(node.left, indent, False)
self.__print_helper(node.right, indent, True)
def preorder(self):
self.pre_order_helper(self.root)
def inorder(self):
self.in_order_helper(self.root)
def postorder(self):
self.post_order_helper(self.root)
def searchTree(self, k):
return self.search_tree_helper(self.root, k)
def minimum(self, node):
while node.left != self.TNULL:
node = node.left
return node
def maximum(self, node):
while node.right != self.TNULL:
node = node.right
return node
def successor(self, x):
if x.right != self.TNULL:
return self.minimum(x.right)
y = x.parent
while y != self.TNULL and x == y.right:
x = y
y = y.parent
return y
def predecessor(self, x):
if x.left != self.TNULL:
return self.maximum(x.left)
y = x.parent
while y != self.TNULL and x == y.left:
x = y
y = y.parent
return y
def left_rotate(self, x):
y = x.right
x.right = y.left
if y.left != self.TNULL:
y.left.parent = x
y.parent = x.parent
if x.parent == None:
self.root = y
elif x == x.parent.left:
x.parent.left = y
else:
x.parent.right = y
y.left = x
x.parent = y
def right_rotate(self, x):
y = x.left
x.left = y.right
if y.right != self.TNULL:
y.right.parent = x
y.parent = x.parent
if x.parent == None:
self.root = y
elif x == x.parent.right:
x.parent.right = y
else:
x.parent.left = y
y.right = x
x.parent = y
def insert(self, key):
node = Node(key)
node.parent = None
node.item = key
node.left = self.TNULL
node.right = self.TNULL
node.color = 1
y = None
x = self.root
while x != self.TNULL:
y = x
if node.item < x.item:
x = x.left
else:
x = x.right
node.parent = y
if y == None:
self.root = node
elif node.item < y.item:
y.left = node
else:
y.right = node
if node.parent == None:
node.color = 0
return
if node.parent.parent == None:
return
self.fix_insert(node)
def get_root(self):
return self.root
def delete_node(self, item):
self.delete_node_helper(self.root, item)
def print_tree(self):
self.__print_helper(self.root, "", True)
if __name__ == "__main__":
bst = RedBlackTree()
bst.insert(55)
bst.insert(40)
bst.insert(65)
bst.insert(60)
bst.insert(75)
bst.insert(57)
bst.print_tree()
print("\nAfter deleting an element")
bst.delete_node(40)
bst.print_tree()
C++
#include <iostream>
using namespace std;
struct Node
{
int data;
Node *parent;
Node *left;
Node *right;
int color;
};
typedef Node *NodePtr;
class RedBlackTree
{
private:
NodePtr root;
NodePtr TNULL;
void initializeNULLNode(NodePtr node, NodePtr parent)
{
node->data = 0;
node->parent = parent;
node->left = nullptr;
node->right = nullptr;
node->color = 0;
}
// Preorder
void preOrderHelper(NodePtr node)
{
if (node != TNULL)
{
cout node->data " ";
preOrderHelper(node->left);
preOrderHelper(node->right);
}
}
// Inorder
void inOrderHelper(NodePtr node)
{
if (node != TNULL)
{
inOrderHelper(node->left);
cout node->data " ";
inOrderHelper(node->right);
}
}
// Post order
void postOrderHelper(NodePtr node)
{
if (node != TNULL)
{
postOrderHelper(node->left);
postOrderHelper(node->right);
cout node->data " ";
}
}
NodePtr searchTreeHelper(NodePtr node, int key)
{
if (node == TNULL || key == node->data)
{
return node;
}
if (key < node->data)
{
return searchTreeHelper(node->left, key);
}
return searchTreeHelper(node->right, key);
}
// For balancing the tree after deletion
void deleteFix(NodePtr x)
{
NodePtr s;
while (x != root && x->color == 0)
{
if (x == x->parent->left)
{
s = x->parent->right;
if (s->color == 1)
{
s->color = 0;
x->parent->color = 1;
leftRotate(x->parent);
s = x->parent->right;
}
if (s->left->color == 0 && s->right->color == 0)
{
s->color = 1;
x = x->parent;
}
else
{
if (s->right->color == 0)
{
s->left->color = 0;
s->color = 1;
rightRotate(s);
s = x->parent->right;
}
s->color = x->parent->color;
x->parent->color = 0;
s->right->color = 0;
leftRotate(x->parent);
x = root;
}
}
else
{
s = x->parent->left;
if (s->color == 1)
{
s->color = 0;
x->parent->color = 1;
rightRotate(x->parent);
s = x->parent->left;
}
if (s->right->color == 0 && s->right->color == 0)
{
s->color = 1;
x = x->parent;
}
else
{
if (s->left->color == 0)
{
s->right->color = 0;
s->color = 1;
leftRotate(s);
s = x->parent->left;
}
s->color = x->parent->color;
x->parent->color = 0;
s->left->color = 0;
rightRotate(x->parent);
x = root;
}
}
}
x->color = 0;
}
void rbTransplant(NodePtr u, NodePtr v)
{
if (u->parent == nullptr)
{
root = v;
}
else if (u == u->parent->left)
{
u->parent->left = v;
}
else
{
u->parent->right = v;
}
v->parent = u->parent;
}
void deleteNodeHelper(NodePtr node, int key)
{
NodePtr z = TNULL;
NodePtr x, y;
while (node != TNULL)
{
if (node->data == key)
{
z = node;
}
if (node->data <= key)
{
node = node->right;
}
else
{
node = node->left;
}
}
if (z == TNULL)
{
cout "Key not found in the tree" endl;
return;
}
y = z;
int y_original_color = y->color;
if (z->left == TNULL)
{
x = z->right;
rbTransplant(z, z->right);
}
else if (z->right == TNULL)
{
x = z->left;
rbTransplant(z, z->left);
}
else
{
y = minimum(z->right);
y_original_color = y->color;
x = y->right;
if (y->parent == z)
{
x->parent = y;
}
else
{
rbTransplant(y, y->right);
y->right = z->right;
y->right->parent = y;
}
rbTransplant(z, y);
y->left = z->left;
y->left->parent = y;
y->color = z->color;
}
delete z;
if (y_original_color == 0)
{
deleteFix(x);
}
}
// For balancing the tree after insertion
void insertFix(NodePtr k)
{
NodePtr u;
while (k->parent->color == 1)
{
if (k->parent == k->parent->parent->right)
{
u = k->parent->parent->left;
if (u->color == 1)
{
u->color = 0;
k->parent->color = 0;
k->parent->parent->color = 1;
k = k->parent->parent;
}
else
{
if (k == k->parent->left)
{
k = k->parent;
rightRotate(k);
}
k->parent->color = 0;
k->parent->parent->color = 1;
leftRotate(k->parent->parent);
}
}
else
{
u = k->parent->parent->right;
if (u->color == 1)
{
u->color = 0;
k->parent->color = 0;
k->parent->parent->color = 1;
k = k->parent->parent;
}
else
{
if (k == k->parent->right)
{
k = k->parent;
leftRotate(k);
}
k->parent->color = 0;
k->parent->parent->color = 1;
rightRotate(k->parent->parent);
}
}
if (k == root)
{
break;
}
}
root->color = 0;
}
void printHelper(NodePtr root, string indent, bool last)
{
if (root != TNULL)
{
cout indent;
if (last)
{
cout "R----";
indent += " ";
}
else
{
cout "L----";
indent += "| ";
}
string sColor = root->color ? "RED" : "BLACK";
cout << root->data << "(" << sColor << ")" << endl;
printHelper(root->left, indent, false);
printHelper(root->right, indent, true);
}
}
public:
RedBlackTree()
{
TNULL = new Node;
TNULL->color = 0;
TNULL->left = nullptr;
TNULL->right = nullptr;
root = TNULL;
}
void preorder()
{
preOrderHelper(this->root);
}
void inorder()
{
inOrderHelper(this->root);
}
void postorder()
{
postOrderHelper(this->root);
}
NodePtr searchTree(int k)
{
return searchTreeHelper(this->root, k);
}
NodePtr minimum(NodePtr node)
{
while (node->left != TNULL)
{
node = node->left;
}
return node;
}
NodePtr maximum(NodePtr node)
{
while (node->right != TNULL)
{
node = node->right;
}
return node;
}
NodePtr successor(NodePtr x)
{
if (x->right != TNULL)
{
return minimum(x->right);
}
NodePtr y = x->parent;
while (y != TNULL && x == y->right)
{
x = y;
y = y->parent;
}
return y;
}
NodePtr predecessor(NodePtr x)
{
if (x->left != TNULL)
{
return maximum(x->left);
}
NodePtr y = x->parent;
while (y != TNULL && x == y->left)
{
x = y;
y = y->parent;
}
return y;
}
void leftRotate(NodePtr x)
{
NodePtr y = x->right;
x->right = y->left;
if (y->left != TNULL)
{
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == nullptr)
{
this->root = y;
}
else if (x == x->parent->left)
{
x->parent->left = y;
}
else
{
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
void rightRotate(NodePtr x)
{
NodePtr y = x->left;
x->left = y->right;
if (y->right != TNULL)
{
y->right->parent = x;
}
y->parent = x->parent;
if (x->parent == nullptr)
{
this->root = y;
}
else if (x == x->parent->right)
{
x->parent->right = y;
}
else
{
x->parent->left = y;
}
y->right = x;
x->parent = y;
}
// Inserting a node
void insert(int key)
{
NodePtr node = new Node;
node->parent = nullptr;
node->data = key;
node->left = TNULL;
node->right = TNULL;
node->color = 1;
NodePtr y = nullptr;
NodePtr x = this->root;
while (x != TNULL)
{
y = x;
if (node->data x->data)
{
x = x->left;
}
else
{
x = x->right;
}
}
node->parent = y;
if (y == nullptr)
{
root = node;
}
else if (node->data < y->data)
{
y->left = node;
}
else
{
y->right = node;
}
if (node->parent == nullptr)
{
node->color = 0;
return;
}
if (node->parent->parent == nullptr)
{
return;
}
insertFix(node);
}
NodePtr getRoot()
{
return this->root;
}
void deleteNode(int data)
{
deleteNodeHelper(this->root, data);
}
void printTree()
{
if (root)
{
printHelper(this->root, "", true);
}
}
};
int main()
{
RedBlackTree bst;
bst.insert(55);
bst.insert(40);
bst.insert(65);
bst.insert(60);
bst.insert(75);
bst.insert(57);
bst.printTree();
cout endl
"After deleting" endl;
bst.deleteNode(40);
bst.printTree();
}
کاربردهای درخت قرمز-سیاه
- برای پیاده سازی پکیجهای جاواجاوا چیست؟ تعریف، معنی و ویژگی های جاوا (java) از 0تا100جاوا یک زبان برنامه نویسی همه منظوره، مبتنی بر کلاس و شی گرا است که برای داشتن وابستگی های پیاده سازی کمتر طراحی شده است، زبان برنامه نویسی جاوا شبیه ++C است: java.util.TreeMap و java.util.TreeSet
- برای پیادهسازی کتابخانههای قالب استاندارد (STL) در C++: multiset، map، multimap
- در کرنل لینوکس
جمعبندی
یکی از اساسیترین ساختمان دادهآموزش ساختمان داده و الگوریتمهر ساختمان داده یک نوع فرمت ذخیرهسازی و مدیریت دادهها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن دادهها را برای یکسری از الگوریتمها و کاربردها فراهم میکند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده استها، درخت جستجوی دودویی برای جستجو و مرتبسازی دادهها است. با این حال، عملکرد یک درخت جستجوی دودویی به شدت به شکل آن بستگی دارد و در بدترین حالت، میتواند به یک ساختار خطی با پیچیدگی زمانیپیچیدگی زمانی الگوریتم چیست؟ معرفی نماد های مجانبیاین صفحه عالی به معرفی پیچیدگی زمانی الگوریتم پرداخته، همچنین انواع نماد های مجانبی و پیچیدگی زمانی های برخی از الگوریتم های مرتب سازی و جستجو را توضیح داده O(n) تبدیل شود. اینجاست که درختان قرمز-سیاه وارد میشوند. آنها یک درخت جستجوی باینری متعادل هستند که از مجموعه قوانین خاصی برای اطمینان از اینکه درخت همیشه متعادل است استفاده میکنند. این تعادل تضمین میکند که پیچیدگی زمانی برای عملیاتهایی مانند درج، حذف و جستجو، صرفنظر از شکل اولیه درخت، همیشه O(log n) است. در این مقاله به بررسی این نوع درختان پرداختیم و همچنین با پیادهسازی آنها و برخی کاربردهای آنها آشنا شدیم.
درخت قرمز-سیاه چیست؟
درخت قرمز-سیاه یک درخت جستجوی دودویی با ویژگی های قرمز-سیاه زیر است:
هر گره یا قرمز یا سیاه است.
هر برگ (NIL) سیاه است.
اگر یک گره قرمز باشد، هر دو فرزند آن سیاه هستند.
هر مسیر ساده از یک گره به یک برگ شامل تعداد برابری گره سیاه است.
آیا یک درخت قرمز-سیاه میتواند تمام سیاه باشد؟
بله، اما این موضوع برای درخت قرمز-سیاه با تمام گرههای قرمز صادق نیست. چنین درختی باطل است. محدودیتهایی وجود دارد که گرهها باید سیاه باشند؛ به عنوان مثال، گرههای برگ باید سیاه باشند و فرزندان یک گره قرمز باید سیاه باشند.
چرا درخت قرمز-سیاه بهتر از درخت جستجوی دودویی است؟
به دلیل تغییرات کوچک ایجاد شده و پیروی از خواص درخت قرمز-سیاه، درخت می تواند بدترین حالت خود را از زمان خطی O(N) به زمان لگاریتمی O(log N) بهبود بخشد. با مقادیر کوچک N، N و log(N) قابل مقایسه هستند، اما با رشد دادهها، زمان لگاریتمی به طور قابل توجهی کمتر از زمان خطی میشود.
درخت AVL بهتر است یا درخت قرمز-سیاه؟
از آنجایی که درخت AVL متعادلتر است، جستجوی سریعتری را فراهم میکند. اما زمانی که بخواهیم عملیات درج و حذف را بیشتر در اولویت قرار دهیم، به دلیل چرخشهای کمتر، باید به سراغ درخت قرمز-مشکی برویم.