当前位置:网站首页>Binary search tree concept
Binary search tree concept
2022-07-06 14:22:00 【xmh-sxh-1314】
In the article 《 Common data structure and complexity 》 in , This paper introduces some linear data structures commonly used in computer programming , Include Array、ArrayList、LinkedList<T>、List<T>、Stack<T>、Queue<T>、Hashtable and Dictionary<T> etc. . It also briefly introduces the internal implementation principle of these data structures and the computational complexity of common operations , And how to choose the appropriate data structure . In this article , We will introduce the common tree structure and the computational complexity of common operations .
Binary tree (Binary Tree)
A complete binary tree and a full binary tree
Binary search tree (Binary Search Tree)
Insert node
Delete node
Traversal node
We know something like genealogy 、 The organizational structure of the company organizes data in the form of tree structure . For example, the company organization chart shown in the figure below .
Trees (Tree) It consists of multiple nodes (Node) The collection of , Each node has multiple child nodes associated with it (Child Node). The child node is the node directly under the node , And the parent node (Parent Node) It is located above the direct association of nodes . The root of the tree (Root) It refers to a separate node without a parent node .
All trees show some common properties :
Only one root node ;
Except for the root node , All nodes have only one parent ;
acyclic . Take any node as the starting node , There is no path back to the starting node .( It is the first two properties that guarantee the establishment of acyclic .)
Terms used in trees
root (Root): The topmost node in the tree , The root has no parent node .
Child node (Child): The root node of the subtree owned by the node is called the child node of the node .
Parent node (Parent): If the node has child nodes , Then this node is the parent node of the child node .
Brother node (Sibling): A node that has the same parent node as the node .
Descendants node (Descendant): Nodes reachable on the downward path .
Leaf nodes (Leaf): Nodes without children .
Inner node (Internal Node): A node that has at least one child node .
degree (Degree): The number of subtrees a node has .
edge (Edge): The link between the two nodes .
route (Path): The sequence of edges and nodes in the process from node to descendant node .
Hierarchy (Level): Root is Level 0 layer , The child nodes of the root are Level 1 layer , And so on .
Height (Height)/ depth (Depth): The number of middle layers in the tree . Such as the only Level 0,Level 1,Level 2 Then the height is 3.
Category
Tree name
Binary search tree
(Binary Search Tree)
Binary search tree , Cartesian tree ,T Trees
Self-balancing binary search tree
(Self-balancing Binary Search Tree)
AA Trees ,AVL Trees ,
Red and black trees (Red-Black Tree),
Stretch the tree (Splay Tree)
B Trees
(B-Tree)
2-3 Trees ,2-3-4 Trees ,
B Trees ,B+ Trees ,B* Trees
Dictionary tree
(Trie-Tree)
Suffix tree , Cardinal tree , Trident lookup tree , Fast prefix tree
Spatial data segmentation tree
(Spatial Data Partitioning Tree)
R Trees ,R+ Trees ,R* Trees ,
Line segment tree , first R Trees
Binary tree (Binary Tree)
Binary tree (Binary Tree) Is a special type of tree , Each node can only have two child nodes at most . These two child nodes are respectively called the left child of the current node (left child) And the right child (right child).
Above picture , Binary tree (a) contain 8 Nodes , Where nodes 1 Is its root node . node 1 The left child is the node 2, The right child is the node 3. Be careful , There is no requirement for a node to have both left and right children . for example , Binary tree (a) in , node 4 There is only one right child 6. Besides , Nodes can also have no child nodes . for example , Binary tree (b) in , node 4、5、6、7 There are no child nodes .
Nodes without children are called leaf nodes (Leaf Node), Nodes with children are called inner nodes (Internal Node). Such as in the figure above , Binary tree (a) Nodes in 6、8 For leaf nodes , node 1、2、3、4、5、7 Is the inner node .
A complete binary tree and a full binary tree
Perfect binary tree (Complete Binary Tree): Depth is h, Yes n A binary tree of nodes , If and only if each of its nodes has a depth of h In a full binary tree , Serial number is 1 to n When the node corresponding to , It's called a complete binary tree .
Full binary tree (Full Binary Tree): The depth of a tree is one h, And there are 2h - 1 A node is called a full binary tree .
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
A full binary tree is a tree in which every node other than the leaves has two children.
Perfect binary tree Full binary tree
Total nodes k 2h-1 <= k < 2h - 1
k = 2h - 1
Tree height h h = log2k + 1
h = log2(k + 1)
.NET There is no direct implementation of binary tree in , We need to achieve it by ourselves BinaryTree class . stay 《 Have you ever implemented a binary tree 》 In the article , A simple binary tree model based on generics is implemented .
We have learned that an array is a continuous arrangement of elements in memory , The binary tree is not stored in continuous memory . actually , Usually BinaryTree The instance of the class contains only the root node (Root Node) Instance reference , The root node instance points to its left and right child node instances , And so on . So the key difference is , The node object instances that make up the binary tree can be dispersed to CLR Anywhere in the managed heap , They don't have to be stored continuously like array elements .
If you want to access a node in the binary tree , Usually, you need to traverse the nodes in the binary tree one by one , To locate that node . It does not have direct access to the specified node like an array . So the asymptotic time of finding binary tree is linear O(n), In the worst case, you need to find all the nodes in the tree . in other words , As the number of binary tree nodes increases , The number of steps to find any node will increase accordingly .
that , If the search time of a binary tree is linear , The positioning time is also linear , Where is the advantage over arrays ? After all, although the search time of the array is linear O(n), But the positioning time is constant O(1) ah ? That's true , Generally speaking, ordinary binary trees really can't provide better performance than arrays . However , If we organize and arrange the elements in the binary tree according to certain rules , It can greatly improve the query time and positioning time .
Binary search tree (Binary Search Tree)
Binary search tree (BST:Binary Search Tree) It's a special binary tree , It improves the efficiency of searching nodes in binary tree . Binary search trees have the following properties :
For any node n,
Its left subtree (left subtree) Every descendant node under (descendant node) The values of are all smaller than the nodes n Value ;
Its right subtree (right subtree) The value of each descendant node under is greater than the node n Value .
So called node n The subtree of , You can think of it as a node n Is the tree of the root node . All nodes of a subtree are nodes n The offspring of , The root of a subtree is a node n In itself .
The following figure shows two binary trees . Binary tree (b) It's a binary search tree (BST), It conforms to the property of binary search tree . And binary trees (a), Is not a binary search tree . Because of the node 10 Right child node of 8 Less than nodes 10, But it appears at the node 10 In the right subtree . Again , node 8 Right child node of 4 Less than nodes 8, But it appears in its right subtree . No matter where it is , As long as it does not conform to the nature of binary search tree , It's not a binary search tree . for example , node 9 The left subtree of can only contain nodes with values less than 9 The node of , That is to say 8 and 4.
From the properties of binary search tree ,BST The data stored by each node must be able to be compared with other nodes . Given any two nodes ,BST You must be able to judge whether the value of these two nodes is less than 、 Greater than or equal to .
Suppose we're looking for BST A node in . For example, the binary search tree in the above figure (b) in , We need to find a value of 10 The node of .
We start from the root . You can see , The value of the root node is 7, Less than the node value we are looking for 10. therefore , If node 10 There is , It must exist in its right subtree , So you should skip to the node 11 Continue to find . here , Node values 10 Less than nodes 11 Value , The node 10 It must exist at the node 11 In the left subtree . Looking for nodes 11 The left child , At this point, we have found the target node 10, Locate here .
What if the node we are looking for does not exist in the tree ? for example , We need to find nodes 9. Repeat the above operation , Until you reach the node 10, It is larger than the node 9, So if the node 9 There is , It must exist at the node 10 In the left subtree . However, we see nodes 10 There is no left child at all , So nodes 9 There is no... In the tree .
In conclusion , The search algorithm we use is as follows :
Suppose we want to find nodes n, from BST The root node of . The algorithm constantly compares the size of the node value until it finds the node , Or determine that it does not exist . We have to deal with two nodes in each step : A node in the tree , Referred to as a node c, And the node to find n, Then compare c and n Value . At the beginning of the , node c by BST The root node . Then perform the following steps :
If c Value is empty , be n be not in BST in ;
Compare c and n Value ;
If the values are the same , Then the specified node is found n;
If n The value is less than c, So if n There is , Must be in c In the left subtree . Back to the first 1 Step , take c My left child as c;
If n The value is greater than c, So if n There is , Must be in c In the right subtree . Back to the first 1 Step , take c My right child as c;
adopt BST Find node , Ideally, the number of nodes we need to check can be halved . As shown in the figure below BST Trees , Contains 15 Nodes . Execute the search algorithm from the root node , The first comparison determines whether we move to the left subtree or the right subtree . In either case , Once you perform this step , The number of nodes we need to visit is reduced by half , from 15 Down to 7. Again , The number of nodes visited in the next step has also been reduced by half , from 7 Down to 3, And so on .
According to this characteristic , The time complexity of the search algorithm should be O(log2n), Shorthand for O(lg n). We are in the article 《 Algorithm complexity analysis 》 There are some descriptions about time complexity in . You know ,log2n = y, amount to 2y = n. namely , If the number of nodes increases n, The search time only slowly increases to log2n. The following figure shows O(log2n) And linear growth O(n) The difference between growth rates . The time complexity is O(log2n) The running time of the algorithm is the following line .
As can be seen from the above figure ,O(log2n) The curve is almost horizontal , With n An increase in value , The curve grows very slowly . for instance , Find a with 1000 Array of elements , Need to check 1000 Elements , And find one with 1000 An element of BST Trees , Only need to query 10 Nodes (log21024 = 10).
But in fact , about BST Search Algorithm , It depends very much on the topology of the nodes in the tree , That is, the layout relationship between nodes . The following figure depicts a node inserted in the order 20, 50, 90, 150, 175, 200 Of BST Trees . These nodes are inserted in ascending order , The result is that the tree has no breadth (Breadth) At all . in other words , Its topology is actually to arrange nodes on a line , Instead of spreading out in a fan-shaped structure , So the search time is O(n).
When BST When the nodes in the tree are scattered in a fan-shaped structure , Insert it 、 The sub linear running time can be achieved when the deletion and search operations are optimal O(log2n). Because when BST When looking for a node in , After each comparison operation, the number of nodes will be reduced by half . For all that , If the topology looks like the one in the above figure , The running time will be reduced to linear time O(n). Because after each comparison operation, you still need to compare the remaining nodes one by one . in other words , under these circumstances , stay BST Find nodes in the array (Array) Search in is basically similar .
therefore ,BST The search time of the algorithm depends on the topology of the tree . The best situation is O(log2n), And the worst case is O(n).
Insert node
We not only need to know how to find a node in the binary search tree , You also need to know how to insert and delete a node in the binary lookup tree .
When inserting a new node into the tree , This node will always
边栏推荐
- captcha-killer验证码识别插件
- 强化学习基础记录
- xray与burp联动 挖掘
- An unhandled exception occurred when C connected to SQL Server: system Argumentexception: "keyword not supported:" integrated
- Strengthen basic learning records
- xray與burp聯動 挖掘
- HackMyvm靶机系列(5)-warez
- Attack and defense world misc practice area (GIF lift table ext3)
- Get started with typescript
- 记一次edu,SQL注入实战
猜你喜欢
Internet Management (Information Collection)
搭建域环境(win)
Tencent map circle
captcha-killer验证码识别插件
Network layer - simple ARP disconnection
Hackmyvm Target Series (3) - vues
1143_ SiCp learning notes_ Tree recursion
《统计学》第八版贾俊平第十三章时间序列分析和预测知识点总结及课后习题答案
强化学习基础记录
Harmonyos application development -- address book management system telmanagesys based on listcontainer [phonebook][api v6]
随机推荐
Meituan dynamic thread pool practice ideas, open source
JDBC read this article is enough
7-15 h0161. Find the greatest common divisor and the least common multiple (PTA program design)
【Numpy和Pytorch的数据处理】
内网渗透之内网信息收集(四)
Strengthen basic learning records
Feature extraction and detection 14 plane object recognition
Experiment 9 input and output stream (excerpt)
Harmonyos JS demo application development
强化學習基礎記錄
7-1 output all primes between 2 and n (PTA programming)
Web vulnerability - File Inclusion Vulnerability of file operation
链队实现(C语言)
Experiment 6 inheritance and polymorphism
JDBC事务、批处理以及连接池(超详细)
Detailed explanation of three ways of HTTP caching
Detailed explanation of network foundation routing
Hackmyvm target series (1) -webmaster
《统计学》第八版贾俊平第十四章指数知识点总结及课后习题答案
Yugu p1012 spelling +p1019 word Solitaire (string)