پیشگویی
این مقاله در مورد درخت های جستجوی باینری است. من اخیراً مقاله ای در مورد آن نوشتم در آنجا من واقعاً به درختان باینری توجه نکردم ، زیرا روش های جستجو ، درج ، حذف مرتبط نبود. حالا تصمیم گرفتم مقاله ای در مورد درختان بنویسم. شاید شروع کنیم
درخت یک ساختار داده ای است که از گره هایی به هم متصل شده اند. می توان گفت که درخت یک مورد خاص از یک گراف است. در اینجا یک درخت مثال است:
این درخت جستجوی دودویی نیست! همه چیز زیر برش است!
اصطلاحات
ریشه
ریشه درخت بالاترین گره است. در مثال، این گره A است. در درخت، تنها یک مسیر می تواند از ریشه به هر گره دیگری منتهی شود! در واقع هر گره ای را می توان به عنوان ریشه زیردرخت مربوط به این گره در نظر گرفت.
والدین / فرزندان
همه گره ها به جز ریشه دقیقا یک یال دارند که به گره دیگر منتهی می شود. گره بالای گره فعلی نامیده می شود والدین این گره گرهی که در زیر گره فعلی قرار دارد و به آن متصل است نامیده می شود نسل این گره بیایید یک مثال بزنیم. گره B را بگیرید، سپس والد آن گره A و فرزندان آن گره های D، E و F خواهند بود.
ورق
گره ای که فرزند ندارد برگ درخت نامیده می شود. در مثال، گره های D، E، F، G، I، J، K برگ خواهند بود.
این اصطلاح پایه است. سایر مفاهیم بعداً مورد بحث قرار خواهد گرفت. بنابراین، درخت باینری درختی است که در آن هر گره بیش از دو فرزند نخواهد داشت. همانطور که حدس زدید، درخت مثال باینری نخواهد بود، زیرا گره های B و H بیش از دو فرزند دارند. در اینجا مثالی از درخت دودویی آورده شده است:
گره های درخت می توانند حاوی هر اطلاعاتی باشند. درخت جستجوی باینری یک درخت باینری است که دارای ویژگی های زیر است:
- هر دو زیردرخت چپ و راست درخت های جستجوی دودویی هستند.
- تمام گره های زیردرخت سمت چپ یک گره دلخواه X دارای مقادیر کلید داده کمتر از مقدار کلید داده خود گره X هستند.
- تمام گره های زیردرخت سمت راست یک گره دلخواه X دارای مقادیر کلید داده بزرگتر یا مساوی با مقدار کلید داده خود گره X هستند.
کلید - برخی از ویژگی های گره (به عنوان مثال، یک عدد). کلید مورد نیاز است تا بتوان عنصر درختی که این کلید با آن مطابقت دارد را پیدا کرد. مثال درخت جستجوی باینری:
نمای درختی
همانطور که ادامه می‌دهم، تعدادی (شاید ناقص) کد را به منظور بهبود درک شما اضافه می‌کنم. کد کامل در انتهای مقاله خواهد بود.
درخت از گره ها تشکیل شده است. ساختار گره:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
//...остальные методы узла
}
هر گره دو فرزند دارد (ممکن است فرزندان leftChild و/یا rightChild تهی باشند). احتمالاً متوجه شده اید که در این مورد داده های عددی، داده های ذخیره شده در گره است. کلید - کلید گره.
ما گره را فهمیدیم، حالا بیایید در مورد مشکلات اساسی در مورد درختان صحبت کنیم. در اینجا و در زیر، کلمه "درخت" به معنای مفهوم درخت جستجوی دودویی خواهد بود. ساختار درختی دودویی:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
به عنوان یک فیلد کلاس، ما فقط به ریشه درخت نیاز داریم، زیرا از ریشه، با استفاده از متدهای getLeftChild() و getRightChild() می توانید به هر گره درخت دسترسی پیدا کنید.
الگوریتم های درختی
جستجو
فرض کنید شما یک درخت ساخته شده دارید. چگونه عنصر را با کلید کلید پیدا کنیم؟ شما باید به طور متوالی از ریشه به پایین درخت حرکت کنید و مقدار کلید را با کلید گره بعدی مقایسه کنید: اگر کلید کمتر از کلید گره بعدی است، سپس به سمت چپ گره بروید، اگر بیشتر باشد - در سمت راست، اگر کلیدها برابر باشند - گره مورد نظر پیدا می شود! کد مربوطه:
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
اگر جریان تهی شود، آنگاه تکرار به انتهای درخت رسیده است (در سطح مفهومی، شما در یک مکان ناموجود در درخت هستید - فرزند یک برگ).
کارایی الگوریتم جستجو را روی یک درخت متعادل (درختی که در آن گره ها کم و بیش به طور مساوی توزیع شده اند) در نظر بگیرید. سپس بازده جستجو O(log(n)) و لگاریتم پایه 2 خواهد بود.ببینید: اگر n عنصر در درخت متعادل وجود داشته باشد، این بدان معناست که پایه 2 سطح درخت log(n) وجود خواهد داشت. و در جستجو، برای یک مرحله از چرخه، یک سطح پایین می آیید.
قرار دادن
اگر ماهیت جستجو را درک کرده اید، درک درج برای شما دشوار نخواهد بود. شما فقط باید به برگ درخت بروید (طبق قوانین فرود شرح داده شده در جستجو) و نوادگان آن شوید - چپ یا راست، بسته به کلید. پیاده سازی:
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
در این حالت علاوه بر گره فعلی، لازم است اطلاعات مربوط به والد گره جاری نیز ذخیره شود. وقتی جریان تهی می شود، متغیر والد حاوی برگه مورد نیاز ما خواهد بود.
کارایی درج بدیهی است که همان کارایی جستجو خواهد بود - O(log(n)).
حذف کنید
حذف پیچیده ترین عملیاتی است که باید با درخت انجام شود. واضح است که ابتدا لازم است عنصری را که قصد حذف آن را داریم پیدا کنیم. اما بعدش چی؟ اگر به سادگی مرجع آن را null قرار دهیم، اطلاعات مربوط به زیردرختی که ریشه آن این گره است را از دست خواهیم داد. روش های حذف درخت به سه مورد تقسیم می شوند.
مورد اول گره ای که باید حذف شود فرزندی ندارد.
اگر گره ای که باید حذف شود فرزندی نداشته باشد به این معنی است که یک برگ است. بنابراین، می توانید به سادگی فیلدهای leftChild یا rightChild والد آن را روی null قرار دهید.
مورد دوم. گره ای که باید حذف شود یک فرزند دارد
این مورد هم خیلی سخت نیست. بیایید به مثال خود برگردیم. فرض کنید باید عنصری را با کلید 14 حذف کنیم. موافق باشید که چون فرزند مناسب گره با کلید 10 است، پس هر یک از فرزندان آن (در این مورد، عنصر مناسب) کلیدی بزرگتر از 10 خواهد داشت، بنابراین شما می تواند به راحتی آن را از درخت "برش دهد" و والد را مستقیماً به فرزند گره در حال حذف متصل کند، یعنی. گره را با کلید 10 به گره 13 متصل کنید. اگر بخواهیم گره ای را که فرزند چپ والد آن است حذف کنیم، وضعیت مشابه خواهد بود. خودتان در مورد آن فکر کنید - یک قیاس دقیق.
مورد سوم. گره دو فرزند دارد
سخت ترین مورد. بیایید نگاهی به یک مثال جدید بیاندازیم.
به دنبال جانشین باشید
فرض کنید باید گره را با کلید 25 حذف کنیم. چه کسی را به جای آن قرار دهیم؟ یکی از پیروان او (از اولاد یا اولاد اولاد) باید شود جانشین(کسی که جای گره حذف شده را می گیرد).
چگونه می دانید که چه کسی باید جانشین باشد؟ به طور شهودی، این گره در درخت است که کلید آن بزرگترین گره بعدی است که از گره حذف می شود. الگوریتم به شرح زیر است. باید به فرزند راست آن بروید (همیشه سمت راست، زیرا قبلاً گفته شد که کلید جانشین بزرگتر از کلید گره در حال حذف است) و سپس از زنجیره فرزندان چپ این سمت راست عبور کنید. کودک. در مثال، ما باید به گره با کلید 35 برویم، و سپس زنجیره فرزندان چپ آن را به سمت برگ پایین برویم - در این حالت، این زنجیره فقط از گره با کلید 30 تشکیل شده است. به طور دقیق، ما به دنبال این هستیم کوچکترین گره در مجموعه گره ها بزرگتر از گره مورد نظر است.
کد روش جستجوی جانشین:
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;//родитель преемника
Node<T> successor = deleteNode;//преемник
Node<T> current = successor.getRightChild();//просто "пробегающий" узел
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
//на выходе из цикла имеем преемника и родителя преемника
if (successor != deleteNode.getRightChild()) {//если преемник не совпадает с правым потомком удаляемого узла
parentSuccessor.setLeftChild(successor.getRightChild());//то его родитель забирает себе потомка преемника, чтобы не потерять его
successor.setRightChild(deleteNode.getRightChild());//связываем преемника с правым потомком удаляемого узла
}
return successor;
}
کد کامل روش حذف:
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;//В зависимости от того, является ли удаляемый узел левым или правым потомком своего родителя, булевская переменная isLeftChild будет принимать значение true или false соответственно.
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {//первый случай
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {//второй случай
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {//третий случай
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
پیچیدگی را می توان به O(log(n)) تقریب زد.
یافتن حداکثر/حداقل در یک درخت
بدیهی است که نحوه یافتن حداقل / حداکثر مقدار در درخت - باید به ترتیب از زنجیره عناصر چپ / راست درخت عبور کنید. وقتی به برگ رسیدید، عنصر حداقل/حداکثر خواهد بود.
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
پیچیدگی - O(log(n))
بای پس متقارن
پیمایش بازدید از هر گره درخت به منظور انجام کاری با آن است.
الگوریتم پیمایش متقارن بازگشتی:
- روی کودک چپ یک عمل انجام دهید
- با خودت اقدام کن
- در مورد فرزند مناسب اقدام کنید
کد:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
نتیجه
سرانجام! اگر چیزی را توضیح ندادم یا نظری نداشتم، در نظرات منتظر هستم. همانطور که قول داده بودیم، این کد کامل است.
Node.java:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public void setLeftChild(Node<T> newNode) {
leftChild = newNode;
}
public void setRightChild(Node<T> newNode) {
rightChild = newNode;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
public T getData() {
return data;
}
public int getKey() {
return key;
}
}
BinaryTree.java:
public class BinaryTree<T> {
private Node<T> root;
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;
Node<T> successor = deleteNode;
Node<T> current = successor.getRightChild();
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
if (successor != deleteNode.getRightChild()) {
parentSuccessor.setLeftChild(successor.getRightChild());
successor.setRightChild(deleteNode.getRightChild());
}
return successor;
}
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");
inOrder(current.getRightChild());
}
}
}
PS
انحطاط به O(n)
شاید بسیاری از شما متوجه شده باشید: اگر درخت را نامتعادل کنید چه؟ به عنوان مثال، گره ها را در درخت با کلیدهای افزایش دهنده قرار دهید: 1,2,3,4,5,6،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX... سپس درخت تا حدودی یادآور یک لیست پیوندی خواهد بود. و بله، درخت ساختار درختی خود را از دست خواهد داد و از این رو کارایی دسترسی به داده ها را از دست خواهد داد. پیچیدگی عملیات جستجو، درج و حذف مانند لیست پیوندی خواهد بود: O(n). این یکی از مهمترین، به نظر من، معایب درختان باینری است.
فقط کاربران ثبت نام شده می توانند در نظرسنجی شرکت کنند. ، لطفا.
من مدت زیادی است که در Habré نبوده ام و می خواهم بدانم چه مقالاتی در مورد چه موضوعاتی دوست دارید بیشتر ببینید؟
-
ساختارهای داده
-
الگوریتم ها (DP، بازگشت، فشرده سازی داده ها، و غیره)
-
کاربرد ساختارها و الگوریتم های داده در زندگی واقعی
-
برنامه نویسی برنامه های اندروید در جاوا
-
برنامه نویسی وب اپلیکیشن جاوا
2 کاربر رای دادند 1 کاربر ممتنع.
منبع: www.habr.com