Red black tree python

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Python implementation of reb black tree

ersul4ik/rbt

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Реализация алгоритма написана на Python 3.

Девушка: Нарисуй дерево. Программист: (рисует бинарное дерево) Девушка: Нет, другое. Программист: Я и красно-черное дерево могу нарисовать.

КЧД наследует все свойства от обычного бинарного дерева + :

• Каждый узел окрашен либо в красный, либо в черный цвет (в структуре данных узла появляется дополнительное поле – бит цвета).
• Корень окрашен в черный цвет.
• Листья(так называемые NULL-узлы) окрашены в черный цвет.
• Каждый красный узел должен иметь два черных дочерних узла. Нужно отметить, что у черного узла могут быть черные дочерние узлы. Красные узлы в качестве дочерних могут иметь только черные.
• Пути от узла к его листьям должны содержать одинаковое количество черных узлов(это черная высота).

About

Python implementation of reb black tree

Источник

Building a Red-Black Binary Tree in Python

Curated backend podcasts, videos and articles. All free.

If you’re looking to become a backend developer, or just stay up-to-date with the latest backend technologies and trends, you found the right place. Subscribe below to get a copy of our newsletter, The Boot.dev Beat, each month in your inbox. No spam, no sponsors, totally free.

A red-black tree is a kind of self-balancing binary search tree. Each node stores an extra bit, which we will call the color, red or black. The color ensures that the tree remains approximately balanced during insertions and deletions. When the tree is modified, the new tree is rearranged and repainted to restore the coloring properties that constrain how unbalanced the tree can become in the worst case.

The purpose of a red-black tree is to stay balanced which ensures that its common operations, like lookup and delete, never degrade to worse than O(n*log(n)) .

🔗 What is a balanced binary tree?

Since the reason colors are added to a binary tree is to ensure that it remains balanced, we need to understand how and why a binary tree is balanced. To put it simply, a balanced tree’s branches differ in height by no more than 1.

The following tree is balanced because between its two branches one has a height of 2, and the other 3, meaning they differ by no more than 1.

The next tree is unbalanced because it’s branches differ in height by more than 1. C ’s right side has a height of 2 while its left side has a height of 4).

🔗 Why do we want balanced trees?

Balanced binary search trees ensure speed. The speed of an operation in a binary tree depends on the height of the tree. If the tree is balanced, then the height is only the log of the number of nodes, which means the tree will work as fast as possible. However, if the tree is unbalanced, for example with one really long branch, then the height because the total number of nodes rather than the log.

🔗 Properties of a red-black tree

In addition to all the properties of a Binary Search Tree, a red-black tree must have the following:

1. Each node is either red or black
2. The root is black. This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice versa, this rule has little effect on analysis.
3. All nil leaf nodes are black.
4. If a node is red, then both its children are black.
5. All paths from a single node go through the same number of black nodes to reach any of its descendant nil nodes.

🔗 Implementing a Red-Black Tree in Python

🔗 Step 1 – RBNode Class

Our implementation will use a Tree class and a Node class. The Node will be fairly simple, it’s just a constructor.

Next let’s create a tree class with a constructor.

    The insert method will look a lot like a traditional binary tree insert method. The biggest difference is that after doing an insert, we’ll call a special fix_insert method. For now just call it, we’ll implement it in just a moment.

🔗 Step 4 — Rotate left

We’ll need some rotation methods in our “fix” step that’s coming up. Let’s code those now.

The real bread and butter is in this step, it’s what makes a red-black tree balanced.

   Full Example of Red-Black Tree in Code 

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Red-black tree implementation in Python

License

emilydolson/python-red-black-trees

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

A Python implementation of red-black trees. This code was originally copied from programiz.com, but I have made a few tweaks to improve the user interface. I have also fixed a hard-to-catch but serious bug in the original implementation (which has since been propogated to a number of tutorials on the internet), and added a rigorous testing suite to ensure there are no further bugs.

I made this repo so that students in my algorithms class can try out red-black trees without needing to use C++. Feel free to use it for similar educational purposes! For more practical use-cases, you’re probably better off using the SortedContainers library, which is more efficient, more scalable, and better maintained.

This data structure is designed to be used either as a standard red-black binary search tree or as a red-black tree backed dictionary.

Standard red-black tree interface

A new red-black tree can be constructed as follows:

Items can be inserted into a tree using the insert method:

bst.insert(5) # inserts a node with value 5 

Items can be removed from the tree using the delete method. This method will do nothing if there is no item in the tree with the specific key.

bst.delete(5) # removes a node with value 5 

The minimum and maximum value in the tree can be found with the corresponding methods. If the tree is empty, these methods will both return the special value bst.TNULL

bst.minimum() # returns minimum value bst.maximum() # returns maximum value bst.minimum() == bst.TNULL # Check whether tree is empty 

Tree size can be accessed via the size member variable:

bst.size # contains the tree's size 

To find a specific item in the tree, you can use the search method:

bst.search(6) # returns the node containing 6. Will return bst.TNULL if item is not present. 

Predecessor and successor

To get a node’s predecessor or sucessor;

bst.predecessor(bst.search(6)) # Gets the predecessor a node containing 6 bst.successor(bst.search(6)) # Gets the successor a node containing 6 

To know more about the contents of the tree, you can print it to stdout:

bst.print_tree() # prints an ASCII representation of the whole tree 

To contents of the tree can be collected into an array in any of three ways. The tree itself can be used anywhere a collection is used.

bst.preorder() # creates a preorder traversal list bst.inorder() # creates an inorder traveral list bst.postorder() # creates a postorder traversal list key_string = "" bst.set_iteration_style("pre") for node in bst: key_string += str(node.get_key()) + " " 

bst[80] = 4 # Store the value 4 with the key 80 bst[80] # Retrieve the value associated with the key 80 

About

Red-black tree implementation in Python

Источник