Hướng dẫn red-black tree python library - thư viện trăn cây đỏ đen
Trong bài viết này, chúng tôi sẽ nghiên cứu một cây đen đỏ là gì và tại sao nó hữu ích. Chúng tôi sẽ hiểu các hoạt động khác nhau của cây màu đỏ đỏ cùng với thuật toán, ví dụ và mã Python của chúng. Sau đó, chúng tôi cũng sẽ trải qua các ưu điểm, nhược điểm và ứng dụng khác nhau của cây đỏ đen. & NBSP; Show
Cây đỏ đen là gì?Một cây đen đỏ là biến thể của cây tìm kiếm nhị phân với tính chất tự cân bằng. Một cây đen đỏ còn được gọi là Binary B-cây đối xứng. Mỗi nút của cây màu đỏ đỏ chứa một thuộc tính bổ sung biểu thị màu của nút, cụ thể là màu đỏ hoặc đen. Tầm quan trọng của các màu này trong các nút của cây đảm bảo rằng cây được cân bằng trong khi chèn và xóa các hoạt động của nút. Do đó, cây đen đỏ tuân theo các thuộc tính dưới đây:binary search tree with the property of self-balancing. A red-black tree is also called symmetric binary B-Tree. Every node of the red-black tree contains an extra attribute denoting the color of the node, specifically, either red or black. The importance of these colors in the nodes of the tree ensures that the tree is balanced while insertion and deletion operations of the node. Therefore, the red-black tree follows the below properties:
Hãy nhớ rằng mọi nút của cây màu đỏ đỏ chỉ tiêu thụ 1 bit bộ nhớ lưu trữ để lưu trữ thông tin màu, do đó cây giống hệt với cây tìm kiếm nhị phân cổ điển. Tại sao phải sử dụng cây màu đỏ đen? & NBSP;Như bạn đã biết rằng cây tìm kiếm nhị phân duy trì thứ tự tự nhiên của dữ liệu được chèn, nhưng nó không hạn chế kích thước, chiều dài hoặc chiều cao của cây. Hãy xem xét hình ảnh dưới đây nơi các nút được chèn vào cây tìm kiếm nhị phân là 10,20,30,40,50. Ở đây, chiều cao của cây là 5 khi cây phát triển tuyến tính khi nút mới được chèn. Do đó, khi chiều cao của cây phát triển tuyến tính, hoạt động tìm kiếm trong cây trở thành trường hợp xấu nhất và mất thời gian O (n) trong đó n là tổng số nút được chèn.height of the tree. Consider the below image where the nodes inserted in the binary search tree are 10,20,30,40,50. Here, the height of the tree is 5 as the tree grows linearly when the new node is inserted. Hence, as the height of the tree grows linearly, the search operation in the tree becomes the worst-case scenario and takes O(n) time where n is the total number of nodes inserted. Vấn đề này có thể được giải quyết bằng cách sử dụng một cây màu đen đỏ. Khi cây màu đen màu đỏ duy trì chiều cao của cây sau mỗi lần chèn và xóa, cây có thể tránh khỏi độ lệch. Do đó, độ phức tạp thời gian cho hoạt động tìm kiếm được giảm xuống O (log n) trong đó n là số lượng nút trong cây.O(log n) where n is the number of nodes in the tree. Thay vì một cây đen đỏ, bạn cũng có thể sử dụng cây AVL để cân bằng chiều cao của cây. Nhưng cần lưu ý rằng cây màu đen đỏ tạo ra ít thay đổi cấu trúc hơn để cân bằng chiều cao của cây so với cây AVL. Do đó, cây đen đỏ có khả năng nhanh hơn trong quá trình chèn và xóa so với cây AVL.AVL tree to balance the height of the tree. But it is noted, that the red-black tree makes fewer structural changes to balance the height of the tree in comparison to AVL trees. Hence, the red-black tree is potentially faster during insertion and deletion operations in comparison to AVL trees. Xoay trong cây đen màu đỏXoay là quá trình điều chỉnh hoặc trao đổi các nút của các cây con bên trong cây theo cách mà chiều cao của cây được khôi phục. Nó giúp duy trì các thuộc tính cây màu đỏ đỏ đôi khi bị vi phạm trong khi chèn và xóa các hoạt động. Về cơ bản, có hai loại xoay trong cây đỏ đen: 1) Xoay bên tráiCác nút ở bên phải của cây được chuyển đổi ở nút bên trái được gọi là xoay bên trái. Nhìn vào thuật toán dưới đây để hiểu. Thuật toán
2) Xoay bên phảiCác nút ở bên trái của cây được chuyển đổi ở nút bên phải được gọi là vòng quay bên trái. Nhìn vào thuật toán dưới đây để hiểu. Thuật toán
2) Xoay bên phảiCác nút ở bên trái của cây được chuyển đổi ở nút bên phải được gọi là vòng quay bên trái. Nhìn vào thuật toán dưới đây để hiểu. Hãy xem xét cây màu đỏ đỏ bên dưới Chỉ định ‘B, làm nút mẹ của phần cây con bên phải của‘ A, nếu ‘A, có một cây con bên phảiGán ’a" là gốc của cây nếu cha mẹ của ‘b, là null
Tạo ra ’một" là nút cha mẹ của ‘B,3) Xoay bên trái và bên trái phảiRed Node. This is because the insertion of a new node does not violate the depth property of the red-black tree. But what if the red node gets attached to the red node? Well, this problem is easier to fix using rotation rather than violating the depth property of the tree. Later, if the tree properties are violated then the red-black tree undergoes the following operations:
Thuật toán để chèn nútLet ‘x’ be the root node of the tree and ‘y’ be the leaf node If the tree is empty, add NewNode as the root node and black in color Else, repeat the below steps till we reach the leaf of the tree Compare NewNode with RootNode If NewNode is greater than RootNode, traverse to the right subtree Otherwise, traverse through the left subtree Assign parent of leaf to parent of NewNode If LeafNode is greater than NewNode, assign NewNode as RightChild Otherwise, assign NewNode as LeftChild Assign Null to LeftChild and RightChild of NewNode Assign NewNode as Red color Apply InsertionFix Algorithm if the property of the red-black tree is violated Thuật toán chèn để duy trì thuộc tính cây đen đỏIf parent ‘n’ of NewNode is Red then: If ‘n’ is the LeftChild of GrandParent ‘gp’ of ‘m’ then Case 1: If RightChild of ‘gp’ is Red color, set color of both children of ‘gp’ as Black color and ‘gp’ as Red Color Assign ‘gp’ to NewNode Case 2: If NewNode is RightChild of ‘n’ then, assign ‘n’ to NewNode Left-Rotate NewNode Case 3: Assign ‘n’ as Black and ‘gp’ as Red Right-Rotate ‘gp’ Otherwise, do the following If LeftChild of ‘gp’ of ‘z’ is Red color, then set both children of ‘gp’ as Black color and ‘gp’ as Red color Assign ‘gp’ to NewNode If NewNode is LeftChild of ‘n’ then, assign ‘n’ to NewNode and Right Rotate NewNode Set ‘n’ as Black color and ‘gp’ as Red color Left-Rotate ‘gp’ Set Root of the tree as Black color Thí dụ Chèn nút ‘4 bên trong một cây trống. Như đã thảo luận, phần tử được chèn đầu tiên luôn là nút gốc và màu đen Bây giờ, chèn nút ‘20, bên trong cây. Như 20> 4, nó sẽ được chèn dưới dạng cây con phù hợp của nút gốc và màu đỏ Bây giờ, chèn nút ‘31 bên trong cây. Như 31> 20, nó sẽ là con phù hợp của nút cha ‘20. Node xông 31 có màu đỏ và theo tính chất của cây màu đỏ đen, không có hai nút màu đỏ nào có thể được cùng nhau và do đó chúng tôi trải qua vòng quay RR để lấy lại sự cân bằng của cây. Bây giờ, chèn nút ‘14 bên trong cây. Như 14> 4 nhưng 14 Do đó, cấu trúc cây cuối cùng sẽ được đưa ra dưới đây: Hoạt động xóaKhi bạn xóa một nút từ cây, có những khả năng bạn vi phạm thuộc tính cây đen đỏ. Do đó, sau khi tháo nút ra khỏi cây, hãy đảm bảo bạn cân bằng cây bằng cách làm theo các thuộc tính của cây. Thuật toán để xóa một nútSave the color of DeletingNode in OriginalColor If LeftChild of DeletingNode is Null Assign the RightChild of DeletingNode to be ‘a’ Transplant DeletingNode with ‘a’ Otherwise, if the RighChild of DeletingNode is Null Assign the LeftChild of DeletingNode into ‘a’ Transplant DeletingNode with ‘a’ Otherwise Assign the minimum of Right-Subtree of DeletingNode into ‘b’ Save the color of ‘b’ in OriginalColor Assign the RightChild of ‘b’ into ‘a’ If ‘b’ is a child of DeletingNode, then set the parent of ‘a’ as ‘b’ Otherwise, transplant ‘b’ with RightChild of ‘b’ Transplant DeletingNode with ‘b’ Set color of ‘b’ with OriginalColor Call DeletionFix if the OriginalColor is Black Khi việc DeletingNode có màu đen, nó vi phạm thuộc tính cây đen đỏ. Kịch bản này có thể được sửa chữa bằng cách giả sử rằng nút ‘A, có thêm màu đen. Do đó, nút ’A, không phải là màu đỏ hay đen thay vào đó là màu đen hoặc đen và đỏ cùng một lúc. Do đó, tài sản cây đen đỏ bị vi phạm. Do đó, có thể loại bỏ thêm màu đen nếu
Thuật toán xóaFix để duy trì thuộc tính cây đen đỏRepeat the following until the ‘a’ is not the RootNode of the tree and ‘a’ is not the Black colored If ‘a’ is the LeftChild of its parent then, Assign ‘n’ to the sibling of ‘a’ If RightChild of the parent of ‘a’ is Red Case 1: Set RightChild of the parent of ‘a’ as Black color Set parent of ‘a’ as Red Color Left-Rotate the parent of ‘a’ Assign the RightChild of the parent of ‘a’ to ‘n’ If RightChild and the LeftChild of ‘n’ is Black in color Case 2: Set ‘n’ as Red color Assign parent of ‘a’ to ‘a’ Otherwise, if the RightChild of ‘n’ is Black in color Case 3: Set the LeftChild of ‘n’ as Black color Set ‘n’ as Red color Right-rotate ‘n’ Assign the RightChild of the parent of ‘a’ to ‘n’ If all of the above cases don’t occur, then do the following Case 4: Set color of ‘n’ as the color of the parent of ‘a’ Set parent of ‘a’ as Black color Set RightChild ‘n’ as Black color Left-rotate the parent of ‘a’ Set ‘a’ as RootNode of tree Repeat the same steps as above by interchanging the right to left and vice versa Set ‘a’ as Black color Thí dụ Chèn nút ‘4 bên trong một cây trống. Như đã thảo luận, phần tử được chèn đầu tiên luôn là nút gốc và màu đen Bây giờ, chèn nút ‘20, bên trong cây. Như 20> 4, nó sẽ được chèn dưới dạng cây con phù hợp của nút gốc và màu đỏ Bây giờ, chèn nút ‘31 bên trong cây. Như 31> 20, nó sẽ là con phù hợp của nút cha ‘20. Node xông 31 có màu đỏ và theo tính chất của cây màu đỏ đen, không có hai nút màu đỏ nào có thể được cùng nhau và do đó chúng tôi trải qua vòng quay RR để lấy lại sự cân bằng của cây. Bây giờ, chèn nút ‘14 bên trong cây. Như 14> 4 nhưng 14 Do đó, cấu trúc cây cuối cùng sẽ được đưa ra dưới đây:# Define Node class Node(): def __init__(self,val): self.val = val # Value of Node self.parent = None # Parent of Node self.left = None # Left Child of Node self.right = None # Right Child of Node self.color = 1 # Red Node as new node is always inserted as Red Node # Define R-B Tree class RBTree(): def __init__(self): self.NULL = Node ( 0 ) self.NULL.color = 0 self.NULL.left = None self.NULL.right = None self.root = self.NULL # Insert New Node def insertNode(self, key): node = Node(key) node.parent = None node.val = key node.left = self.NULL node.right = self.NULL node.color = 1 # Set root colour as Red y = None x = self.root while x != self.NULL : # Find position for new node y = x if node.val < x.val : x = x.left else : x = x.right node.parent = y # Set parent of Node as y if y == None : # If parent i.e, is none then it is root node self.root = node elif node.val < y.val : # Check if it is right Node or Left Node by checking the value y.left = node else : y.right = node if node.parent == None : # Root node is always Black node.color = 0 return if node.parent.parent == None : # If parent of node is Root Node return self.fixInsert ( node ) # Else call for Fix Up def minimum(self, node): while node.left != self.NULL: node = node.left return node # Code for left rotate def LR ( self , x ) : y = x.right # Y = Right child of x x.right = y.left # Change right child of x to left child of y if y.left != self.NULL : y.left.parent = x y.parent = x.parent # Change parent of y as parent of x if x.parent == None : # If parent of x == None ie. root node self.root = y # Set y as root elif x == x.parent.left : x.parent.left = y else : x.parent.right = y y.left = x x.parent = y # Code for right rotate def RR ( self , x ) : y = x.left # Y = Left child of x x.left = y.right # Change left child of x to right child of y if y.right != self.NULL : y.right.parent = x y.parent = x.parent # Change parent of y as parent of x if x.parent == None : # If x is root node self.root = y # Set y as root elif x == x.parent.right : x.parent.right = y else : x.parent.left = y y.right = x x.parent = y # Fix Up Insertion def fixInsert(self, k): while k.parent.color == 1: # While parent is red if k.parent == k.parent.parent.right: # if parent is right child of its parent u = k.parent.parent.left # Left child of grandparent if u.color == 1: # if color of left child of grandparent i.e, uncle node is red u.color = 0 # Set both children of grandparent node as black k.parent.color = 0 k.parent.parent.color = 1 # Set grandparent node as Red k = k.parent.parent # Repeat the algo with Parent node to check conflicts else: if k == k.parent.left: # If k is left child of it's parent k = k.parent self.RR(k) # Call for right rotation k.parent.color = 0 k.parent.parent.color = 1 self.LR(k.parent.parent) else: # if parent is left child of its parent u = k.parent.parent.right # Right child of grandparent if u.color == 1: # if color of right child of grandparent i.e, uncle node is red u.color = 0 # Set color of childs as black k.parent.color = 0 k.parent.parent.color = 1 # set color of grandparent as Red k = k.parent.parent # Repeat algo on grandparent to remove conflicts else: if k == k.parent.right: # if k is right child of its parent k = k.parent self.LR(k) # Call left rotate on parent of k k.parent.color = 0 k.parent.parent.color = 1 self.RR(k.parent.parent) # Call right rotate on grandparent if k == self.root: # If k reaches root then break break self.root.color = 0 # Set color of root as black # Function to fix issues after deletion def fixDelete ( self , x ) : while x != self.root and x.color == 0 : # Repeat until x reaches nodes and color of x is black if x == x.parent.left : # If x is left child of its parent s = x.parent.right # Sibling of x if s.color == 1 : # if sibling is red s.color = 0 # Set its color to black x.parent.color = 1 # Make its parent red self.LR ( x.parent ) # Call for left rotate on parent of x s = x.parent.right # If both the child are black if s.left.color == 0 and s.right.color == 0 : s.color = 1 # Set color of s as red x = x.parent else : if s.right.color == 0 : # If right child of s is black s.left.color = 0 # set left child of s as black s.color = 1 # set color of s as red self.RR ( s ) # call right rotation on x s = x.parent.right s.color = x.parent.color x.parent.color = 0 # Set parent of x as black s.right.color = 0 self.LR ( x.parent ) # call left rotation on parent of x x = self.root else : # If x is right child of its parent s = x.parent.left # Sibling of x if s.color == 1 : # if sibling is red s.color = 0 # Set its color to black x.parent.color = 1 # Make its parent red self.RR ( x.parent ) # Call for right rotate on parent of x s = x.parent.left if s.right.color == 0 and s.right.color == 0 : s.color = 1 x = x.parent else : if s.left.color == 0 : # If left child of s is black s.right.color = 0 # set right child of s as black s.color = 1 self.LR ( s ) # call left rotation on x s = x.parent.left s.color = x.parent.color x.parent.color = 0 s.left.color = 0 self.RR ( x.parent ) x = self.root x.color = 0 # Function to transplant nodes 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 # Function to handle deletion def delete_node_helper ( self , node , key ) : z = self.NULL while node != self.NULL : # Search for the node having that value/ key and store it in 'z' if node.val == key : z = node if node.val <= key : node = node.right else : node = node.left if z == self.NULL : # If Kwy is not present then deletion not possible so return print ( "Value not present in Tree !!" ) return y = z y_original_color = y.color # Store the color of z- node if z.left == self.NULL : # If left child of z is NULL x = z.right # Assign right child of z to x self.__rb_transplant ( z , z.right ) # Transplant Node to be deleted with x elif (z.right == self.NULL) : # If right child of z is NULL x = z.left # Assign left child of z to x self.__rb_transplant ( z , z.left ) # Transplant Node to be deleted with x else : # If z has both the child nodes y = self.minimum ( z.right ) # Find minimum of the right sub tree y_original_color = y.color # Store color of y x = y.right if y.parent == z : # If y is child of z x.parent = y # Set parent of x as 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 : # If color is black then fixing is needed self.fixDelete ( x ) # Deletion of node def delete_node ( self , val ) : self.delete_node_helper ( self.root , val ) # Call for deletion # Function to print def __printCall ( self , node , indent , last ) : if node != self.NULL : print(indent, end=' ') if last : print ("R----",end= ' ') indent += " " else : print("L----",end=' ') indent += "| " s_color = "RED" if node.color == 1 else "BLACK" print ( str ( node.val ) + "(" + s_color + ")" ) self.__printCall ( node.left , indent , False ) self.__printCall ( node.right , indent , True ) # Function to call print def print_tree ( self ) : self.__printCall ( self.root , "" , True ) if __name__ == "__main__": bst = RBTree() bst.insertNode(10) bst.insertNode(20) bst.insertNode(30) bst.insertNode(5) bst.insertNode(4) bst.insertNode(2) bst.print_tree() print("\nAfter deleting an element") bst.delete_node(2) bst.print_tree() Hoạt động xóaKhi bạn xóa một nút từ cây, có những khả năng bạn vi phạm thuộc tính cây đen đỏ. Do đó, sau khi tháo nút ra khỏi cây, hãy đảm bảo bạn cân bằng cây bằng cách làm theo các thuộc tính của cây. Thuật toán để xóa một nút Khi việc DeletingNode có màu đen, nó vi phạm thuộc tính cây đen đỏ. Kịch bản này có thể được sửa chữa bằng cách giả sử rằng nút ‘A, có thêm màu đen. Do đó, nút ’A, không phải là màu đỏ hay đen thay vào đó là màu đen hoặc đen và đỏ cùng một lúc. Do đó, tài sản cây đen đỏ bị vi phạm.Do đó, có thể loại bỏ thêm màu đen nếu Nó đạt đến rootnode
Để chèn, xóa và hoạt động tìm kiếm, độ phức tạp thời gian cho cây đen đỏ là hàm logarit, tức là o (log n) trong đó n là tổng số nút trong cây màu đỏ. Trong khi đó, độ phức tạp không gian của cây màu đỏ là O (n).
Nó cung cấp tìm kiếm hiệu quả vì cây AVL được cân bằng nghiêm ngặt
Các nút có màu đỏ hoặc đen
Sự kết luậnCây đen đỏ là & nbsp; một trong những thành viên của cây tìm kiếm nhị phân giúp duy trì chiều cao của cây nhị phân giống như cây AVL.Mỗi nút trong cây tìm kiếm nhị phân & nbsp; được tô màu đỏ hoặc đen, giúp duy trì các thuộc tính của cây và cung cấp một phương pháp hiệu quả và hiệu quả để chèn và xóa các hoạt động của nút trong cây nhị phân bằng cách trải qua ít xoay hơn.Do đó, điều quan trọng là phải hiểu và sử dụng cây đỏ đỏ để tăng cường độ phức tạp thời gian tìm kiếm của cây tìm kiếm nhị phân bằng cách ngăn chặn cây bị lệch.Để biết thêm chi tiết, vui lòng tham khảo chương trình gia sư mở rộng của chúng tôi được thiết kế bởi các chuyên gia tại Favtutor. & NBSP; |