درخت قرمز-سیاه یک درخت جستجوی باینری خود متعادل کننده است که در آن هر گره حاوی یک بیت اضافی برای نشان دادن رنگ گره، قرمز یا سیاه است. در این مقاله به بررسی این نوع درخت می‌پردازیم.
حتما بخوانید :
درخت تصمیم یا درخت تصمیم گیری چیست و چگونه کار می کند؟ویژگی های درخت قرمز- سیاه
یک درخت قرمز-سیاه دارای ویژگی های زیر است:
- ویژگی قرمز/سیاه: هر گره رنگی است، قرمز یا سیاه.
- ویژگی ریشه: ریشه سیاه است.
- ویژگی برگ: هر برگ (NIL) سیاه است.
- ویژگی قرمز: اگر یک گره قرمز دارای فرزند باشد، فرزندان همیشه سیاه هستند.
- ویژگی عمق: برای هر گره، هر مسیر ساده‌ای از این گره به هر یک از برگ‌های نواده آن، عمق سیاه یکسانی دارد (تعداد گره‌های سیاه).
عملیات های درخت قرمز-سیاه
عملیات‌های درخت قرمز-سیاه بطور کامل در مقاله عملیات‌های درخت قرمز-سیاه توضیح داده شده‌اند. برای آشنایی با این عملیات‌ها پیشنهاد می‌کنیم مقاله مربوطه را مطالعه کنید.
پیاده سازی درخت قرمز-سیاه
در ادامه به پیاده‌سازی درخت قرمز-سیاه درزبان های برنامه نویسی پایتون و سی پلاس پلاس می‌پردازیم:
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.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 متعادل‌تر است، جستجوی سریع‌تری را فراهم می‌کند. اما زمانی که بخواهیم عملیات درج و حذف را بیشتر در اولویت قرار دهیم، به دلیل چرخش‌های کمتر، باید به سراغ درخت قرمز-مشکی برویم.
مطالب مرتبط
همه مقالات
