Красно черное дерево java код

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.

An implementation of the red-black tree in Java.

License

ggabriel96/red_black_tree

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

An implementation of the red-black tree in Java. This code was forked from my repo «binary_search_tree».

Important: some of this code is based on Cormen’s Introduction to Algorithms and Open Data Structures code and content/info about trees. I’m really thankful for their effort on writing their books and this repository wouldn’t have all these methods if it weren’t for them.

• p , left and right are the parent node and left and right children, respectively. key is the information that node holds. The boolean red indicates if that node is red, obviously haha;
• The find() method searches for the node that contains the int passed as argument. If found, returns it. If not, returns the node that would be its parent if the searched item existed at that moment;
• The add() method uses find() to get to the place where the new node should be added. If a node already has the int passed as argument, it ignores it and doesn’t add a thing (so there are no duplicates). If the new node is smaller than the current being looked at, it goes to the left; if it’s greater, it goes to the right. At the end, calls addFix() so that it takes care of the potential violations of the red-black properties (this then calls rotateLeft() and rotateRight() when necessary);
• The remove() method uses transplant() (that performs a swap between nodes) and remFix() to remove the node that contains the int passed as argument from its tree. remFix() is analogous to addFix() ;
• The delete() method calls remove() on the root node while it’s not Tree.nil to completely delete the tree. Sets the root to null and also returns null so we don’t need another line to set our Tree object to null ;
• The min() and max() methods return the node that holds the minimum and maximum values of the tree rooted at the object calling it;
• The predecessor() and successor() methods return the predecessor ( max() of its left child) and successor ( min() of the right child) of the object calling it. If the respective child doesn’t exist, returns itself;
• The size() method returns the quantity of nodes in the (sub-)tree rooted at the object calling it;
• The depth() returns the length of the path from the object calling it to the root of the tree. If called from a Tree object, will return the height of the tree, as it doesn’t make sense to calculate the depth of the root (and the total depth of the tree is equal to its height);
• The height() returns the length of the path from the object calling it to the farthest descendant/leaf;
• And the inorderWalk() method prints the key of all nodes in ascending order, one per line;
• Finally, the graph() method outputs the tree in the GraphViz dot language format. The nodes are colored accordingly and it prints L and R for the left and right child.

About

An implementation of the red-black tree in Java.

Источник

Красно черное дерево java код

We follow a path from the root to the searched node (or to a NIL leaf). At each level, we perform a comparison. The effort for the comparison is constant. The search cost is thus proportional to the tree height. We denote by n the number of tree nodes. In the «Height of a Red-Black Tree» section, we have recognized that the longest path is at most twice as long as the shortest path. It follows that the height of the tree is bounded by O(log n). A formal proof is beyond the scope of this article. You can read the proof on Wikipedia. Thus, the time complexity for finding a node in a red-black tree is: O(log n)

Insertion Time

• Checking the color of the parent node
• Determination of the uncle node and checking its color
• Recoloring one up to three nodes
• Performing one or two rotations

Each of these operations has constant time, O(1), in itself. The total time for checking and repairing the tree is therefore also proportional to its height.

So the time complexity for inserting into a red-black tree is also: O(log n)

Deletion Time

Just as with insertion, we first search for the node to be deleted in time O(log n).

Also, the deletion cost is independent of the tree size, so it is constant O(1).

For checking the rules and repairing the tree, one or more of the following operations occur – at most once per level:

• Checking the color of the deleted node
• Determining the sibling and examining its color
• Checking the colors of the sibling’s children
• Recoloring the parent node
• Recoloring the sibling node and one of its children
• Performing one or two rotations

These operations also all have a constant complexity in themselves. Thus, the total effort for checking and restoring the rules after deleting a node is also proportional to the tree height.

So the time complexity for deleting from a red-black tree is also: O(log n)

Red-Black Tree Compared With Other Data Structures

The following sections describe the differences and the advantages and disadvantages of the red-black tree compared to alternative data structures.

Red-Black Tree vs. AVL Tree

The red-black tree, as well as the AVL tree, are self-balancing binary search trees.

In the red-black tree, the longest path to the root is at most twice as long as the shortest path to the root. On the other hand, in the AVL tree, the depth of no two subtrees differs by more than 1.

In the red-black tree, balance is maintained by the node colors, a set of rules, and by rotating and recoloring nodes. In the AVL tree, the heights of the subtrees are compared, and rotations are performed when necessary.

These differences in the characteristics of the two types of trees lead to the following differences in performance and memory requirements:

• Due to the more even balancing of the AVL tree, search in an AVL tree is usually faster. In terms of magnitude, however, both are in the range O(log n).
• For insertion and deletion, the time complexity in both trees is O(log n). In a direct comparison, however, the red-black tree is faster because it rebalances less frequently.
• Both trees require additional memory: the AVL tree one byte per node for the height of the subtree starting at a node; the red-black tree one bit per node for the color information. This rarely makes a difference in practice since a single bit usually occupies at least one byte.

If you expect many insert/delete operations, then you should use a red-black tree. If, on the other hand, you expect more search operations, then you should choose the AVL tree.

Red-Black Tree vs. Binary Search Tree

The red-black tree is a concrete implementation of a self-balancing binary search tree. So every red-black tree is also a binary search tree.

There are also other types of binary search trees, such as the AVL tree mentioned above – or trivial non-balanced implementations. Thus, not every binary search tree is also a red-black tree.

Summary

This tutorial taught you what a red-black tree is, which rules govern it and how these rules are evaluated and restored if necessary after inserting and deleting nodes. I also introduced you to a Java implementation that is as easy to understand as possible.

The JDK uses red-black trees in TreeMap (here is the source code on GitHub) and in bucket collisions in HashMap (here is the source code).

With this, I conclude the tutorial series on binary trees.

If I could help you better understand binary trees in general, binary search trees, AVL trees, and – in this article – red-black trees, I’m happy about a comment. Also, feel free to share the article using one of the share buttons at the end.

Do you want to be informed when the next article is published on HappyCoders.eu? Then click here to sign up for the HappyCoders newsletter.

Источник

Красно черное дерево java код

Learn Latest Tutorials

Preparation

Trending Technologies

B.Tech / MCA

Javatpoint Services

JavaTpoint offers too many high quality services. Mail us on h[email protected], to get more information about given services.

• Website Designing
• Website Development
• Java Development
• PHP Development
• WordPress
• Graphic Designing
• Logo
• Digital Marketing
• On Page and Off Page SEO
• PPC
• Content Development
• Corporate Training
• Classroom and Online Training
• Data Entry

Training For College Campus

JavaTpoint offers college campus training on Core Java, Advance Java, .Net, Android, Hadoop, PHP, Web Technology and Python. Please mail your requirement at [email protected].
Duration: 1 week to 2 week

Like/Subscribe us for latest updates or newsletter

Источник