Перейти к содержимому

Что такое красно черное дерево java

  • автор:

1123. Data Structure — Red Black Tree — draft RBT

Introduce red black tree and its properties.

1. Problems with Binary Search Tree

image

For Binary Search Tree, although the average time complexity for the search, insertion and deletion are all $O(\log<>n)$, where n is the number of nodes in the tree, the time complexity becomes to $O(n)$ in worst case — BST is not balanced.

We can guarantee $O(\log<>n)$ time for all three operations by using a balanced tree — a tree that always has height log(n) .

2. Red Black Tree

2.1 Definition of RBT

A red black tree is a binary search tree with following four properties.

  • Color property : Each node has a color (red or black) associated with it (in addition to its key, left and right children).
  • Root property : The root of the red-black tree is black.
  • Red property : The children of a red node are black.
  • Black property : For each node with at least one null child, the number of black nodes on the path from the root to the null child is the same.

Examples of Red Black Tree. imageThe following examples are NOT Red Black Tree. image

1.2 Time Complexity

  • Search — $O(\log<>n)$
  • Insertion — $O(\log<>n)$
  • Deletion — $O(\log<>n)$

1.3 Space Complexity

2. Search

3. Insertion

The goal of the insert operation is to insert key x into tree T , and keep T’s red-black tree properties. We use Recoloring and Rotation to achieve that.

There are several cases when inserting a new key to RBT. We will go through all of them below.

3.1 Special Case: Empty Tree

image

A special case is required for an empty tree. If T is empty, replace it with a single black node containing x. This ensures that the root property is satisfied.

3.2 Non-empty Tree

If T is a non-empty tree, then we do the following:

  • 1) Use the BST insert algorithm to add x to the tree
  • 2) color the node containing x to red
  • 3) restore red-black tree properties (if necessary)

