Home PC Games Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ The Linux kernel and AVL tree in red-black tree     - Performance issues under CentOS 6.5 VLAN devices (Linux)

- The default permissions for files and directories under Linux computing (Linux)

- Cool Android realization SVG animation (Programming)

- Restore Oracle Database Cold backup and database reconstruction emca (Database)

- Linux Getting Started tutorial: GNU C and Vim will fight the C / C ++ IDE semi-automatic (Linux)

- Hadoop 1 and 2.x installation notes (Server)

- Linux system monitoring, top command of the diagnostic tool Detailed (Linux)

- Java development specifications summary (Programming)

- Oracle archive log full cause abnormal slow database performance (Database)

- Ubuntu 14.04.02 LTS startup items erroneous writing / dev / sda1 (win 7 loader) Repair (Linux)

- Use Python automatically cleared Android Engineering excess resources (Programming)

- GitLab Installation Guide -Ubuntu 14.04 LTS (Server)

- Spring inject a type of object to enumerate (Programming)

- How to limit network bandwidth usage in Linux (Linux)

- The difference between free command displays the buffers and cache (Linux)

- Upload the project to GitHub, synchronous remote repository Github (Linux)

- Under CentOS 7 installation and deployment environment Ceph (Server)

- The Linux C truncate function clears the file notes (Programming)

- DataGuard a hardware issue warnings found (Database)

- Ubuntu install Vendetta Online 14.04 (Linux)

 
         
  The Linux kernel and AVL tree in red-black tree
     
  Add Date : 2018-11-21      
         
         
         
  Why Linux previously used by AVL trees and red-black tree was predisposed towards?

In fact, this is the result of red-black tree pragmatism characteristics caused this essay is still a metaphysical point of view. Red-black tree can be derived directly from the 2-3 tree, we can no longer mention the red-black tree, but only to mention the 2-3 tree, because the operation is too simple a 2-3 tree. In addition, any operation and characteristics of the red-black tree can be mapped to a 2-3 tree. Therefore, red and black, and AVL trees became 2-3 Comparative Comparative tree and AVL tree.

Where the difference between the two of them? 2-3 balanced tree is perfectly balanced, but it may be the number of branches to three, and AVL tree almost perfectly balanced point binary standard allows only the sub-tree of a height difference of up to 1. So it seems visible, 2-3 tree more balanced than an AVL tree, but the 2-3 tree into a binary tree, red-black tree that is when it is no longer able to maintain the perfect balance, because the trigeminal node to split out a red node so that the sub-tree height plus 1, so it seems, in the strict sense of the red-black tree AVL tree is no balance!

AVL tree at each insertion and deletion must maintain it was "almost point of balance", and red-black tree without disturbing black nodes only need to order a 2-3 tree is concerned, it is after all the expense of a binary tree standard features into a ternary tree to maintain balance. Visible, red-black tree insertion / deletion costs far less than the AVL tree, the query overhead, in theory, a more balanced AVL tree better than the red-black tree (because the tree for 2-3 encountered trigeminal node, you need to compare 2 times), but the red-black tree twice tree height imbalance is a small probability event! So for normal circumstances, you can think of query cost AVL trees and red-black tree is the same, in short, under normal circumstances, is better than the red-black tree AVL tree.

AVL tree was over, while the Linux kernel data structures, especially virtual memory management module, especially the CFS scheduler task column, they are frequently inserted removed, so choose the red-black tree instead of AVL tree .
     
         
         
         
  More:      
 
- High-performance JavaScript loaded and executed (Programming)
- CentOS7 set boot directly into the command line interface (Linux)
- Installation Docker FAQ on Ubuntu (Linux)
- Those things packaged using Gradle to Android (Programming)
- Install Java 8 on Ubuntu using PPA (Linux)
- ActiveMQ memory settings and flow control (Linux)
- In addition to wget and curl, what better alternatives (Linux)
- Hibernate learning introductory tutorial (Programming)
- Java semaphores (Programming)
- Install Oracle 11g illustrations and dependent libraries under SUSE11 (Database)
- MongoDB collection data migration to MySQL database (Database)
- MySQL function: group_concat () function (Database)
- How to install Linux Go Language (Linux)
- What is Java EE (Programming)
- Basic Tutorial: Linux novice should know 26 commands (Linux)
- How to find on Linux and delete duplicate files: FSlint (Linux)
- Java garbage collection (Programming)
- 25 Git Usage Tips (Linux)
- Analysis of MySQL High Availability (Database)
- Linux operating system security management skills notes (Linux)
     
           
     
  CopyRight 2002-2022 newfreesoft.com, All Rights Reserved.