| |
|
|
| |
# -*- coding: utf-8 -*-
#------------------------------------------------------------------------------+
# |
# КРАСНО-ЧЁРНОЕ ДЕРЕВО (Алгоритмы построения и анализ. - 2-е изд. Томас Кормен,|
# Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штейн; гл. 13 стр. 336) | |
# Открыто в 1972 году Рудольфом Байером(Wikipedia). |
# |
#------------------------------------------------------------------------------+
# сигнальные биты цвета
RED = True
BLACK = False
# Узел красно-чёрного дерева
class RBTreeNode:
color = left_child = right_child = parent = None
def __init__(self, key):
self.key = key
#------------------------------------------------------------------------------+
# |
# Теорема: |
# Бинарное дерево поиска является красно-чёрным деревом, если оно удволитворяет|
# следующим красно-чёрным свойствам: |
# 1. Каждый узел является красным или чёрным. |
# 2. Корень дерева является чёрным. |
# 3. Каждый лист дерева (nil) является чёрным. |
# 4. Если узел - красный, то оба его дочерних узла - чёрные. |
# 5. Для каждого узла все пути от него до листьев, являющихся потомками |
# данного узла, содержат одно и то же количество чёрных узлов. |
# |
#------------------------------------------------------------------------------+
# Красно-чёрное дерево
class RBTree:
def __init__(self):
# Для удобства работы с красно-черным деревом мы заменим все листья одним
# ограничивающим узлом, представляющим значение nil.
# В красно-черном дереве T ограничитель nil[T] пред-
# представляет собой объект с теми же полями, что и обычный узел дерева. Значение
# color этого узла равно black (черный), а все остальные поля могут иметь произ-
# произвольные значения. Все указатели на nil заменяются
# указателем на ограничитель nil[T].
self.nil = RBTreeNode(None)
self.nil.color = BLACK
self.root = self.nil
# повороты
def left_rotate(self, x):
y = x.right_child # устанавливаем y
# леввое поддерево y становится правым поддеревом x
x.right_child = y.left_child
if (y.left_child != self.nil):
y.left_child.parent = x
if (y != self.nil):
y.parent = x.parent # перенос родителя x в y
if (x.parent):
if (x == x.parent.left_child):
x.parent.left_child = y
else:
x.parent.right_child = y
else:
self.root = y
y.left_child = x
if (x != self.nil):
x.parent = y
def right_rotate(self, x):
y = x.left_child
x.left_child = y.right_child
if (y.right_child != self.nil):
y.right_child.parent = x
if (y != self.nil):
y.parent = x.parent
if (x.parent):
if (x == x.parent.right_child):
x.parent.right_child = y
else:
x.parent.left_child = y
else:
self.root = y
y.right_child = x
if (x != self.nil):
x.parent = y
def insert(self, key):
current = self.root
parent = None
while (current != self.nil):
if (key == current.key):
return "Ключ уже существует!"
paren = current
if (key < current.key):
parent = current.left_child
else:
parent = current.right_child
node = RBTreeNode(key) # новый узел
node.parent = parent
node.left_child = self.nil
node.right_child = self.nil
node.color = RED
node.key = key
if (parent):
if (key < parent.key):
parent.left_child = node
else:
parent.right_child = node
else:
self.root = node
self.insert_fixup(node)
# метод служащий для восстановления красно-чёрных свойств дерева
def insert_fixup(self, node):
while (node != self.root and node.parent.color == RED):
if (node.parent == node.parent.parent.left_child):
y = node.parent.parent.right_child
if (y.color == RED):
# дядя красный
node.parent.color = BLACK
y.color = BLACK
node.parent.parent.color = RED
node = node.parent.parent
else:
# дядя чёрный
if (node == node.parent.right_child):
node = node.parent
self.left_rotate(node)
node.parent.color = BLACK
node.parent.parent.color = RED
self.right_rotate(node)
else:
y = node.parent.parent.left_child
if (y.color == RED):
# дядя красный
node.parent.color = BLACK
y.color = BLACK
node.parent.parent.color = RED
node = node.parent.parent
else:
# дядя чёрный
if (node == node.parent.left_child):
node = node.parent
self.right_rotate(node)
node.parent.color = BLACK
node.parent.parent.color = RED
self.left_rotate(node)
self.root.color = BLACK
# вывод значений в порядке возрастания
def inorder_traverse(self, root):
if (root != self.nil):
self.inorder_traverse(root.left_child)
print root.key
self.inorder_traverse(root.right_child)
# *КОНЕЦ СЦЕНАРИЯ*
|
| |
| |
|
|
| |
|
|
| |
для: Ури Геллер
(20.04.2010 в 13:26)
| | | Хотяб скажи, что за язык... | |
| |
|
|
| |
|
|
| |
для: ~AquaZ~
(20.04.2010 в 19:31)
| | | Поручик Ржевский ,а в чём же соль?
А соли нет.......есть песок и дерьмо , песок и дерьмо...
-----------------------------------------------
из одноимённого анекдота
Тут нет вопроса :) | |
| |
|
|
| |
|
|
| |
для: ~AquaZ~
(20.04.2010 в 19:31)
| | | (C)python ver. 2.7a | |
| |
|
|
| |
|
|
| |
для: Ури Геллер
(20.04.2010 в 13:26)
| | | Может быть тут "...Клиффорд Штейн..."?) | |
| |
|
|
| |
|
|
| |
для: Ури Геллер
(20.04.2010 в 13:26)
| | | Что-то странно взял переписал всё с нуля на этот раз без самодеятельности и теперь работает вроде без ошибок
>>> t = RBTree()
>>> t.insert("Иванов И.И.", "223344")
>>> t.insert("Абрамов В.В.", "112233")
>>> t.inorderTraverse(t.root)
Абрамов В.В. => 112233
Иванов И.И. => 223344
>>> t.insert("Петров П.П.", "334455")
>>> t.insert("Сидоров Е.Н.", "445566")
>>> t.insert("Тихонов С.А.", "556677")
>>> t.inorderTraverse(t.root)
Абрамов В.В. => 112233
Иванов И.И. => 223344
Петров П.П. => 334455
Сидоров Е.Н. => 445566
Тихонов С.А. => 556677
>>> t.insert("Булгаков А.С.", "667788")
>>> t.inorderTraverse(t.root)
Абрамов В.В. => 112233
Булгаков А.С. => 667788
Иванов И.И. => 223344
Петров П.П. => 334455
Сидоров Е.Н. => 445566
Тихонов С.А. => 556677
>>>
|
| |
| |
|
|
| |
|
|
| |
для: Ури Геллер
(20.04.2010 в 13:26)
| | | Что почитал про это красно черное дерево время поиска log10(x), т.е. для миллиона записей по ходу нужно 6 итераций. Главный вопрос где это используется? | |
| |
|
|