For step 3, what we need to do depends on the color of x’s parent. Let p be x’s parent. We need to consider two cases:

  • Case 1: x’s parent p is black. The insertion of x does not result in the red property being violated, so there’s nothing more to do.
  • Case 2: K’s parent p is red .
    For easy understanding, we have the following naming convention. imageIf p is red, then p now has a red child, which violates the red property. Note that p’s parent, g , must be black. In order to handle this double-red situation, we will need to consider the color of g’s other child, that is, p’s sibling, s . (Note that s might be null, i.e., g only has one child and that child is p.) We have two cases:
    • Case 2a: p ’s sibling s is red .
      Perform recoloring of p , s and g : the color of p and s is changed to black and the color of g is changed to red (unless g is the root, in which case we leave g black to preserve the root property). imageRecoloring does not affect the black property of a tree: the number of black nodes on any path that goes through p and g is unchanged when p and g switch colors (similarly for s and g ). But, the recoloring may have introduced a double-red situation between g and g ’s parent. If that is the case, then we recursively handle the double-red situation starting at g and g ’s parent (instead of x and x ’s parent).
    • Case 2b: p ’s sibling s is black or null.
      If s is black or null, then we will do a tri-node restructuring of x , p and g . There are four subcases for the relative ordering of x, p and g. The way a restructuring is done for each of the possibilities is shown below.
      • i) Left Left Case (p is left child of g and x is left child of p) image
      • ii) Left Right Case (p is left child of g and x is right child of p) image
      • iii) Right Right Case (Mirror of case i) image
      • iv) Right Left Case (Mirror of case ii) image

      Что такое красно черное дерево java

      We can determine the cost of searching, inserting, and deleting a node in the binary tree as follows:

      Search Time

      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

      When inserting, we first perform a search. We have just determined the search cost as O(log n).

      Next, we insert a node. The cost of this is constant regardless of the tree size, so O(1).

      Then we check the red-black rules and restore them if necessary. We do this starting at the inserted node and ascending to the root. At each level, we perform one or more of the following operations:

      • 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.

      Colour it please as Red-Black Trees

      Aleksandra Sikora

      We have something like binary search trees. Really simple data structure. But we have also plenty of different tree-like structures: splays, AVLs, red-black trees and so on. Why is that? Why are BSTs not enough? Namely, the reason is that they can grow uneven beyond our control. So, in the worst case, the time complexity for search may be linear, which by and large make no point for using tree data structure. For sure we won’t be satisfied with the BST looking like that:

      And any attempts for preventing it may be expensive and unpractical. Only imagine how great it would be to have a tree with the assurance that its height remains as O(log n) after any sequence of deletions and insertions. That’s why for time complexity satisfaction we need something that takes care of itself and makes itself evenly distributed. Let me introduce Red-Black Trees.

      In Red-Black Tree, we assume that the leaves don’t store any additional information besides that they’re leaves. And from property number 2 they are all black. An example of Red-Black-Tree:

      The height of the Red-Black Tree

      As mentioned earlier what we care the most about in trees data structures is the height of the tree. The bigger it is the longer search query is going to take. So to ascertain if these two-colour trees are really a good idea we want to state the maximum height that a tree can obtain.

      In case you wonder why is that there comes the explanation. But let’s enter some useful fact beforehand.

      The maximum height of the tree is just the number of nodes in the longest path from the tree root to the leaf. But from property number 4 we know that each path from the root to the leaf must contain the same number of black nodes. That implies that the number of the black nodes is restricted by the length of the shortest path from the root to the leaf (this means that the shortest path contain only black nodes).

      Assume the shortest path from the root to the leaf has height k. Then we have:

      • There are k+1 nodes in the path at height k
      • There is a complete binary subtree of height k (this is the shortest path, right?)

      Let’s look a the example for the shortest path at height 2:

      Suppose this complete binary subtree has n nodes, then using the fact that n=2^(k+1)−1, the number of nodes in the path from the root to leaf is: k+1= log ⁡(n+1) and this is the maximum number of black nodes in any path from the root to leaf.

      Okay, that’s something but that’s not what we wanted yet. We need to establish the number of nodes in the longest path from the root to leaf. We know that this path will contain log(n+1) black nodes, but how many red ones? From property number 3 we have that a red node must have black node children. This restricts the maximum number of red nodes to being placed between the black nodes:

      So the length of the longest path is:

      max number of black nodes + max number of red nodes = 2log(n+1)\

      Insertion

      In Red-Black Trees after inserting an element two types of actions are used to assure balancing and bring back violated properties:

      The insert strategy consists of two steps. The first is inserting an element like in the ordinary binary search tree, marked as red. It may violate property number 3, which tells that each red node must have black node children. That’s when the second step comes, in which we need to use the previously introduced actions (recolouring and rotations). Here we have to check for the colour of the inserted node’s uncle. Take a look at the picture describing a relationships between nodes in the tree.

      Okay, so suppose we inserted a node X, which violated Red-Black Tree properties. Time for recover. We have four possible scenarios:

      I. Inserted element X is a root. As we insert new elements marked as red and from the property number 2 we know that the root must be black, the solution here is to change colour of X from red to black.

      II. X’s uncle is red. The solution for this case regards changing the colours of X’s father and uncle to black and X’s grandfather to red. Then it calls recovering procedure on X’s grandfather (If X would be a child of C the solution would be analogous).

      III. X’s uncle is black (triangle). Now we are performing a single rotation on X’s father and as the result we’re going to obtain case IV. After rotation we call recovering procedure on X’s father (the one before rotation — node C in the picture below).

      IV. X’s uncle is black (line). This case solution assume two steps. The first is changing the colours of X’s grandfather to red, and X’s father to black. Then in the second step we perform rotation of X’s grandfather. After that we call recovering procedure on X’s father.

      Deletion

      Like Insertion, recolouring and rotations are used to maintain the Red-Black properties. In insert operation, we needed to check colour of uncle to decide the appropriate case. In delete operation, on the other hand, we check colour of sibling. Another difference between insert and delete operations is the property which is violated afterward. In insertion, it was property number 3 (red nodes have black children). In deletion, the main violated property is property number 4 (the one about the same number of black nodes in any path from some node to leaf). Deletion of a black node may cause deletion of a black node from some root-to-leaf path.

      The deletion strategy comes that way: standard BST delete and Red-Black properties recovering. There is also something like double black that needs some explanation. So, when a black node is deleted and replaced by a black child, the child is marked as double black as we want to pass deleted black colour. The main task then becomes to convert this double black to single black.

      Before we start analysing Red-Black properties recovery, let’s recall deleting a node from binary search tree. There are three possible cases for deleting node X:

      I. X is a leaf. It’s the simplest one. We just need to remove it.

      II. X has one child. More complicated. We need to copy the child to the X’s father and delete the child.

      III. X has two children. A little bit more complicated. Now we want to find inorder successor of the node (the smallest node in the right subtree) and then copy its contents to the X’s father recursively call delete operation for X’s successor in X’s right subtree.

      Now we can go to recovering part. Let X be the node to be deleted and Y be the node that replaces X in the tree. Like in post insert recovery we have some cases. Two, namely. And a lot of subcases…

      I. Either X or Y is red. They can’t be both red as there cannot be two consecutive red nodes in Red-Black tree. We mark the replaced child as black, which make no change in number of black nodes in any path that contain newly marked node.

      II. Both X and Y are black. Firstly we need to colour Y as double black. Now our task reduces to convert this double black to single black. Note that If X is leaf, then Y is NULL and colour of NULL is considered as black. So the deletion of a black leaf also causes a double black. So while we still have a double black on some node and that node is not the root (in case of root we can just remove the double black) we are going to perform recovery on following subcases:

      a) Sibling S is black and at least one of sibling’s children is red — we need to perform rotation on the sibling. Let R be the red child of S. This subcase can be divided in four subsubcases depending upon positions of S and R. In each of them some actions will be performed, which I’m going to describe on pictures.

      a.1 Right-right case: S is right child of its parent and R is right child of S.

      a.2 Right-left Case: S is right child of its parent and R is left child of S.

      a.3 Left-left case: S is left child of its parent and R is left child of S. The actions taken in that case are analogous to the right-right case.

      a.4 Left-right case: S is left child of its parent and R is right child of S. The actions taken in that case are analogous to the right-left case.

      b) Sibling is black and its both children are black. The solution is to perform recolouring, and then recur for the parent if parent is black. If parent was red, then we don’t need to recur for it, we can simply make it black (red + double black = single black).

      c) Sibling is red: Here we are going to perform a rotation to move X’s sibling up and recolour X’s sibling and parent. This mainly converts the tree to black sibling case (by rotation) and leads to case a) or b). This divided in two subsubcases.

      c.1 Right case: S is right child of its parent. Here we left rotate the X’s father.

      c.2 Left case: S is left child of its parent. This is mirror of right right case shown in picture above.

      Деревья, красно-черные деревья

      — Нашел тут свои старые записи и приготовил для тебя немного интересного материала. Думаю, тебе будет интересно послушать.

      — Давай. Ты всегда находишь что-то интересное, которое потом становится очень полезным.

      — Ладно. Сегодня я хочу тебе рассказать про деревья, поэтому начну я с графов.

      Граф – это система, состоящая из точек и линий, которые их соединяют. Точки называются вершинами графа, а линии – ребрами графа. Пример:

      Деревья, красно-черные деревья - 1

      Граф очень удобно использовать как математическую модель для различных реальных процессов и задач. Для графов придумано очень много различных задач и алгоритмов, поэтому их довольно часто используют.

      Например, вершины – это города, а ребра – это дороги. Тогда поиск самой короткой дороги между городами превращается в задачу «дан граф, найти кратчайший путь между двумя вершинами».

      Но не всегда путь из А в Б, занимает столько же, как и путь из Б в А. Поэтому иногда желательно бы иметь две различные линии. Для этого линии (ребра графа) заменяют на стрелки. Т.е. граф может содержать две стрелки: одну из А в Б, а вторую из Б в А.

      Если в графе используются стрелки, его называют ориентированным графом, если просто линии – неориентированным графом.

      У каждой вершины может быть свое количество ребер. Также вершина может не иметь ребер вообще. Или наоборот, быть соединена ребрами со всеми остальными вершинами. Если в графе каждая вершина соединена ребром с каждой – такой граф называют полным.

      Если в графе по ребрам можно добраться до любой вершины, такой граф называют связным. Граф состоящий из трех отдельных вершин, без ребер вообще, это все равно граф, но несвязный.

      Деревья, красно-черные деревья - 2

      Чтобы соединить в связный граф N вершин, надо минимум N-1 ребер. Такой граф называется деревом.

      При этом обычно одну вершину выбирают корнем дерева, а остальные объявляют ее ветвями. Ветви дерева, которые не имеют своих ветвей, называют листьями . Пример:

      Деревья, красно-черные деревья - 3

      Дерево называют бинарным, если у каждого элемента дерева не более двух потомков. Т.е. их может быть 0, 1 или 2. Выше справа как раз изображено бинарное дерево.

      Дерево называют полным бинарным деревом, когда у каждой ветви 2 потомка, а все листья (без потомков) находятся в одном ряду.

      Деревья, красно-черные деревья - 4

      — А зачем нужны такие деревья?

      — О, деревья применяются много где. Бинарные деревья поиска так вообще являются отсортированной структурой данных.

      — Да очень просто. В каждой вершине мы храним некоторое значение. А для каждого элемента вводится правило – значение, которое хранится в потомке справа, больше, чем значение в вершине, а значение, которое хранится в потомке слева – меньше чем значение в вершине. Такое упорядочивание позволяет очень быстро находить нужные элементы в дереве.

      — А можно поподробнее.

      — Сортировка элементов дерева обычно выполняется добавлением. Вот, допустим, у нас есть 7 элементов: 13, 5, 4, 16, 8, 11, 10

      Вот как добавляются элементы в такое дерево.

      Деревья, красно-черные деревья - 5

      Если мы ищем, например, число 7 в таком дереве, то поиск будет проходить так:

      0) Начинаем с корня.

      1а) Число 7 равно 13? Нет

      1б) Число 7 больше 13? Нет, тогда идем в левое поддерево.

      2а) Чисто 7 равно 5? Нет.

      2б) Число 7 больше 5? Да, тогда идем в правое поддерево.

      3а) Число 7 равно 8? Нет

      3б) Число 7 больше 8? Нет, тогда идем в левое поддерево.

      4а) Левого поддерева нет, значит, числа 7 в дереве нет.

      — Ага. Т.е. нам надо проверять только вершины на пути от корня до предполагаемого места нужного числа. Да, это действительно быстро.

      — Еще бы, если дерево сбалансировано, то для миллиона элементов понадобится обход всего около 20 вершин.

      — Да, согласен, что это не много.

      А что значит – сбалансированное дерево?

      — Дерево без «перекосов» — без длинных ветвей. Ведь если бы мы подавали элементы при строительстве дерева в уже отсортированном порядке, у нас бы получилось длинное-предлинное дерево, состоящее из одной ветви.

      — Гм. Действительно. И как тогда быть?

      — Как ты уже, наверное, догадался, самым эффективным будет дерево, которое имеет ветви примерно равной длины. Тогда при каждом сравнении отбрасывается наибольшая часть поддерева из оставшегося.

      — Т.е. нужно переделать дерево?

      — Ага. Его нужно «сбалансировать» — сделать максимально похожим на полное бинарное дерево.

      Для решения этой проблемы были придуманы самобалансирующиеся деревья. Когда после добавления элемента в дереве возникает перекос, оно немного меняет порядок элементов, и все становится ок. Пример балансировки:

      Деревья, красно-черные деревья - 6

      Одними из таких деревьев есть так называемые « красно -черные деревья».

      — А почему их называют красно-черные?

      — Их создатель придумал красить все вершины в два цвета. Один цвет – красный, второй – черный. И разные вершины подчиняются разным правилам. На этом и строится вся балансировка.

      Деревья, красно-черные деревья - 7

      — А что это за принципы?

      — 1) Красная вершина не может быть сыном красной вершины.

      2) Черная глубина любого листа одинакова (черной глубиной называют количество черных вершин на пути из корня).

      3) Корень дерева черный.

      Я не буду рассказывать тебе, как это работает, у тебя уже небось голова кипит.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *