1. แนวคิด
ต้นไม้ค้นหาไบนารีก็กลายเป็นต้นไม้เรียงลำดับไบนารี มันมีลักษณะที่ว่าถ้าโหนดมีลูกสองโหนดจะต้องพอใจ ค่าของโหนดเด็กด้านซ้ายจะต้องเล็กกว่าค่าของโหนดและค่าของโหนดเด็กที่เหมาะสมจะต้องมากกว่าค่าของโหนด สำหรับการเปรียบเทียบประเภทที่ไม่ใช่พื้นฐานสามารถนำอินเตอร์เฟสเปรียบเทียบได้ ในบทความนี้ข้อมูลประเภท INT ใช้สำหรับการทำงาน
ในการใช้ทรีไบนารีคุณต้องเริ่มต้นด้วยการเพิ่มขึ้น โดยการสร้างต้นไม้เท่านั้นคุณสามารถใช้การดำเนินการอื่น ๆ ได้
2. การก่อสร้างต้นไม้ค้นหาไบนารี
เมื่อพูดถึงการเพิ่มขึ้นของต้นไม้ไบนารีเราต้องสร้างชั้นเรียนก่อนเป็นตัวแทนโหนด คลาสของโหนดมีหลายแอตทริบิวต์ค่าของโหนดโหนดพาเรนต์โหนดซ้ายและโหนดขวาของโหนด รหัสมีดังนี้
โหนดคลาสคงที่ {โหนดพาเรนต์; โหนดซ้าย; โหนด RightChild; int val; โหนดสาธารณะ (โหนดพาเรนต์, โหนดซ้าย, โหนดขวา, int val) {super (); this.parent = Parent; this.leftchild = leftchild; this.rightChild = RightChild; this.val = val; } โหนดสาธารณะ (int val) {this (null, null, null, val); } โหนดสาธารณะ (โหนดโหนด, int val) {สิ่งนี้ (โหนด, null, null, val); -ที่นี่เราใช้วิธีการเขียนชั้นเรียนภายใน หลังจากสร้างค่าโหนดเราจะสร้างต้นไม้ทั้งหมด ต้นไม้จะต้องมีโหนดรูทก่อนจากนั้นขยายไปยังโหนดลูกที่เหลือ ในต้นไม้นี้มีคุณลักษณะบางอย่างเช่นรากโหนดรากพื้นฐานและขนาดองค์ประกอบในต้นไม้ หากมีการใช้แอตทริบิวต์ทั้งสองนี้แอตทริบิวต์ตัวเปรียบเทียบอาจถูกเพิ่มหรืออาจมีการใช้งานเริ่มต้น รหัสเฉพาะมีดังนี้
Public Class SearchBinaryTree {รูทโหนดส่วนตัว; ขนาด int ส่วนตัว; Public SearchBinaryTree () {super (); -3. เพิ่ม
เมื่อเพิ่มองค์ประกอบคุณต้องพิจารณาการเริ่มต้นของโหนดรูท โดยทั่วไปมีสองประเภท: เมื่อตัวสร้างของคลาสนี้เริ่มต้นรูทรูทรูทรูทจะเริ่มต้น ประการที่สองคือการเพิ่มโหนดรูทเมื่อมีการเพิ่มองค์ประกอบแรก ทั้งคู่ทำงานในทางทฤษฎี แต่มักจะใช้แบบฟอร์มการโหลดขี้เกียจที่สอง
เมื่อเพิ่มองค์ประกอบมีหลายสถานการณ์ที่ต้องพิจารณา
1. เมื่อเพิ่มให้พิจารณาว่ารูทจะเริ่มต้นหรือไม่ หากไม่ได้เริ่มต้นมันจะเริ่มต้น กำหนดค่าให้กับโหนดรูทและเพิ่มหนึ่งขนาด
2. เนื่องจากแผนผังการค้นหาต้นไม้ไบนารีเป็นไปตามค่าโหนดรูทมากกว่าโหนดซ้ายและเล็กกว่าโหนดด้านขวาค่าที่แทรกจะต้องเปรียบเทียบกับโหนดรูทก่อน หากมีขนาดใหญ่ให้ค้นหาในทรีย่อยที่ถูกต้อง หากมีขนาดเล็กให้ค้นหาในทรีย่อยด้านซ้าย จนถึงโหนดเด็ก
การใช้งานการแทรกที่นี่สามารถนำมาใช้สองประเภท: หนึ่ง, การเรียกซ้ำ, สอง, ซ้ำ (เช่นผ่านในขณะที่โหมดลูป)
3.1. การแทรกเวอร์ชันแบบเรียกซ้ำ
บูลีนสาธารณะเพิ่ม (int val) {ถ้า (root == null) {root = new node (val); ขนาด ++; กลับมาจริง; } โหนดโหนด = getAdapternode (root, val); โหนด newNode = new node (val); if (node.val> val) {node.leftchild = newNode; newNode.parent = node; } อื่นถ้า (node.val <val) {node.rightchild = newNode; newNode.parent = node; } else {// ไม่มีการประมวลผลสำหรับเวลา} size ++; 19 return true; } /*** รับโหนดพาเรนต์ของโหนดที่จะแทรก โหนดพาเรนต์ตรงกับหนึ่งในสถานะต่อไปนี้* 1. โหนดพาเรนต์เป็นโหนดลูก* 2 ค่าของโหนดการแทรกมีขนาดเล็กกว่าโหนดพาเรนต์ แต่โหนดพาเรนต์ไม่มีโหนดลูกซ้าย* 3 ค่าของโหนดการแทรกมีขนาดใหญ่กว่าโหนดแม่แม่ * 5. โหนดพาเรนต์ว่างเปล่า* หากหนึ่งใน 5 กรณีข้างต้นเป็นที่พอใจมันจะหยุดซ้ำ * @param Node * @param val * @return */ โหนดส่วนตัว getAdapternode (โหนดโหนด, int val) {ถ้า (node == null) {return node; } // แทรกลงในทรีย่อยด้านซ้าย แต่ไม่มีทรีย่อยด้านซ้ายถ้า (node.val> val && node.leftchild == null) {return node; } // แทรกลงในทรีย่อยด้านขวา แต่ไม่มีทรีย่อยที่ถูกต้องกลับมาหาก (node.val <val && node.rightchild == null) {return node; } // แทรกลงในทรีย่อยด้านขวา แต่ไม่มีทรีย่อยที่ถูกต้องกลับมาหาก (node.val <val && node.rightchild == null) {return node; } // แทรกลงในทรีย่อยด้านขวา แต่ไม่มีทรีย่อยที่ถูกต้องกลับมาหาก (node.val <val && node.rightchild == null) {return node; } // แทรกลงในทรีย่อยด้านขวา แต่ไม่มีทรีย่อยที่ถูกต้องกลับมาอีกด้วย (node.leftchild == null && node.rightchild == null) {return node; } if (node.val> val && node.leftchild! = null) {return getadaptarnode (node.leftchild, val); } อื่นถ้า (node.val <val && node.rightchild! = null) {return getAdaptarnode (node.rightchild, val); } else {return node; -ใช้การเรียกซ้ำก่อนค้นหาจุดสิ้นสุดของการเรียกซ้ำแล้วเปลี่ยนปัญหาทั้งหมดให้เป็นปัญหาย่อย ในรหัสข้างต้นตรรกะนั้นประมาณนี้: ก่อนอื่นกำหนดว่าโหนดรูทจะเริ่มต้นหรือไม่และหากไม่ได้เริ่มต้นจะเริ่มต้นและหลังจากเสร็จสิ้นมันจะกลับมาแล้วใช้ฟังก์ชั่นเพื่อรับโหนดที่ดัดแปลง จากนั้นแทรกค่า
3.2. เวอร์ชันวนซ้ำ
บูลีนสาธารณะใส่ (int val) {return putval (root, val); } บูลีนส่วนตัว putval (โหนดโหนด, int val) {ถ้า (node == null) {// เริ่มต้นโหนดรูทโหนด = โหนดใหม่ (val); root = node; ขนาด ++; กลับมาจริง; } โหนดอุณหภูมิ = โหนด; โหนด P; int t; / ** * รับโหนดที่ดีที่สุดผ่านการทำซ้ำในขณะที่วนซ้ำ, */ ทำ {p = temp; t = temp.val-val; if (t> 0) {temp = temp.leftchild; } อื่นถ้า (t <0) {temp = temp.rightchild; } else {temp.val = val; กลับเท็จ; }} ในขณะที่ (temp! = null); โหนด newNode = โหนดใหม่ (p, val); if (t> 0) {p.leftchild = newNode; } อื่นถ้า (t <0) {p.rightChild = newNode; } size ++; กลับมาจริง; -หลักการนั้นเหมือนกับการเรียกซ้ำซึ่งจะได้รับโหนดที่ดีที่สุดและทำงานบนโหนดนั้น
ในแง่ของประสิทธิภาพมันเป็นเวอร์ชันซ้ำที่ดีที่สุดดังนั้นโดยทั่วไปแล้วมันเป็นเวอร์ชันวนซ้ำที่จะใช้งานกับข้อมูล
4. ลบ
อาจกล่าวได้ว่าในการดำเนินการของแผนผังไบนารีการลบนั้นมีความซับซ้อนมากที่สุดและมีสถานการณ์ที่ต้องพิจารณาค่อนข้างมาก ในวิธีการทั่วไปถ้าคุณลบโหนดในแผนผังไบนารีคุณจะนึกถึงสถานการณ์สี่สถานการณ์ต่อไปนี้อย่างแน่นอน
1. โหนดที่จะลบไม่มีโหนดลูกซ้ายและขวาดังแสดงในโหนด D, E และ G ในรูปด้านบน
2. โหนดที่จะลบเป็นเพียงโหนดลูกซ้ายเช่นโหนด B
3. โหนดที่จะถูกลบเป็นเพียงโหนดลูกที่เหมาะสมเช่นโหนด F
4. โหนดที่จะถูกลบมีทั้งโหนดลูกซ้ายและโหนดลูกที่ถูกต้องเช่นโหนด A และ C
สำหรับสามสถานการณ์แรกอาจกล่าวได้ว่ามันค่อนข้างง่ายในขณะที่สถานการณ์ที่สี่มีความซับซ้อน มาวิเคราะห์อันแรก
หากเป็นกรณีนี้ตัวอย่างเช่นหากมีการลบโหนด D โหนดเด็กด้านซ้ายของโหนด B สามารถตั้งค่าเป็น null และหากโหนด G ถูกลบโหนดลูกที่ถูกต้องของโหนด F สามารถตั้งค่าเป็น null ได้ ควรตั้งค่าด้านใดและดูว่าโหนดที่ถูกลบอยู่ด้านใด
วิธีที่สองในการลบโหนด B คุณเพียงแค่ตั้งค่าโหนดซ้ายของโหนด A เป็นโหนด D และโหนดพาเรนต์ของโหนด D เป็น A ซึ่งตั้งค่าด้านใดขึ้นอยู่กับว่าด้านใดของโหนดที่ถูกลบอยู่บนโหนดพาเรนต์
ประเภทที่สามเหมือนกับประเภทที่สอง
ประเภทที่สี่ซึ่งมีความซับซ้อนเล็กน้อยตามที่กล่าวไว้ก่อนหน้านี้คือการลบโหนด C ตั้งค่าโหนดพาเรนต์ของโหนด F เป็นโหนด A ตั้งค่าโหนดด้านซ้ายของโหนด F เป็นโหนด E ตั้งโหนดขวาของโหนด F, ตั้งค่าโหนด parent ของ e เป็น node ดังนั้นควรใช้อันไหน? หากโหนดลบเป็นโหนดรูทฉันจะลบได้อย่างไร?
สำหรับกรณีที่สี่คุณสามารถนึกถึงสิ่งนี้: ค้นหาโหนดผู้สืบทอดของ C หรือโหนดลบโหนดผู้สืบทอดและตั้งค่าของโหนดผู้สืบทอดเป็นค่าของ C หรือโหนด ก่อนอื่นมาเสริมแนวคิดของโหนดผู้สืบทอด
โหนดผู้สืบทอดของโหนดในต้นไม้ทั้งหมดจะต้องพอใจ โหนดที่มีค่าที่เล็กที่สุดในชุดของโหนดที่มีค่าโหนดคือโหนดผู้สืบทอด แน่นอนว่าอาจไม่มีโหนดผู้สืบทอด
อย่างไรก็ตามสำหรับกรณีที่สี่โหนดผู้สืบทอดจะต้องมีอยู่และจะต้องอยู่ในทรีย่อยที่ถูกต้องและมันก็ตรงกับหนึ่งในกรณีที่มีโหนดเด็กเพียงหนึ่งโหนดหรือไม่มีโหนดเด็ก เหตุผลที่เฉพาะเจาะจงอาจเป็นสิ่งนี้ได้เนื่องจากโหนดผู้สืบทอดมีขนาดใหญ่กว่าโหนด C และเนื่องจากส่วนย่อยด้านซ้ายและขวาของโหนด C ต้องมีอยู่จึงต้องมีอยู่ในส่วนย่อยด้านซ้ายในต้นไม้ย่อยด้านขวา ตัวอย่างเช่นโหนดผู้สืบทอดของ C คือ F และโหนดผู้สืบทอดของ A คือ E.
ด้วยการวิเคราะห์ข้างต้นการใช้งานค่อนข้างง่ายรหัสมีดังนี้
บูลีนสาธารณะลบ (int val) {node node = getNode (val); if (node == null) {return false; } node parent = node.parent; โหนด leftchild = node.leftchild; โหนด RightChild = node.rightChild; // โหนดพาเรนต์ทั้งหมดต่อไปนี้ว่างเปล่าหมายความว่าโหนดที่ถูกลบคือโหนดรูทถ้า (ซ้าย == null && rightChild == null) {// ไม่มีโหนดลูกถ้า (parent! = null) {ถ้า (parent.leftchild == node) {parent.leftchild = null; } อื่นถ้า (parent.rightchild == node) {parent.rightchild = null; }} else {// โหนดพาเรนต์ไม่มีอยู่ซึ่งหมายความว่าโหนดที่ถูกลบคือรูทรูทรูทรูท = null; } node = null; กลับมาจริง; } อื่นถ้า (leftChild == null && rightChild! = null) {// เฉพาะโหนดที่ถูกต้องถ้า (parent! = null && parent.val> val) {// มีโหนดพาเรนต์ } อื่นถ้า (parent! = null && parent.val <val) {// มีโหนดพาเรนต์และตำแหน่งโหนดเป็นด้านขวาของ parent parent.rightchild = rightChild; } else {root = rightChild; } node = null; กลับมาจริง; } อื่นถ้า (leftChild! = null && rightChild == null) {// เฉพาะโหนดซ้ายถ้า (parent! = null && parent.val> val) {// มีโหนดพาเรนต์ } อื่นถ้า (parent! = null && parent.val <val) {// มีโหนดพาเรนต์และตำแหน่งโหนดเป็นด้านขวาของ parent parent.rightchild = leftChild; } else {root = leftchild; } return true; } อื่นถ้า (leftChild! = null && rightChild! = null) {// โหนดเด็กทั้งสองมีโหนดผู้สืบทอด = getSuccessor (โหนด); // ในกรณีนี้จะต้องมีโหนดผู้สืบทอด บูลีนลบ = ลบ (อุณหภูมิ); if (ลบ) {node.val = temp; } ผู้สืบทอด = null; กลับมาจริง; } return false; } /*** ค้นหาโหนดผู้สืบทอดของโหนดโหนด* 1 ก่อนกำหนดว่าโหนดมีทรีย่อยที่เหมาะสมหรือไม่ ถ้าเป็นเช่นนั้นให้มองหาโหนดผู้สืบทอดจากทรีย่อยด้านซ้ายของโหนดขวา ถ้าไม่ให้ไปยังขั้นตอนถัดไป* 2. ค้นหาโหนดพาเรนต์ของโหนด หากโหนดขวาของโหนดพาเรนต์เท่ากับโหนดให้ดำเนินการต่อเพื่อค้นหาโหนดพาเรนต์ * จนกว่าโหนดพาเรนต์จะเป็นโมฆะหรือค้นหาโหนดขวาที่ไม่เท่ากับโหนด * เหตุผลโหนดผู้สืบทอดจะต้องใหญ่กว่าโหนด หากมีทรีย่อยที่ถูกต้องโหนดผู้สืบทอดจะต้องมีอยู่ในทรีย่อยด้านขวา นี่คือเหตุผลสำหรับขั้นตอนแรก* หากไม่มีทรีย่อยที่ถูกต้องอาจมีโหนดปู่ของโหนด (เช่นโหนดพาเรนต์ของโหนดหรือโหนดพาเรนต์เหนือโหนดพาเรนต์) * ค้นหาซ้ำ ๆ ถ้ามีมันจะส่งคืนโหนดและหากไม่มีมันจะส่งคืน null * @param node * @return */ โหนดส่วนตัว getSuccessor (โหนดโหนด) {ถ้า (node.rightchild! = null) ในขณะที่ (rightChild.leftchild! = null) {rightChild = RightChild.leftchild; } return rightchild; } node parent = node.parent; ในขณะที่ (parent! = null && (node == parent.rightchild)) {node = parent; ผู้ปกครอง = parent.parent; } ส่งคืนพาเรนต์; -สำหรับตรรกะเฉพาะโปรดดูการวิเคราะห์ข้างต้น ฉันจะไม่อธิบายข้อความที่นี่
นอกเหนือจากการใช้งานนี้แล้วการดำเนินการอื่นยังมีอยู่ในการแนะนำอัลกอริทึม
บูลีนสาธารณะลบ (int val) {node node = getNode (val); if (node == null) {return false; } if (node.leftchild == null) {// 1. โหนดซ้ายไม่มีอยู่โหนดขวาอาจมีอยู่รวมถึงสองสถานการณ์ ทั้งสองโหนดไม่มีอยู่และมีเพียงโหนดที่ถูกต้องเท่านั้นที่มีการปลูกถ่าย (โหนด, node.rightchild); } อื่นถ้า (node.rightchild == null) {// 2 มีลูกซ้ายอยู่และโหนดขวาไม่มีการปลูกถ่าย (โหนด, node.leftchild); } else {// 3. ทั้งสองโหนดมีโหนดผู้สืบทอด = getSuccessor (โหนด); // รับโหนดโหนดผู้สืบทอดถ้า (successor.parent! = node) {// โหนดผู้สืบทอดอยู่ในทรีย่อยที่ถูกต้องของโหนด การปลูกถ่าย (ผู้สืบทอด, ผู้สืบทอด. RightChild); // แทนที่ผู้สืบทอดด้วยโหนดลูกที่ถูกต้องของผู้สืบทอดตำแหน่ง rightchild = node.rightchild; // กำหนดต้นไม้ลูกที่เหมาะสมของโหนดโหนดไปยังโหนดที่ถูกต้องของผู้สืบทอด การปลูกถ่าย (โหนดผู้สืบทอด); ผู้สืบทอด. leftchild = node.leftchild; ผู้สืบทอด. leftchild.parent = ผู้สืบทอด; } return true; } /*** แทนที่โหนดเด็กด้วยโหนดโหนด* @param รูทรูทโหนด* @param โหนดโหนดโหนดเพื่อลบ* @param ลูกโหนดลูกโหนดลูกโหนดโหนดเด็กโหนดโหนดลูกโหนดลูกโมฆะ ขั้นตอน* 2. พิจารณาว่าโหนดโหนดเป็นลูกของโหนดพาเรนต์ (นั่นคือตรวจสอบว่าโหนดเป็นโหนดขวาหรือโหนดซ้าย)* หลังจากได้รับผลลัพธ์ให้แทนที่โหนดเด็กด้วยโหนดโหนดนั่นคือถ้าโหนดโหนดเป็นโหนดของโหนด Node*/ if (node.parent == null) {this.root = child; } อื่นถ้า (node.parent.leftchild == node) {node.parent.leftchild = child; } อื่นถ้า (node.parent.rightchild == node) {node.parent.rightchild = child; } if (child! = null) {child.parent = node.parent; -5. ค้นหา
การค้นหานั้นค่อนข้างง่าย แต่ที่จริงแล้วมันถูกนำไปใช้เมื่อมีการเพิ่ม ในสถานการณ์จริงส่วนนี้สามารถสกัดได้จากวิธีการแยกต่างหาก รหัสมีดังนี้
โหนดสาธารณะ getNode (int val) {โหนด temp = root; int t; ทำ {t = temp.val-val; if (t> 0) {temp = temp.leftchild; } อื่นถ้า (t <0) {temp = temp.rightchild; } else {return temp; }} ในขณะที่ (temp! = null); คืนค่า null; -6. ต้นไม้ค้นหาไบนารีสำรวจ
หลังจากทำความเข้าใจคุณสมบัติของแผนผังการค้นหาไบนารีเป็นที่ชัดเจนว่าคำสั่งกลางของมันถูกจัดเรียงตามลำดับจากขนาดเล็กไปใหญ่ นี่คือรหัสการเดินทางคำสั่งซื้อระดับกลางที่ให้ไว้ที่นี่
Public Void Print () {print (root); } private void print (node root) {if (root! = null) {print (root.leftchild); System.out.println (root.val); // ถ้าตำแหน่งอยู่ตรงกลางแล้วคำสั่งจะอยู่ตรงกลาง ถ้าอยู่ด้านหน้ามันอยู่ในแบบอย่างมิฉะนั้นจะเป็นงานพิมพ์ที่ตามมา (root.rightchild); - สรุป
ด้านบนคือการใช้งาน Java ของฟังก์ชั่นการค้นหาแบบไบนารีที่แนะนำโดยบรรณาธิการ ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน หากคุณมีคำถามใด ๆ โปรดฝากข้อความถึงฉัน บรรณาธิการจะตอบกลับทุกคนในเวลา!