توضیحات کامل درباره الگوریتم درخت قرمز-سیاه 🌳🔍

مقدمه

درخت قرمز-سیاه (Red-Black Tree) یک نوع درخت جستجوی دودویی است که به منظور حفظ تعادل درخت در زمان درج و حذف گره‌ها به کار می‌رود. این تعادل باعث می‌شود که عملیات جستجو، درج و حذف به صورت کارآمد و با پیچیدگی زمانی O(log n) انجام شود. در این متن، به توضیح دقیق‌تر و جزئیات بیشتری درباره این الگوریتم می‌پردازیم. 😊

ویژگی‌های درخت قرمز-سیاه

درخت قرمز-سیاه دارای ویژگی‌های زیر است:

1. هر گره یا قرمز است یا سیاه: این ویژگی باعث ساده‌تر شدن تشخیص و اصلاح نقض‌های احتمالی قوانین درخت می‌شود.
2. ریشه درخت همیشه سیاه است: این ویژگی تضمین می‌کند که مسیرهای از ریشه به برگ‌ها همیشه دارای حداقل یک گره سیاه هستند.
3. تمام برگ‌های نهایی (NIL) سیاه هستند: برگ‌های نهایی اشاره‌گرهایی هستند که به گره‌های واقعی متصل نیستند و به عنوان نگهبان عمل می‌کنند.
4. هر گره قرمز دو فرزند سیاه دارد: این ویژگی از وجود دو گره قرمز پشت سر هم جلوگیری می‌کند و به تعادل درخت کمک می‌کند.
5. هر مسیری از ریشه به یک برگ نهایی تعداد یکسانی گره سیاه دارد: این ویژگی تضمین می‌کند که مسیرها از لحاظ ارتفاع سیاه متعادل هستند.

عملیات اصلی در درخت قرمز-سیاه

1. درج (Insertion): هنگام درج یک گره جدید، ابتدا گره را به عنوان یک گره قرمز درج می‌کنیم. سپس، با بررسی و اصلاح نقض‌های احتمالی، تعادل درخت را حفظ می‌کنیم.
2. حذف (Deletion): حذف یک گره نیز ممکن است باعث نقض قوانین درخت شود. در این صورت، با استفاده از چرخش‌ها و تغییر رنگ‌ها، درخت را به حالت متعادل برمی‌گردانیم.
3. چرخش‌ها (Rotations): دو نوع چرخش در درخت قرمز-سیاه وجود دارد: چرخش به چپ و چرخش به راست. این چرخش‌ها برای اصلاح ساختار درخت و حفظ تعادل به کار می‌روند.

چرخش به چپ و راست

چرخش به چپ

چرخش به چپ یک عملیات است که یک گره را به سمت چپ و فرزند راست آن را به جای آن قرار می‌دهد. این عملیات برای جابجایی گره‌ها و اصلاح نقض‌های احتمالی به کار می‌رود.

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 is 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 is None:
self.root = y
elif x == x.parent.right:
x.parent.right = y
else:
x.parent.left = y
y.right = x
x.parent = y
مزایای استفاده از درخت قرمز-سیاه

1. زمان جستجوی بهینه: به دلیل تعادل درخت، زمان جستجو در درخت قرمز-سیاه به O(log n) محدود می‌شود.
2. درج و حذف کارآمد: عملیات درج و حذف در درخت قرمز-سیاه نیز با پیچیدگی زمانی O(log n) انجام می‌شود.
3. پیاده‌سازی آسان‌تر نسبت به سایر درخت‌های متعادل: الگوریتم درخت قرمز-سیاه نسبت به برخی از درخت‌های متعادل دیگر مانند درخت AVL، ساده‌تر پیاده‌سازی می‌شود.

نتیجه‌گیری

درخت قرمز-سیاه یک ابزار قدرتمند برای مدیریت داده‌ها و حفظ تعادل در عملیات‌های جستجو، درج و حذف است. این الگوریتم با ویژگی‌های خاص خود، عملکرد بهینه و پیاده‌سازی نسبتاً ساده‌ای دارد. امیدوارم این توضیحات به درک بهتر شما از درخت قرمز-سیاه کمک کرده باشد. 🌟

