Red-Black Trees and BST Properties

Red-black trees are balanced BSTs with specific properties like color rules and black node count. They ensure O(logn) height for balanced trees. Learn about the characteristics, insertion methods, and rotations in red-black trees compared to BSTs.

• Red-Black Trees
• Binary Search Trees
• Balanced Trees
• Data Structures
• Tree Algorithms

nbeme Follow

Uploaded on Sep 17, 2024 | 1 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Redblacktrees

2. Define the red-black tree properties Describe and implement rotations Implement red-black tree insertion We will skip red-black tree deletion October 2004 John Edgar 2

3. Items can be inserted in and removed from BSTs in O(height) time So what is the height of a BST? If the tree is balanced: O(logn) If the tree is very unbalanced: O(n) 43 balanced BST 24 61 height = O(logn) 12 37 61 12 unbalanced BST 43 height = O(n) 37 24 October 2004 John Edgar 3

4. Define a balanced binary tree as one where There is no path from the root to a leaf* that is more than twice as long as any other such path The height of such a tree is O(logn) Guaranteeing that a BST is balanced requires either A more complex structure (2-3 and 2-3-4 trees) or More complex insertion and deletion algorithms (red- black trees) *definition of leaf on next slide October 2004 John Edgar 4

5. A red-black tree is a balanced BST Each node has an extra colour field which is red or black Usually represented as a boolean isBlack Nodes have an extra pointer to their parent Imagine that empty nodes are added so that every real node has two children They are imaginarynodes so are not allocated space The imaginary nodes are always coloured black October 2004 John Edgar 5

6. 1. Every node is either red or black 2. Every leaf is black This refers to the imaginaryleaves i.e. every null child of a node is considered to be a black leaf 3. If a node is red both its children must be black 4. Every path from a node to a leaf contains the same number of black nodes 5. The root is black (mainly for convenience) October 2004 John Edgar 6

7. Perfect trees are perfectly balanced But they are inflexible, can only store 1, 3, 7, nodes Black nodes form a perfect tree Red nodes allow flexibility Draw some pictures October 2004 John Edgar 7

8. The black height of a node, bh(v), is the number of black nodes on a path from v to a leaf Without counting v itself Because of property 4 every path from a node to a leaf contains the same number of black nodes The height of a node, h(v), is the number of nodes on the longest path from v to a leaf Without counting v itself From property 3a red node s children must be black So h(v) 2(bh(v)) October 2004 John Edgar 8

9. It can be shown that a tree with the red-black structure is balanced A balanced tree has no path from the root to a leaf that is more than twice as long as any other such path Assume that a tree has n internal nodes An internal node is a non-leaf node, and the leaf nodes are imaginarynodes A red-black tree has 2bh 1 internal (real) nodes Can be proven by induction (e.g. Algorithms, Cormen et al.) October 2004 John Edgar 9

10. Claim: a red-black tree has height, h 2*log(n+1) n 2bh 1 (see above) bh h / 2 (red nodes must have black children) n 2h/2 1 (replace bh with h) log(n + 1) h / 2 (add 1, log2 of both sides) h 2*log(n + 1) (multiply both sides by 2) October 2004 John Edgar 10

12. An item must be inserted into a red-black tree at the correct position The shape of a tree is determined by The values of the items inserted into the tree The order in which those values are inserted This suggests that there is more than one tree (shape) that can contain the same values A tree s shape can be altered by rotation while still preserving the bst property Note: only applies to bst with no duplicate keys! October 2004 John Edgar 12

13. Left rotate(x) z x x y z D y C A B C D A B October 2004 John Edgar 13

14. Right rotate(z) z x x y z D y C A B C D A B October 2004 John Edgar 14

15. Left rotation of 32, call the node x Assign a pointer to x's R child 47 32 81 temp 13 40 37 44 October 2004 John Edgar 15

16. Left rotation of 32, call the node x Assign a pointer to x's R child 47 Make temp s L child x s R child 32 81 Detach temp s L child temp 13 40 37 44 October 2004 John Edgar 16

