ホームページ バックエンド開発 Python チュートリアル 赤黒木の原理と特性、および Python でのコード実装

赤黒木の原理と特性、および Python でのコード実装

Jan 23, 2024 am 08:42 AM

赤黒ツリーは、B ツリーと同様に、バランスのとれた二分探索ツリーです。赤黒の木の各節は赤または黒に色付けされていますが、木の根元は黒く、根元の葉も黒です。また、赤黒ツリー内の任意のノードから葉への直接パスには、同じ数の黒いノードが含まれることに注意してください。

红黑树的原理和特性 Python代码实现红黑树

#赤黒の木はどのようにして自己平衡特性を維持しているのでしょうか?

赤と黒のツリー ノードの色に関する制限により、ルートからリーフまでの最長パスが最短パスの 2 倍を超えないようになります。

赤黒ツリーでは、新しく挿入されたノードが常に赤くなるのはなぜですか?

これは、赤色のノードを挿入しても、赤黒ツリーの黒色ノードの数量プロパティに違反しないためです。また、新しい赤いノードが元の赤いノードに挿入された場合でも、この問題の解決は黒いノードの違反によって引き起こされる問題よりも簡単です。

赤黒ツリーの Python コード実装

import sys
# 创建节点
class Node():
    def __init__(self, item):
        self.item = item
        self.parent = None
        self.left = None
        self.right = None
        self.color = 1

class RedBlackTree():
    def __init__(self):
        self.TNULL = Node(0)
        self.TNULL.color = 0
        self.TNULL.left = None
        self.TNULL.right = None
        self.root = self.TNULL

    # 前序
    def pre_order_helper(self, node):
        if node != TNULL:
            sys.stdout.write(node.item + " ")
            self.pre_order_helper(node.left)
            self.pre_order_helper(node.right)

    # 中序
    def in_order_helper(self, node):
        if node != TNULL:
            self.in_order_helper(node.left)
            sys.stdout.write(node.item + " ")
            self.in_order_helper(node.right)