الگوریتم درخت قرمز_سیاه(red_black tree)🔴🌳⚫️

Minimalist Data Wrangling with #Python



برای دانلود کتابهای بیشتر در کانال عضو شوید
👇
🆔 @ProgrammingPDF

کانال اختصاصی پایتون👇
🆔 @Python4all_pro

import time

def countdown(t):
while (t >= 0):
mins, secs = divmod(t, 60)
hrs, mins = divmod(mins, 60)
timer = '{:02d} : {:02d} : {:02d}'.format(hrs, mins, secs)
print(timer, end="\r")
time.sleep(1)
t -= 1

print('\ntime is up')


t = input("Enter the time in seconds: ")

countdown(int(t))

تایمر❤️

import pygame, sys
import os
import random player_lives = 3
score = 0
fruits = ['melon', 'orange', 'pomegranate', 'guava', 'bomb']
WIDTH = 800
HEIGHT = 500
FPS = 12

pygame.init()
pygame.display.set_caption(‘FRUIT NINJA--DataFlair’)
gameDisplay = pygame.display.set_mode((WIDTH, HEIGHT))
clock = pygame.time.Clock()

WHITE = (255,255,255)
BLACK = (0,0,0)
RED = (255,0,0)
GREEN = (0,255,0)
BLUE = (0,0,255)

gameDisplay.fill((BLACK))
background = pygame.image.load('back.jpg')
font = pygame.font.Font(os.path.join(os.getcwd(), 'comic.ttf'), 32)
score_text = font.render('Score : ' + str(score), True, (255, 255, 255))
lives_icon = pygame.image.load('images/white_lives.png')

def generate_random_fruits(fruit):
fruit_path = "images/" + fruit + ".png"
data[fruit] = {
'img': pygame.image.load(fruit_path),
'x' : random.randint(100,500),
'y' : 800,
'speed_x': random.randint(-10,10),
'speed_y': random.randint(-80, -60),
'throw': False,
't': 0,
'hit': False,
}

if random.random() >= 0.75:
data[fruit]['throw'] = True
else:
data[fruit]['throw'] = False

data = {}
for fruit in fruits:
generate_random_fruits(fruit)

font_name = pygame.font.match_font('comic.ttf')

def draw_text(display, text, size, x, y):
font = pygame.font.Font(font_name, size)
text_surface = font.render(text, True, WHITE)
text_rect = text_surface.get_rect()
text_rect.midtop = (x, y)
gameDisplay.blit(text_surface, text_rect)

def draw_lives(display, x, y, lives, image) :
for i in range(lives) :
img = pygame.image.load(image)
img_rect = img.get_rect()
img_rect.x = int(x + 35 * i)
img_rect.y = y
display.blit(img, img_rect)

def hide_cross_lives(x, y):
gameDisplay.blit(pygame.image.load("images/red_lives.png"), (x, y))

def show_gameover_screen():
gameDisplay.blit(background, (0,0))
draw_text(gameDisplay, "FRUIT NINJA!", 64, WIDTH / 2, HEIGHT / 4)
if not game_over :
draw_text(gameDisplay,"Score : " + str(score), 40, WIDTH / 2, 250)


draw_text(gameDisplay, "Press a key to begin!", 24, WIDTH / 2, HEIGHT * 3 / 4)
pygame.display.flip()
waiting = True
while waiting:
clock.tick(FPS)
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
if event.type == pygame.KEYUP:
waiting = False

first_round = True
game_over = True
game_running = True
while game_running :
if game_over :
if first_round :
show_gameover_screen()
first_round = False
game_over = False
player_lives = 3
draw_lives(gameDisplay, 690, 5, player_lives, 'images/red_lives.png')
score = 0

for event in pygame.event.get():

if event.type == pygame.QUIT:
game_running = False