17. Left rotation of 32, call the node x Assign a pointer to x's R child 47 Make temp s L child x s R child 32 81 Detach temp s L child Make x temp's L child temp Make temp x's parent's child 13 40 37 44 October 2004 John Edgar 17

18. Left rotation of 32, call the node x 47 40 81 32 44 13 37 October 2004 John Edgar 18

19. Right rotation of 47, call the node x Assign a pointer to x's L child 47 32 81 temp 13 40 7 29 37 October 2004 John Edgar 19

20. Right rotation of 47, call the node x Assign a pointer to x's L child 47 Make temp s R child x s L child 32 81 Detach temp s R child temp 13 40 7 29 37 October 2004 John Edgar 20

21. Right rotation of 47, call the node x Assign a pointer to x's L child 47 Make temp s R child x s L child 32 81 Detach temp s R child temp Make x temp's L child 13 40 7 29 37 October 2004 John Edgar 21

22. Right rotation of 47, call the node x Assign a pointer to x's L child 32 Make temp s R child x s L child 13 47 Detach temp s R child temp Make x temp's L child Make temp the new root 7 81 29 40 37 October 2004 John Edgar 22

24. Insert as for a binary search tree Make the new node red October 2004 John Edgar 24

25. Insert 65 47 32 71 93 October 2004 John Edgar 25

26. Insert 65 47 32 71 93 65 October 2004 John Edgar 26

27. Insert as for a binary search tree Make the new node red What can go wrong? (see slide 6) The only property that can be violated is that both a red node s children are black (its parent may be red) So, after inserting, fix the tree by re-colouring nodes and performing rotations October 2004 John Edgar 27

28. The fixing of the tree remedies the problem of two consecutive red nodes There are a number of cases (that s what is next) It is iterative (or recursive) and pushes this problem one step up the tree at each step I.e. if the consecutive red nodes are at level d, at the next step they are at d-1 This is why it turns out to be O(log n) We won t go into the analysis October 2004 John Edgar 28

29. Need to fix tree if new nodes parent is red Case I for fixing: If parent and uncle are both red Then colour them black And colour the grandparent red It must have been black beforehand, why? October 2004 John Edgar 29

30. Insert 65 47 Insert 82 32 71 93 65 October 2004 John Edgar 30

31. Insert 65 47 Insert 82 32 71 93 65 82 October 2004 John Edgar 31

32. Insert 65 47 Insert 82 32 71 71 93 93 65 65 change nodes colours 82 October 2004 John Edgar 32

33. Need to fix tree if new nodes parent is red Case II for fixing: If parent is red but uncle is black Need to do some tree rotations to fix it October 2004 John Edgar 33

34. Insert 65 47 Insert 82 Insert 87 32 71 65 93 82 October 2004 John Edgar 34

35. Insert 65 47 Insert 82 Insert 87 32 71 65 93 82 87 October 2004 John Edgar 35

36. Insert 65 47 Insert 82 Insert 87 32 71 65 93 82 87 October 2004 John Edgar 36

37. Insert 65 47 Insert 82 Insert 87 32 71 65 93 87 82 October 2004 John Edgar 37

38. Insert 65 47 Insert 82 Insert 87 32 71 65 93 93 change nodes colours 87 87 82 October 2004 John Edgar 38

39. Insert 65 47 Insert 82 Insert 87 32 71 65 87 82 93 October 2004 John Edgar 39

40. Why were these rotations performed? First rotation made the two red nodes left children of their parents This rotation isn t performed if this is already the case Note that grandparent must be a black node Second rotation and subsequent recolouring fixes the tree October 2004 John Edgar 40

41. Full details require a few cases See link to example code snippets at end Understand the application of tree rotations October 2004 John Edgar 41

43. Red-black trees are balanced binary search trees Augment each node with a colour Maintaining relationships between node colours maintains balance of tree Important operation to understand: rotation Modify tree but keep binary search tree property (ordering of nodes) October 2004 John Edgar 43

44. For implementation details, please see: http://en.wikipedia.org/wiki/Red-black_tree (see Operations ) October 2004 John Edgar 44