# 后根
    def post_order_helper(self, node):
        if node != TNULL:
            self.post_order_helper(node.left)
            self.post_order_helper(node.right)
            sys.stdout.write(node.item + " ")

    # 搜索树
    def search_tree_helper(self, node, key):
        if node == TNULL or key == node.item:
            return node

        if key < node.item:
            return self.search_tree_helper(node.left, key)
        return self.search_tree_helper(node.right, key)

    # 删除后平衡树
    def delete_fix(self, x):
        while x != self.root and x.color == 0:
            if x == x.parent.left:
                s = x.parent.right
                if s.color == 1:
                    s.color = 0
                    x.parent.color = 1
                    self.left_rotate(x.parent)
                    s = x.parent.right

                if s.left.color == 0 and s.right.color == 0:
                    s.color = 1
                    x = x.parent
                else:
                    if s.right.color == 0:
                        s.left.color = 0
                        s.color = 1
                        self.right_rotate(s)
                        s = x.parent.right

                    s.color = x.parent.color
                    x.parent.color = 0
                    s.right.color = 0
                    self.left_rotate(x.parent)
                    x = self.root
            else:
                s = x.parent.left
                if s.color == 1:
                    s.color = 0
                    x.parent.color = 1
                    self.right_rotate(x.parent)
                    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:
                        s.right.color = 0
                        s.color = 1
                        self.left_rotate(s)
                        s = x.parent.left

                    s.color = x.parent.color
                    x.parent.color = 0
                    s.left.color = 0
                    self.right_rotate(x.parent)
                    x = self.root
        x.color = 0

    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

    # 节点删除
    def delete_node_helper(self, node, key):
        z = self.TNULL
        while node != self.TNULL:
            if node.item == key:
                z = node

            if node.item <= key:
                node = node.right
            else:
                node = node.left

        if z == self.TNULL:
            print("Cannot find key in the tree")
            return

        y = z
        y_original_color = y.color
        if z.left == self.TNULL:
            x = z.right
            self.__rb_transplant(z, z.right)
        elif (z.right == self.TNULL):
            x = z.left
            self.__rb_transplant(z, z.left)
        else:
            y = self.minimum(z.right)
            y_original_color = y.color
            x = y.right
            if y.parent == z:
                x.parent = 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:
            self.delete_fix(x)

    # 插入后平衡树
    def fix_insert(self, k):
        while k.parent.color == 1:
            if k.parent == k.parent.parent.right:
                u = k.parent.parent.left
                if u.color == 1:
                    u.color = 0
                    k.parent.color = 0
                    k.parent.parent.color = 1
                    k = k.parent.parent
                else:
                    if k == k.parent.left:
                        k = k.parent
                        self.right_rotate(k)
                    k.parent.color = 0
                    k.parent.parent.color = 1
                    self.left_rotate(k.parent.parent)
            else:
                u = k.parent.parent.right

                if u.color == 1:
                    u.color = 0
                    k.parent.color = 0
                    k.parent.parent.color = 1
                    k = k.parent.parent
                else:
                    if k == k.parent.right:
                        k = k.parent
                        self.left_rotate(k)
                    k.parent.color = 0
                    k.parent.parent.color = 1
                    self.right_rotate(k.parent.parent)
            if k == self.root:
                break
        self.root.color = 0

    # Printing the tree
    def __print_helper(self, node, indent, last):
        if node != self.TNULL:
            sys.stdout.write(indent)
            if last:
                sys.stdout.write("R----")
                indent += "     "
            else:
                sys.stdout.write("L----")
                indent += "|    "

            s_color = "RED" if node.color == 1 else "BLACK"
            print(str(node.item) + "(" + s_color + ")")
            self.__print_helper(node.left, indent, False)
            self.__print_helper(node.right, indent, True)

    def preorder(self):
        self.pre_order_helper(self.root)

    def inorder(self):
        self.in_order_helper(self.root)

    def postorder(self):
        self.post_order_helper(self.root)

    def searchTree(self, k):
        return self.search_tree_helper(self.root, k)

    def minimum(self, node):
        while node.left != self.TNULL:
            node = node.left
        return node

    def maximum(self, node):
        while node.right != self.TNULL:
            node = node.right
        return node

    def successor(self, x):
        if x.right != self.TNULL:
            return self.minimum(x.right)

        y = x.parent
        while y != self.TNULL and x == y.right:
            x = y
            y = y.parent
        return y

    def predecessor(self,  x):
        if (x.left != self.TNULL):
            return self.maximum(x.left)

        y = x.parent
        while y != self.TNULL and x == y.left:
            x = y
            y = y.parent

        return y

    def left_rotate(self, x):
        y = x.right
        x.right = y.left
        if y.left != self.TNULL:
            y.left.parent = x

        y.parent = x.parent
        if x.parent == None:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x
        x.parent = y

    def right_rotate(self, x):
        y = x.left
        x.left = y.right
        if y.right != self.TNULL:
            y.right.parent = x

        y.parent = x.parent
        if x.parent == None:
            self.root = y
        elif x == x.parent.right:
            x.parent.right = y
        else:
            x.parent.left = y
        y.right = x
        x.parent = y

    def insert(self, key):
        node = Node(key)
        node.parent = None
        node.item = key
        node.left = self.TNULL
        node.right = self.TNULL
        node.color = 1

        y = None
        x = self.root

        while x != self.TNULL:
            y = x
            if node.item < x.item:
                x = x.left
            else:
                x = x.right

        node.parent = y
        if y == None:
            self.root = node
        elif node.item < y.item:
            y.left = node
        else:
            y.right = node

        if node.parent == None:
            node.color = 0
            return

        if node.parent.parent == None:
            return

        self.fix_insert(node)

    def get_root(self):
        return self.root

    def delete_node(self, item):
        self.delete_node_helper(self.root, item)

    def print_tree(self):
        self.__print_helper(self.root, "", True)


if __name__ == "__main__":
    bst = RedBlackTree()

    bst.insert(55)
    bst.insert(40)
    bst.insert(65)
    bst.insert(60)
    bst.insert(75)
    bst.insert(57)

    bst.print_tree()

    print("\nAfter deleting an element")
    bst.delete_node(40)
    bst.print_tree()
ログイン後にコピー

以上が赤黒木の原理と特性、および Python でのコード実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

Pythonを使用してテキストファイルのZIPF配布を見つける方法 Pythonを使用してテキストファイルのZIPF配布を見つける方法 Mar 05, 2025 am 09:58 AM