gameDisplay.blit(background, (0, 0))
gameDisplay.blit(score_text, (0, 0))
draw_lives(gameDisplay, 690, 5, player_lives, 'images/red_lives.png')

for key, value in data.items():
if value['throw']:
value['x'] += value['speed_x']
value['y'] += value['speed_y']
value['speed_y'] += (1 * value['t'])
value['t'] += 1

if value['y'] <= 800:
gameDisplay.blit(value['img'], (value['x'], value['y']))
else:
generate_random_fruits(key)

current_position = pygame.mouse.get_pos()

if not value['hit'] and current_position[0] > value['x'] and current_position[0] < value['x']+60 \
and current_position[1] > value['y'] and current_position[1] < value['y']+60:
if key == 'bomb':
player_lives -= 1
if player_lives == 0:
hide_cross_lives(690, 15)
elif player_lives == 1 :
hide_cross_lives(725, 15)
elif player_lives == 2 :
hide_cross_lives(760, 15)

if player_lives < 0 :
show_gameover_screen()
game_over = True

half_fruit_path = "images/explosion.png"
else:
half_fruit_path = "images/" + "half_" + key + ".png"

value['img'] = pygame.image.load(half_fruit_path)
value['speed_x'] += 10
if key != 'bomb' :
score += 1
score_text = font.render('Score : ' + str(score), True, (255, 255, 255))
value['hit'] = True
else:
generate_random_fruits(key)

pygame.display.update()
clock.tick(FPS)

pygame.quit()

بازی فروت نینجا ❤️☺️

🎮 آموزش ساخت بازی با pyGame

📝 زبان: فارسی
👤 مدرس: حسن امیری
🔗 منبع: تاپ لرن

📌 جلسه 18- ساخت بازی snake (بخش دوم)

🔆 ادامه ساخت بازی snake قسمت دومsnake

#ویدئو #فیلم #پایتون #گیم #پایگیم
#Video #Python #Game #Pygame
🐍 @PythonForever

وقتی ویروسی ک خودت نوشتی رو تو سیستم خودت باز میکنی😄😕

مصاحبه آقای جادی😄

عبارت with توی پایتون چیه و به چه دردی میخوره؟!

‏عبارت with برای مدیریت کردن خطا بدرد میخوره و میتونه کدمون رو تمیز تر و قابل خوندن تر بکنه

مدیریت فایل ها و... رو راحت تر میکنه مثلا تو کد بالا سه تیکه کد داریم که همشون یه کار انجام میدن اما سومی هم راحت تره هم مطمئن تر مثلا برخلاف دوتای اولی تو سومی نیازی نیست file.close رو بنویسید و خود with زحمتش رو برامون میکشه

تو کد بالا قسمت اول که اصلا مستعد باگه و ولش کنید قسمت دوم اوکیه ولی خب کدمون رو سخت میکنه ولی وقتی از with استفاده کی هم باگ نداری و هم کدت اسون تره در واقع سومی در نهایت به دومی ترجمه میشه

Python and Pygame Tutorial - Build Tetris! Full GameDev Course

📌 آموزش کتابخانه پای گیم پایتون

🕹 این‌ آموزش پروژه محور بوده و ساخت بازی معروف و جذاب Tetris را به طور کامل یاد میگیرید.

📝 زبان: فارسی
⏱ مدت: 1 ساعت و 40 دقیقه
💽 کیفیت بسیار بالا و کدهای خوانا

#ویدئو #پای_گیم #تتریس
#Video #Pygame #Tetris
🐍 @PythonForever

ساخت بازی Tetris 😁

🎮 آموزش ساخت بازی با pyGame

📝 زبان: فارسی
👤 مدرس: حسن امیری
🔗 منبع: تاپ لرن

📌 جلسه 19- ساخت بازی snake (بخش آخر)

🔆 بخش آخر ساخت بازی Snake

#ویدئو #فیلم #پایتون #گیم #پایگیم
#Video #Python #Game #Pygame
🐍 @PythonForever

https://t.iss.one/programmingpythons
این هم لینک گروه برنامه نویسان ❤️😊