このチュートリアルでは、Pythonを使用してZIPFの法則の統計的概念を処理する方法を示し、法律の処理時にPythonの読み取りおよび並べ替えの効率性を示します。 ZIPF分布という用語が何を意味するのか疑問に思うかもしれません。この用語を理解するには、まずZIPFの法律を定義する必要があります。心配しないでください、私は指示を簡素化しようとします。 ZIPFの法則 ZIPFの法則は単に意味します。大きな自然言語のコーパスでは、最も頻繁に発生する単語は、2番目の頻繁な単語のほぼ2倍の頻度で表示されます。 例を見てみましょう。アメリカ英語の茶色のコーパスを見ると、最も頻繁な言葉は「thであることに気付くでしょう。

HTMLを解析するために美しいスープを使用するにはどうすればよいですか? HTMLを解析するために美しいスープを使用するにはどうすればよいですか? Mar 10, 2025 pm 06:54 PM

この記事では、Pythonライブラリである美しいスープを使用してHTMLを解析する方法について説明します。 find()、find_all()、select()、およびget_text()などの一般的な方法は、データ抽出、多様なHTML構造とエラーの処理、および代替案(SEL

Pythonでの画像フィルタリング Pythonでの画像フィルタリング Mar 03, 2025 am 09:44 AM

ノイズの多い画像を扱うことは、特に携帯電話や低解像度のカメラの写真でよくある問題です。 このチュートリアルでは、OpenCVを使用してPythonの画像フィルタリング手法を調査して、この問題に取り組みます。 画像フィルタリング:強力なツール 画像フィルター

Pythonを使用してPDFドキュメントの操作方法 Pythonを使用してPDFドキュメントの操作方法 Mar 02, 2025 am 09:54 AM

PDFファイルは、クロスプラットフォームの互換性に人気があり、オペレーティングシステム、読み取りデバイス、ソフトウェア間でコンテンツとレイアウトが一貫しています。ただし、Python Plansing Plain Text Filesとは異なり、PDFファイルは、より複雑な構造を持つバイナリファイルであり、フォント、色、画像などの要素を含んでいます。 幸いなことに、Pythonの外部モジュールでPDFファイルを処理することは難しくありません。この記事では、PYPDF2モジュールを使用して、PDFファイルを開き、ページを印刷し、テキストを抽出する方法を示します。 PDFファイルの作成と編集については、私からの別のチュートリアルを参照してください。 準備 コアは、外部モジュールPYPDF2を使用することにあります。まず、PIPを使用してインストールします。 ピップはpです

DjangoアプリケーションでRedisを使用してキャッシュする方法 DjangoアプリケーションでRedisを使用してキャッシュする方法 Mar 02, 2025 am 10:10 AM

このチュートリアルでは、Redisキャッシングを活用して、特にDjangoフレームワーク内でPythonアプリケーションのパフォーマンスを向上させる方法を示しています。 Redisのインストール、Django構成、およびパフォーマンスの比較をカバーして、Beneを強調します

TensorflowまたはPytorchで深い学習を実行する方法は? TensorflowまたはPytorchで深い学習を実行する方法は? Mar 10, 2025 pm 06:52 PM

この記事では、深い学習のためにTensorflowとPytorchを比較しています。 関連する手順、データの準備、モデルの構築、トレーニング、評価、展開について詳しく説明しています。 特に計算グラップに関して、フレームワーク間の重要な違い

Pythonの並列および同時プログラミングの紹介 Pythonの並列および同時プログラミングの紹介 Mar 03, 2025 am 10:32 AM

データサイエンスと処理のお気に入りであるPythonは、高性能コンピューティングのための豊富なエコシステムを提供します。ただし、Pythonの並列プログラミングは、独自の課題を提示します。このチュートリアルでは、これらの課題を調査し、グローバルな承認に焦点を当てています

Pythonで独自のデータ構造を実装する方法 Pythonで独自のデータ構造を実装する方法 Mar 03, 2025 am 09:28 AM

このチュートリアルでは、Python 3にカスタムパイプラインデータ構造を作成し、機能を強化するためにクラスとオペレーターのオーバーロードを活用していることを示しています。 パイプラインの柔軟性は、一連の機能をデータセットに適用する能力にあります。

See all articles